110418w200wom1nm1n1woz.jpg

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

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

110253tuzhckrhpxhpphyr.jpg

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

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

110253mjdsvmskpmk3hmkj.jpg

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

  3.寻路算法之A Star

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

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

  4.1会进入死胡同

110253erjrs2retmjz7iuh.jpg

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

  4.2 找不到路线

110253sf33f3uzj0ssfvef.jpg

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

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

1102543c8w3tv6sv3g3ziy.jpg

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

110254w17azakyu6dqkqq6.jpg

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

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

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

110254b1ryc0yye0piyhb1.jpg

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

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

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

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

  注意下策略2中的条件2,我们没有用什么高深的算法,我们仅仅是把蛇往一个到苹果最远的格子移动,运行起我们的贪吃蛇,我们发现贪吃蛇AI可以工作了!!这个就有点哲学的味道了,看似在往远离目标的方向上行动,没有想到蛇刚好自己在绕了,绕掉了大部分的身体后,就可以用策略1找到路线了。
  看了好几遍自己贪吃蛇AI的移动,不可避免的会有4.3提到的这个问题,后期留下太多洞了,贪吃蛇要追随自己尾巴,移动很久才能吃到一个苹果,我们知道有标题5 提到的无脑模式,我们在想,要不后期就不要以最短路线去吃苹果,而是无脑绕,来吃,这样反而会快些!
  怎样才能产生无脑绕的效果呢?我们发现策略2中的条件2会产生这样的效果,在后期,我们就走离苹果最远的格子且这个格子能有到达尾巴的路线,我们发现这样走无意中就会产生这样的无脑绕效果!有点像圆。圆心就是目标,最终还算会不断地接近目标的!
  这样算是贪吃蛇游戏的后期呢?我这里就简单如果蛇的长度等于整个游戏格子数量的一半,就算到后期了。

  7.最终贪吃蛇AI效果图:

110301sa1r22lbisq7brlb.jpg

  8.贪吃蛇AI在线试玩地址

  用Cocos2d HTML5实现的。
  http://www.waitingfy.com/html5/snake
  http://www.waitingfy.com/archives/951

  9.贪吃蛇snake html5 下载

  http://www.waitingfy.com/?attachment_id=962
  github:  https://github.com/waitingfy/snake