作者：Hawstein
出处：http://hawstein.com/posts/snake-ai.html
声明：本文采用以下协议进行授权： 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0，转载请注明作者及出处。
前言
这两天在网上看到一张让人涨姿势的图片，图片中展示的是贪吃蛇游戏， 估计大部分人都玩过。但如果仅仅是贪吃蛇游戏，那么它就没有什么让人涨姿势的地方了。 问题的关键在于，图片中的贪吃蛇真的很贪吃XD，它把矩形中出现的食物吃了个遍， 然后华丽丽地把整个矩形填满，真心是看得赏心悦目。作为一个CSer， 第一个想到的是，这东西是写程序实现的(因为，一般人干不出这事。 果断是要让程序来干的)第二个想到的是，写程序该如何实现，该用什么算法？ 既然开始想了，就开始做。因为Talk is cheap，要show me the code才行。 (从耗子叔那学来的)
开始之前，让我们再欣赏一下那只让人涨姿势的贪吃蛇吧：( 如果下面的动态图片浏览效果不佳的话，可以右键保存下来查看)
[attach]12743[/attach]
语言选择
Life is short, use python! 所以，根本就没多想，直接上python。
最初版本
先让你的程序跑起来
首先，我们第一件要做的就是先不要去分析这个问题。 你好歹先写个能运行起来的贪吃蛇游戏，然后再去想AI部分。这个应该很简单， c\c++也就百来行代码(如果我没记错的话。不弄复杂界面，直接在控制台下跑)， python就更简单了，去掉注释和空行，5、60行代码就搞定了。而且，最最关键的， 这个东西网上肯定写滥了，你没有必要重复造轮子， 去弄一份来按照你的意愿改造一下就行了。
简单版本
我觉得直接写perfect版本不是什么好路子。因为perfect版本往往要考虑很多东西， 直接上来就写这个一般是bug百出的。所以， 一开始我的目标仅仅是让程序去控制贪吃蛇运动，让它去吃食物，仅此而已。 现在让我们来陈述一下最初的问题：
在一个矩形中，每一时刻有一个食物，贪吃蛇要在不撞到自己的条件下，
找到一条路(未必要最优)，然后沿着这条路运行，去享用它的美食
我们先不去想蛇会越来越长这个事实，问题基本就是，给你一个起点(蛇头)和一个终点( 食物)，要避开障碍物(蛇身)，从起点找到一条可行路到达终点。 我们可以用的方法有：
BFS
DFS
A*
只要有选择，就先选择最简单的方案，我们现在的目标是要让程序先跑起来， 优化是后话。so，从BFS开始。我们最初将蛇头位置放入队列，然后只要队列非空， 就将队头位置出队，然后把它四领域内的4个点放入队列，不断地循环操作， 直到到达食物的位置。这个过程中，我们需要注意几点：1.访问过的点不再访问。 2.保存每个点的父结点(即每个位置是从哪个位置走到它的， 这样我们才能把可行路径找出来)。3.蛇身所在位置和四面墙不可访问。
通过BFS找到食物后，只需要让蛇沿着可行路径运动即可。这个简单版本写完后， 贪吃蛇就可以很欢快地运行一段时间了。看图吧：(不流畅的感觉来自录屏软件＠_＠)
为了尽量保持简单，我用的是curses模块，直接在终端进行绘图。 从上面的动态图片可以看出，每次都单纯地使用BFS，最终有一天， 贪吃蛇会因为这种不顾后果的短视行为而陷入困境。 而且，即使到了那个时候，它也只会BFS一种策略， 导致因为当前看不到目标(食物)，认为自己这辈子就这样了，破罐子破摔， 最终停在它人生中的某一个点，不再前进。(我好爱讲哲理XD)
BFS+Wander
上一节的简单版本跑起来后，我们认识到，只教贪吃蛇一种策略是不行的。 它这么笨一条蛇，你不多教它一点，它分分钟就会挂掉的。 所以，我写了个Wander函数，顾名思义，当贪吃蛇陷入困境后， 就别让它再BFS了，而是让它随便四处走走，散散心，思考一下人生什么的。 这个就好比你困惑迷茫的时候还去工作，效率不佳不说，还可能阻碍你走出困境； 相反，这时候你如果放下手中的工作，停下来，出去旅个游什么的。回来时， 说不定就豁然开朗，土地平旷，屋舍俨然了。
Wander函数怎么写都行，但是肯定有优劣之分。我写了两个版本，一个是在可行的范围内， 朝随机方向走随机步。也就是说，蛇每次运动的方向是随机出来的， 总共运动的步数也是随机的。Wander完之后，再去BFS一下，看能否吃到食物， 如果可以那就皆大欢喜了。如果不行，说明思考人生的时间还不够，再Wander一下。 这样过程不断地循环进行。可是就像“随机过程随机过”一样，你“随机Wander就随机挂”。 会Wander的蛇确实能多走好多步。可是有一天，它就会把自己给随机到一条死路上了。 陷入困境还可以Wander，进入死胡同，那可没有回滚机制。所以， 第二个版本的Wander函数，我就让贪吃蛇贪到底。在BFS无解后， 告诉蛇一个步数step(随机产生step)，让它在空白区域以S形运动step步。 这回运动方向就不随机了，而是有组织有纪律地运动。先看图，然后再说说它的问题：
没错，最终还是挂掉了。S形运动也是无法让贪吃蛇避免死亡的命运。 贪吃蛇可以靠S形运动多存活一段时间，可是由于它的策略是：- while 没有按下ESC键:
- if 蛇与食物间有路径:
- 走起，吃食物去
- else:
- Wander一段时间
问题就出在蛇发现它自己和食物间有路径，就二话不说跑去吃食物了。 它没有考虑到，你这一去把食物给吃了后形成的局势(蛇身布局)， 完全就可能让你挂掉。(比如进入了一个自己蛇身围起来的封闭小空间)
so，为了能让蛇活得久一些，它还要更高瞻远瞩才行。
高瞻远瞩版本
我们现在已经有了一个比较低端的版本，而且对问题的认识也稍微深入了一些。 现在可以进行一些比较慎密和严谨的分析了。首先，让我们罗列一些问题： (像头脑风暴那样，想到什么就写下来即可)
蛇和食物间有路径直接就去吃，不可取。那该怎么办？
如果蛇去吃食物后，布局是安全的，是否就直接去吃？(这样最优吗？)
怎样定义布局是否安全？
蛇和食物之间如果没有路径，怎么办？
最短路径是否最优？(这个明显不是了)
那么，如果布局安全的情况下，最短路径是否最优？
除了最短路径，我们还可以怎么走？S形？最长？
怎么应对蛇身越来越长这个问题？
食物是随机出现的，有没可能出现无解的布局？
暴力法(brute force)能否得到最优序列？(让贪吃蛇尽可能地多吃食物)
只要去想，问题还挺多的。这时让我们以面向过程的思想，带着上面的问题， 把思路理一理。一开始，蛇很短(初始化长度为1)，它看到了一个食物， 使用BFS得到矩形中每个位置到达食物的最短路径长度。在没有蛇身阻挡下， 就是曼哈顿距离。然后，我要先判断一下，贪吃蛇这一去是否安全。 所以我需要一条虚拟的蛇，它每次负责去探路。如果安全，才让真正的蛇去跑。 当然，虚拟的蛇是不会绘制出来的，它只负责模拟探路。那么， 怎么定义一个布局是安全的呢？ 如果你把文章开头那张动态图片中蛇的销魂走位好好的看一下， 会发现即使到最后蛇身已经很长了，它仍然没事一般地走出了一条路。而且， 是跟着蛇尾走的！嗯，这个其实不难解释，蛇在运动的过程中，消耗蛇身， 蛇尾后面总是不断地出现新的空间。蛇短的时候还无所谓，当蛇一长， 就会发现，要想活下来，基本就只能追着蛇尾跑了。在追着蛇尾跑的过程中， 再去考虑能否安全地吃到食物。(下图是某次BFS后，得到的一个布局， 0代表食物，数字代表该位置到达食物的距离，+号代表蛇头，*号代表蛇身， -号代表蛇尾，#号代表空格，外面的一圈#号代表围墙)- # # # # # # #
- # 0 1 2 3 4 #
- # 1 2 3 # 5 #
- # 2 3 4 - 6 #
- # 3 + * * 7 #
- # 4 5 6 7 8 #
- # # # # # # #
经过上面的分析，我们可以将布局是否安全定义为蛇是否可以跟着蛇尾运动， 也就是蛇吃完食物后，蛇头和蛇尾间是否存在路径，如果存在，我就认为是安全的。
OK，继续。真蛇派出虚拟蛇去探路后，发现吃完食物后的布局是安全的。那么， 真蛇就直奔食物了。等等，这样的策略好吗？未必。因为蛇每运动一步， 布局就变化一次。布局一变就意味着可能存在更优解。比如因为蛇尾的消耗， 原本需要绕路才能吃到的食物，突然就出现在蛇眼前了。所以，真蛇走一步后， 更好的做法是，重新做BFS。然后和上面一样进行安全判断，然后再走。
接下来我们来考虑一下，如果蛇和食物之间不存在路径怎么办？ 上文其实已经提到了做法了，跟着蛇尾走。只要蛇和食物间不存在路径， 蛇就一直跟着蛇尾走。同样的，由于每走一步布局就会改变， 所以每走一步就重新做BFS得到最新布局。
好了，问题又来了。如果蛇和食物间不存在路径且蛇和蛇尾间也不存在路径， 怎么办？这个我是没办法了，选一步可行的路径来走就是了。还是一个道理， 每次只走一步，更新布局，然后再判断蛇和食物间是否有安全路径； 没有的话，蛇头和蛇尾间是否存在路径；还没有，再挑一步可行的来走。
上面列的好几个问题里都涉及到蛇的行走策略，一般而言， 我们会让蛇每次都走最短路径。这是针对蛇去吃食物的时候， 可是蛇在追自己的尾巴的时候就不能这么考虑了。我们希望的是蛇头在追蛇尾的过程中， 尽可能地慢。这样蛇头和蛇尾间才能腾出更多的空间，空间多才有得发展。 所以蛇的行走策略主要分为两种：
1. 目标是食物时，走最短路径
2. 目标是蛇尾时，走最长路径
那第三种情况呢？与食物和蛇尾都没路径存在的情况下， 这个时候本来就只是挑一步可行的步子来走，最短最长关系都不大了。 至于人为地让蛇走S形，我觉得这不是什么好策略，最初版本中已经分析过它的问题了。 (当然，除非你想使用最最无懈可击的那个版本，就是完全不管食物， 让蛇一直走S，然后在墙边留下一条过道即可。这样一来， 蛇总是可以完美地把所有食物吃完，然后占满整个空间，可是就很boring了。 没有任何的意思)
上面还提到一个问题：因为食物是随机出现的，有没可能出现无解的局面？ 答案是：有。我运行了程序，然后把每一次布局都输出到log，发现会有这样的情况：- # # # # # # #
- # * * * * * #
- # * * - 0 * #
- # * * # + * #
- # * * * * * #
- # * * * * * #
- # # # # # # #
其中，+号是蛇头，-号是蛇尾，*号是蛇身，0是食物，#号代表空格，外面一圈# 号代表墙。这个布局上，食物已经在蛇头面前了，可是它能吃吗？不能！ 因为它吃完食物后，长度加1，蛇头就会把0的位置填上，布局就变成：- # # # # # # #
- # * * * * * #
- # * * - + * #
- # * * # * * #
- # * * * * * #
- # * * * * * #
- # # # # # # #
此时，由于蛇的长度加1，蛇尾没有动，而蛇头被自己围着，挂掉了。可是， 我们却还有一个空白的格子#没有填充。按照我们之前教给蛇的策略， 面对这种情况，蛇头就只会一直追着蛇尾跑，每当它和食物有路径时， 它让虚拟的蛇跑一遍发现，得到的新布局是不安全的，所以不会去吃食物， 而是选择继续追着蛇尾跑。然后它就这样一直跑，一直跑。死循环， 直到你按ESC键为止。
由于食物是随机出现的，所以有可能出现上面这种无解的布局。当然了， 你也可以得到完满的结局，贪吃蛇把整个矩形都填充满。
上面的最后一个问题，暴力法是否能得到最优序列。从上面的分析看来， 可以得到，但不能保证一定得到。
最后，看看高瞻远瞩的蛇是怎么跑的吧：
矩形大小10*20，除去外面的边框，也就是8*18。Linux下录完屏再转成GIF格式的图片， 优化前40多M，真心是没法和Windows的比。用下面的命令优化时， 有一种系统在用生命做优化的感觉：- convert output.gif -fuzz 10% -layers Optimize optimised.gif
最后还是拿到Windows下用AE，三下五除二用图片序列合成的动态图片 (记得要在format options里选looping，不然图片是不会循环播放的)
Last but not least
如果对源代码感兴趣，请戳以下的链接： Code goes here
另外，本文的贪吃蛇程序使用了curses模块， 类Unix系统都默认安装的，使用Windows的童鞋需要安装一下这个模块， 送上地址： 需要curses请戳我
以上的代码仍然可以继续改进(现在加注释不到300行，优化一下可以更少)， 也可用pygame或是pyglet库把界面做得更加漂亮，Enjoy！ | 
发表于 2013-5-2 09:52
| 
