如何用Python写一个蛇AI？

这两天在网上看到一张让人提高姿势的图片。图为吃蛇游戏，估计大部分人都玩过。但如果只是贪吃蛇的游戏，那就没什么好让人提高姿态的了。问题的关键是，图中的蛇真的很贪吃XD。它把长方形里的食物都吃光，然后漂亮地填满整个长方形，真的很赏心悦目。作为一个CSer，首先想到的是这个东西是通过写程序实现的(因为一般人做不到)。果断就是让程序去做。)第二个想法是，程序怎么写，应该用什么算法？既然已经开始思考了，那就开始做吧。因为空谈是廉价的，你得给我看代码。(跟老鼠叔叔学的)

开始之前，先来欣赏一下让人站起来的蛇:(以下动态图片如果无效，可以右击保存)

语言的选择

人生苦短，用python！于是，我根本没多想，直接上了python。

原著

让你的程序先运行。

首先，我们要做的第一件事是现在还不分析这个问题。至少先写个能跑的贪吃蛇游戏，再考虑AI部分。这个应该很简单，cc++才一百行代码(如果我没记错的话。没有复杂的界面，直接在控制台下运行)，python更简单。去掉注释和空行，5、60行代码就搞定了。而且，最重要的是，这个东西肯定是网上写的。不需要反复做轮子。随便拿个副本，按照自己的意愿改造就行了。

简单版本

我觉得直接写完美版不是个好办法。因为完美版往往要考虑很多东西，所以直接写这个一般都是满满的bug。所以，一开始，我的目标只是让程序控制蛇的运动，让它吃食物，仅此而已。现在我们来陈述一下最初的问题:

1

2

在一个长方形里，每时每刻都有一块食物，蛇应该不会撞到自己。

找到一条路(不一定是最好的)，沿着它跑，享受它的美味。

我们不要去想蛇会越来越长的事实。基本问题是给你一个起点(蛇头)和一个终点(食物)。避开障碍物(蛇身)，找到一条从起点到终点可行的路。我们可以使用以下方法:

BFS

深度优先搜索

A*

只要有选择，先选最简单的方案。我们现在的目标是让程序先运行起来，优化是另外一回事。所以，从BFS开始。我们先把蛇头的位置放在队列中，然后只要队列不空就把队头的位置出列，然后在队列中它的四个字段放四个点，不断循环，直到到达食物的位置。在这个过程中，需要注意几个点:1。已访问的点不再被访问。2.保存每个点的父节点(也就是每个位置去的地方，这样我们就能找出可行路径)。3.蛇身的位置和四壁都无法接近。

通过BFS找到食物后，就让蛇沿着可行的路径前进。这个简单的版本写好之后，蛇就可以开心地跑一会儿了。看图:(不流畅的感觉来自录屏软件@ @)

为了尽量简单，我使用curses模块直接在终端画图。从上面的动态图片可以看出，每次你简单地使用BFS，总有一天，蛇会因为这种不计后果的短视行为而陷入困境。而且，即使到了那个时候，也只会是BFS的一个策略，会因为目前看不到目标(食物)而导致认为这辈子也会这样，最终会停在它生命的某个点上，停止前进。(我爱讲哲学XD)

BFS+漫步

在运行了上一节的简单版本之后，我们意识到只教蛇一种策略是不够的。这条蛇真蠢。如果不多教它，它分分钟就死了。所以，我写了一个游走函数。顾名思义，当蛇遇到麻烦时，不要让它BFS，而是让它随便走走，放松一下，思考一下人生什么的。这就像你在迷茫困惑的时候去上班。效率低下不说，还可能阻碍你脱困；相反，这个时候，如果你放下工作，停下来，去旅行什么的。等我回来，也许我会豁然开朗，土地会变得平坦，房子也会变成这样。

Wander函数可以怎么写都行，但肯定是有利有弊的。我写了两个版本，一个是在可行的范围内，在随机的方向上采取随机的步骤。也就是说，蛇每次运动的方向是随机的，总运动的步数也是随机的。《流浪》结束后，再去一次BFS，看看能不能吃到美食。如果可以，大家都会开心。如果没有，说明没有足够的时间去思考人生。再试试流浪。这个过程不断循环。但就像“随机过程就是随机”一样，你“随机游走就是随机”。知道游走的蛇真的可以多走很多步。但总有一天，它会随机把自己送上绝路。也可以在遇到麻烦的时候游荡进死胡同，但是没有回滚机制。所以，第二版的游走功能，我让蛇贪婪到底。在BFS无解后，告诉蛇一个步数(随机产生的步数)，让它在空白区域做S形移动。这一次运动的方向不是随机的，而是有组织有纪律的。先看图，再谈它的问题:

是的，我终于死了。s形运动也是无法让蛇避免死亡的命运。蛇可以通过S形运动活得更久，但是因为它的策略:

1

2

三

四

五

虽然没有按下ESC键:

如果蛇和食物之间有一条路:

边走边吃东西。

否则:

徘徊一会儿

问题是蛇在自己和食物之间找到了一条路，所以它二话不说就去吃食物了。没有考虑到你去吃了食物之后形成的局面(蛇形布局)可能会彻底让你死掉。(比如进入自己蛇身围成的封闭小空间)

所以，为了让蛇活得更久，它必须更有前瞻性

前瞻性版本

我们现在有了相对低端的版本，对问题的理解也稍微深入了一些。现在我们可以做一些仔细严谨的分析了。首先列出一些问题:(像头脑风暴一样，把想到的写下来就行)

当蛇与食物之间有路径时，不宜直接进食。那么我们该怎么办呢？

如果蛇去吃食物后布局是安全的，那它是不是应该就这么吃了？(这样最好吗？)

如何定义布局是否安全？

如果蛇和食物之间没有路径呢？

最短路径是最优的吗？(这显然不是)

那么，如果布局是安全的，那么最短路径是最优的吗？

除了最短的路，我们还能怎么走？s形？最长的？

如何应对蛇越长越长的问题？

食物随机出现，有没有可能出现无解的布局？

暴力破解能得到最优序列吗？让蛇吃尽可能多的食物。

只要你想想，问题还真不少。这时候我们就拿过程导向的思维，拿上面的问题来梳理一下思路。一开始蛇很短(初始长度是1)。它看到了一个食物，并使用BFS获得到达矩形中每个位置的食物的最短路径长度。没有蛇挡着，就是曼哈顿距离。然后，我要判断这条蛇去是否安全。所以我需要一条虚拟的蛇，负责每次探路。如果安全了，就让真的蛇跑吧。当然不会画虚拟蛇，它只负责模拟寻路。那么，如何定义一个布局是安全的呢？如果你好好看看文章开头动态图中蛇的迷人位置，你会发现，即使最后蛇已经很长了，它还是走出了一条路，没有任何问题。而且，后面还跟着一条蛇！嗯，这个其实不难解释。蛇在移动的过程中消耗身体，尾巴后面总会出现新的空间。蛇短的时候无所谓。等蛇长大了，你会发现，要想活下来，基本上可以追着蛇尾跑。在追蛇尾的过程中，考虑一下能不能安全吃到食物。(下图是某次BFS后得到的一个布局，其中0代表食物，数字代表位置到食物的距离，+号代表蛇头，*号代表蛇身，-号代表蛇尾，#号代表空间，#号外面代表围栏。)

1

2

三

四

五

六

七

# # # # # # #

# 0 1 2 3 4 #

# 1 2 3 # 5 #

# 2 3 4 - 6 #

# 3 + * * 7 #

# 4 5 6 7 8 #

# # # # # # #

经过以上分析，我们可以把布局是否安全定义为蛇是否能顺着蛇尾走，也就是蛇吃完食物后，蛇头和蛇尾之间是否有路径。如果有，我觉得是安全的。

好吧，继续。真蛇派虚拟蛇探路后，发现吃了食物后的布局是安全的。然后，真正的蛇直接走向食物。等等，这是个好策略吗？不一定。因为蛇每走一步，布局都会改变。布局的改变意味着可能有更好的解决方案。比如因为消耗了蛇的尾巴，不得不绕道去吃的食物突然出现在蛇的面前。因此，真蛇走一步后，最好再做一次BFS。然后如上做一个安全判断，再去。

接下来，我们来思考一下。如果蛇和食物之间没有路径呢？实际上，做法上面已经提到过了，跟着蛇尾走。只要蛇和食物之间没有路径，蛇总是跟着蛇的尾巴走。类似地，因为布局会随着每一步而改变，所以BFS会随着每一步重做以得到最新的布局。

嗯，问题又来了。如果蛇和食物之间没有路径，蛇和蛇的尾巴之间也没有路径怎么办？没办法，就选一条可行的路吧。还是一个道理，走一步看一步，更新布局，然后判断蛇和食物之间是否有安全的路径；如果没有，蛇头和蛇头之间是否有路径；还没有。再走一步可行的。

上面列出的几个问题涉及到蛇的行走策略。一般来说，我们每次都会让蛇走最短的路。这是蛇吃食物的时候，但是蛇在追尾巴的时候不能这么想。我们希望的是，在追蛇头的过程中，蛇头越慢越好。这样可以在蛇头和蛇头之间腾出更多的空间，可以开发更多的空间。所以蛇的行走策略主要分为两种:

1

2

1.当目标是食物时，走最短的路。

2.当目标是蛇尾时，选择最长的路径。

第三种情况呢？在食物和蛇尾之间没有路径的情况下，这一次只是走可行的一步，最短最长的都关系不大。至于人为的让蛇呈S形，我觉得这不是一个好的策略，它的问题在原版中已经分析过了。(当然，除非你想用最无懈可击的版本，那就是完全无视食物，让蛇直扑S，然后在墙边留下一条过道。就这样，蛇总能完美的吃掉所有的食物，然后占据整个空间，但是很无聊。没有任何意义)

还有上面提到的一个问题:因为食物随机出现，有没有可能会无解？答案是:可以。我运行了程序，然后将每一个布局输出到日志中，发现会有这样的情况:

1

2

三

四

五

六

七

# # # # # # #

# * * * * * #

# * * - 0 * #

# * * # + * #

# * * * * * #

# * * * * * #

# # # # # # #

其中，+是蛇头，-是蛇尾，*是蛇身，0是食物，#代表空间，#代表外面的墙。这样的布局，食物已经在蛇头面前了，但是还能吃吗？不能！因为蛇头吃完食物后会在长度上加1，0的位置会被填上，布局就变成了:

1

2

三

四

五

六

七

# # # # # # #

# * * * * * #

# * * - + * #

# * * # * * #

# * * * * * #

# * * * * * #

# # # # # # #

此时，由于蛇的长度加上1，蛇的尾巴没有动，但蛇头被自己围住，挂了起来。然而，我们仍然有一个空白网格#未填充。按照我们之前教蛇的策略，面对这种情况，蛇头只会一直追着蛇头跑。每当它有了有食物的路径，就会让虚拟蛇再跑一次，发现新的布局不安全，就不会吃食物，而是选择继续追着蛇头跑。然后它就一直跑，一直跑。无限循环，直到你按下ESC键。

因为食物是随机出现的，所以有可能出现上面的布局无解。当然，你也可以得到一个圆满的结局。这条蛇填满了整个矩形。

上面最后一个问题是暴力法能否得到最优序列。从上面的分析来看，可以得到，但不能保证一定会得到。

最后，我们来看看远视蛇是怎么跑的:

矩形尺寸为10*20，不包括外边框，为8*18。在Linux下录完屏再转换成GIF格式图片，优化了前40 m，真的没法和Windows比。当使用下面的命令进行优化时，感觉系统正在用生命进行优化:

壳

1

convert output . gif-fuzz 10%-层优化优化. gif

最后得到了AE合成的动态图片，三下五除二，Windows下的图片序列(记得在格式选项中选择循环播放，否则图片不会循环播放)。

最后但并不是最不重要的

如果对源代码感兴趣，请戳以下链接:？代码在这里

此外，本文中的snake程序使用curses模块，该模块默认安装在类Unix系统中。使用Windows的童鞋需要安装这个模块发送到地址:？如果你需要诅咒，请戳我

上面的代码还可以改进(现在注释不到300行，可以优化的更少)，界面也可以通过pygame或者pyglet库做的更漂亮。尽情享受吧！