私信python饕餮蛇，给你发源码和python学习教程。
开始之前，让我们再欣赏一下那只让人涨姿势的饕餮蛇吧：( 如果下面的动态图片浏览效果不佳的话，可以右键保存下来查看)
措辞选择
Life is short, use python! 以是，根本就没多想，直接上python。
最初版本
先让你的程序跑起来
首先，我们第一件要做的便是先不要去剖析这个问题。 你好歹先写个能运行起来的饕餮蛇游戏，然后再去想AI部分。这个该当很大略， c\c++也就百来行代码(如果我没记错的话。不弄繁芜界面，直接在掌握台下跑)， python就更大略了，去掉注释和空行，5、60行代码就搞定了。而且，最最关键的， 这个东西网上肯定写滥了，你没有必要重复造轮子， 去弄一份来按照你的意愿改造一下就行了。
大略版本
我以为直接写perfect版本不是什么好路子。由于perfect版本每每要考虑很多东西， 直接上来就写这个一样平常是bug百出的。以是， 一开始我的目标仅仅是让程序去掌握饕餮蛇运动，让它去吃食品，仅此而已。 现在让我们来陈述一下最初的问题：
在一个矩形中，每一时候有一个食品，饕餮蛇要在不撞到自己的条件下，找到一条路(未必要最优)，然后沿着这条路运行，去享用它的美食
我们先不去想蛇会越来越长这个事实，问题基本便是，给你一个出发点(蛇头)和一个终点( 食品)，要避开障碍物(蛇身)，从出发点找到一条可行路到达终点。 我们可以用的方法有：
BFSDFSA只要有选择，就先选择最大略的方案，我们现在的目标是要让程序先跑起来， 优化是后话。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键为止。
由于食品是随机涌现的，以是有可能涌现上面这种无解的布局。当然了， 你也可以得到圆满的结局，饕餮蛇把全体矩形都添补斥。
上面的末了一个问题，暴力法是否能得到最优序列。从上面的剖析看来， 可以得到，但不能担保一定得到。
末了，看看高瞻远瞩的蛇是怎么跑的吧：
矩形大小1020，撤除表面的边框，也便是818。Linux下录完屏再转成GIF格式的图片， 优化前40多M，至心是没法和Windows的比。用下面的命令优化时， 有一种系统在用生命做优化的觉得：
convert output.gif -fuzz 10% -layers Optimize optimised.gif
末了还是拿到Windows下用AE，三下五除二用图片序列合成的动态图片 (记得要在format options里选looping，不然图片是不会循环播放的)
私信python饕餮蛇，给你发源码和python学习教程。