本文是寻路算法的实际应用篇，以贪吃蛇的实现为例子。

　　1.首先看下这个在微博上很火的贪吃蛇gif

　　这次我们尝试用代码来模拟下，说不定上面这个图就是计算机搞的。

　　2.讲贪吃蛇snake AI之前，我们先看下贪吃蛇移动的特点

　　物理上给人的感觉是整个贪吃蛇往右移了一步，在贪吃蛇非常长的情况下给人的感觉移一步要做很多事情。但是在计算机中我们可以简单的考虑贪吃蛇的移动，假设用一个数组来存储所有组成贪吃蛇的格子，那么移动一步，就是把将来的格子插入到这个数组的头部，然后再去掉这个数组的最后一个元素。我们只做两件事情，就完成了一整条蛇的移动！往下看之前，再仔细考虑下移动这个问题。
　　在说贪吃蛇AI之前，我们要考虑一个问题：怎样保证贪吃蛇永远不死？我们知道无论往那个方向前进一步，尾巴的格子都会空出来，那么追着贪吃蛇的尾巴移动，就能保证贪吃蛇永远不死！

　　3.寻路算法之A Star

　　贪吃蛇一般情况下要找一个最短路线去吃苹果，这个时候A star寻路算法就派上用场了，如果你对A Star 算法还不了解，可以先看下这篇文章：《Cocos2d-x 寻路算法之三 A Star》 。这里用A Star 需要特别注意两个问题：1.整个蛇的身体是不可接触的格子的，要排除掉。2.因为贪吃蛇移动是一个动态的过程，所以每走一步，要重新进行寻路，而不是一次寻路完，走完路线，因为尾巴的位置会不断的空出来。

　　4.单纯使用寻路算法遇到的问题

　　4.1会进入死胡同

　　黄色的是贪吃蛇的头部，红色是我们要吃的东西，根据寻路算法，黑色的就是最短路线，可以在脑子里脑补下，吃完这个东西，贪吃蛇就挂了！

　　4.2 找不到路线

　　在贪吃蛇足够长的情况下，苹果可能会在蛇身体包围的圈中，看上图，黄色表示头部，那么蛇就找不到路线了！

　　4.3 一味的最短路线吃东西，留下太多洞

　　我们看下这张图，红色的表示现在出现的苹果，橙色的表示吃完红色的苹果后，苹果可能出现的位置，如果我们简单的用最短路线去吃红色的，即无脑往左走，那么橙色的就在会出现在蛇的包围圈中，将来要吃这个就非常不利，要走很多步。
　　这个时候比较好的走法是下图：

　　尽可能的多绕，尽可能地把空白地方填完，而不是以最短路线去吃，要为将来打算。

　　5. 贪吃蛇的最佳无脑模式

　　一想到4.3的问题，我就觉得贪吃蛇AI是非常难的一个问题，难道还是设及到“一笔画问题”，那就太难了。不过还好，玩了这么多局的贪吃蛇，我发现一个无脑模式，可以填满整个游戏区域。见下图：

　　就是在最后一行空出来，留做逃生的路线，然后像弹簧一样无脑向右推进，吃完后，从底部绕回最左边，继续这样的策略，直到填满整个游戏区域。不知道读者懂不懂这样的策略。

　　6.开始讲我的贪吃蛇AI实现了

　　一定要先理解上面的东西，才好继续往下看。我们知道追着尾巴跑，蛇就不会死，所以我们以最短路线去吃苹果时，要给自己留条后路，策略1.如果吃完苹果还可以找到到自己尾巴路线的话，才去吃苹果。
　　下面给出的是伪代码：

　　策略2.如果找不到吃苹果路线或者吃完苹果后，会发生找不到自己尾巴路线的话，那么就在头部的周围找一个格子，这个格子要满足两个条件，条件1，走完这个格子要能找到到尾巴的路线，条件2，这个格子到苹果的距离是最远的。
　　策略2中的条件1，我们肯定是能找的到的，因为我们的AI的基础都是基于策略1。
　　策略2的伪代码如下：