如何用Python写一个贪吃蛇AI

前言

这两天在 上看到一张让人涨姿势的图片，图片中展示的是贪吃蛇游戏， 估计大部分人都玩过。但如果仅仅是贪吃蛇游戏，那么它就没有什么让人涨姿势的地方了。 问题的关键在于，图片中的贪吃蛇真的很贪吃XD，它把矩形中出现的食物吃了个遍， 然后华丽丽地把整个矩形填满，真心是看得赏心悦目。作为一个CSer， 第一个想到的是，这东西是写程序实现的(因为，一般人干不出这事。 果断是要让程序来干的)第二个想到的是，写程序该如何实现，该用什么算法然开始想了，就开始做。Talk is cheap，show me the code。

开始之前，让我们再欣赏一下那只让人涨姿势的贪吃蛇吧：( 如果下面的动态图片浏览效果不佳的话，可以右键保存下来查看)

为了尽量保持简单，我用的是curses模块，直接在终端进行绘图。 从上面的动态图片可以看出，每次都单纯地使用BFS，最终有一天， 贪吃蛇会因为这种不顾后果的短视行为而陷入困境。 而且，即使到了那个时候，它也只会BFS一种策略， 导致因为当前看不到目标(食物)，认为自己这辈子就这样了，破罐子破摔， 最终停在它人生中的某一个点，不再前进。(我好爱讲哲理XD)

BFS+Wander

上一节的简单版本跑起来后，我们认识到，只教贪吃蛇一种策略是不行的。 它这么笨一条蛇，你不多教它一点，它分分钟就会挂掉的。 所以，我写了个Wander函数，顾名思义，当贪吃蛇陷入困境后， 就别让它再BFS了，而是让它随便四处走走，散散心，思考一下人生什么的。 这个就好比你困惑迷茫的时候还去工作，效率不佳不说，还可能阻碍你走出困境； 相反，这时候你如果放下手中的工作，停下来，出去旅个游什么的。回来时， 说不定就豁然开朗，土地平旷，屋舍俨然了。

Wander函数怎么写都行，但是肯定有优劣之分。我写了两个版本，一个是在可行的范围内， 朝随机方向走随机步。也就是说，蛇每次运动的方向是随机出来的， 总共运动的步数也是随机的。Wander完之后，再去BFS一下，看能否吃到食物， 如果可以那就皆大欢喜了。如果不行，说明思考人生的时间还不够，再Wander一下。 这样过程不断地循环进行。可是就像“随机过程随机过”一样，你“随机Wander就随机挂”。 会Wander的蛇确实能多走好多步。可是有一天，它就会把自己给随机到一条死路上了。 陷入困境还可以Wander，进入死胡同，那可没有回滚机制。所以， 第二个版本的Wander函数，我就让贪吃蛇贪到底。在BFS无解后， 告诉蛇一个步数step(随机产生step)，让它在空白区域以S形运动step步。 这回运动方向就不随机了，而是有组织有纪律地运动。先看图，然后再说说它的问题：

矩形大小10*20，除去外面的边框，也就是8*18。Linux下录完屏再转成GIF格式的图片， 优化前40多M，真心是没法和Windows的比。用下面的命令优化时， 有一种系统在用生命做优化的感觉：

最后还是拿到Windows下用AE，三下五除二用图片序列合成的动态图片 (记得要在format options里选looping，不然图片是不会循环播放的)

Last but not least

如果对源代码感兴趣，请戳以下的链接： Code goes here

以上的代码仍然可以继续改进(现在加注释不到300行，优化一下可以更少)， 也可用pygame或是pyglet库把界面做得更加漂亮，Enjoy！

文章知识点与官方知识档案匹配，可进一步学习相关知识Python入门技能树首页概览215153 人正在系统学习中