吃满全图？实现全自动贪吃蛇的一种可能（基于Python Turtle）
【本文富含GIF，请作好准备】
刚学会做贪吃蛇游戏时，B站就向我推了这个：
细腻的操作、精准的计算，每一步穿插避让都如此完美，想必是由程序控制。
也不知哪来的勇气，我决定自己学着写一个……
v0.0：广度优先搜索实现寻路
查阅了几个自动贪吃蛇的实现思路后，无一例外提及了“搜索算法”，所以第一天的任务确定：学会一种能用于贪吃蛇寻路的“搜索算法”！
利用B站知识区丰富的资源，我首先使用广度优先搜索算法（BFS）实现了寻路（其实是只学了这一种后就怠惰了），当天成果如下：
v0.1：生搬硬套BFS的笨蛇
在真正开始前，有必要明确一下贪吃蛇游戏的规则：
1. 蛇分为多节，每吃到一次食物增加一节
2. 蛇头可以向前、向左、向右行进，后面的蛇身跟随之
3. 蛇头行进方向上撞到围墙或自身身体，即为游戏失败；遇到食物，则身体加一节
画一个10*10的地图，把起点和终点改为蛇头和食物，套用BFS算法，即实现如下效果：
贪吃蛇动起来了！然而，当身体变长，它很快就挂了。可见，无尽的贪婪终将把自己逼上绝路
进行几次实验后，我发现了贪吃蛇的两大致死原因：
1. 蛇身过长，将地图分为至少两个封闭图形，蛇头与食物间无通路（如下图a，我愿称这种情况为“生存状态”）
2. 食物出现在了刁钻的位置，蛇吃到后将走入死路（如下图b，我称之为“迷茫状态”）
#能吃到食物且吃到食物后，还能追到蛇尾的状态，我称之为“快乐状态” [手动滑稽]
于是有两个对应的解决策略：
1. 因为蛇每往前走一格，蛇尾就会空一格出来，所以蛇头跟着蛇尾方向走肯定不会死；
2. 如果食物出现在死路里，就不应该去吃它。但如何判断？其实，“食物在死路里”的一个充分条件是“吃了这块食物后，蛇头与蛇尾没有通路”。所以，要让蛇学会“三思而后行”，在奔向食物前想想，吃了这块“毒苹果”后是不是再走向蛇尾，如果不能，就只好去追赶蛇尾，以伺良机（指进入能够安全吃食的“快乐状态”）。
v0.2 学会了“追尾”的憨憨蛇
增加了上述两个策略后，贪吃蛇进入“生存状态”和“迷茫状态”后仍能继续行进并有效地生长，寿命明显提高，甚至在进行了50余次实验后表演了一波“吃满全图”：
只简单增加了一次BFS寻找蛇头到蛇尾的通路，就取得如此明显的效果，简直是把我明天的欧气都耗尽了。其实这时我才开始遭遇贪吃蛇真正的难题。
学会追蛇尾的贪吃蛇，再也不会轻易地死掉，但它大部分时候会进入某种死循环，像这样：
还有特别气人的这样……
也就是当食物出现在某个位置时，蛇再也找不到安全的路线去吃它，而自身形成了一个曲折的回路，无法破解。
冥思苦想+翻找博客之后，我稍稍改变了“生存状态”或“迷茫状态”下蛇的行进策略……
v0.3 比较聪明的成年蛇
“你已经是一只成年蛇了，要学会自己找出路。”
如果蛇总是以最短路径向食物靠近，蛇身不可能全部贴合，势必产生许多小洞，留下死循环的隐患。让我们回到本文最开头的GIF，不难发现那条贪吃蛇似乎从一开始就没有走最短路径，而是常常贴着自身走，并且绕各种S形弯，保证了行进的可持续。
这启发我改变“生存状态”或“迷茫状态”下蛇的行进策略：蛇应该远离食物，直至回到“快乐状态”。进入“生存状态”或“迷茫状态”后，需要先寻找蛇头周边的空位，并选择一个走过去。其中有两个要点：
1. 蛇走进这个位置后，蛇头与蛇尾间仍要有通路；
2. 在所有符合条件1的空位中，选择离食物最远的一个。
利用这两个条件，贪吃蛇就会自发地贴着自身走并绕一些S弯了。
以上图为例，蛇处于“生存状态”。蛇头左边是墙，不可走；走右边和前方都可到达蛇尾，但前方离食物更远，故向前走。
现在，重新捋一下思路：
最终效果如下：
实验发现，吃满全屏的概率似乎已经从1/50上升到了60%以上，算是有一定的提高了。
而最后一个未解决的问题如下：
仍然是死循环的问题，常常在剩余1格未填满时陷入死循环，极少数时候还出现过剩余3格未填满的情况。
写在最后
对于最后的死循环，既有的改进思路是：在蛇身达到一定长度时，就开始S形绕弯，预防“最后几个洞”的出现。
但应该在蛇身达到多少时改换策略呢？填满70%的地图时？50%？或是蛇达到能绕地图一周的长度时就要开始绕S形，就像本文最开头的GIF那样？我暂时没有能力探索下去……
如果只是为了做到“吃满全图”，其实早已有完美的解决方案，即不停地S形绕弯（用不自交的封闭曲线填满地图），就像这样：
难道应该基于这种最“无脑”的S形吃法，去改进它的效率？
我猜想这个视频中的蛇正是如此，因此前期显得“有点不太聪明的亚子”。简单粗暴，但保证有效：2分钟看完贪吃蛇全集
S形吃法并非唯一保稳的操作，参见这个视频中贪吃蛇的华丽走位：人工智能AI挑战贪吃蛇，这就是人工智能的艺术！
还有一种十分接近人类的走法：贪吃蛇理论最高分
这是一个13*8的地图，走法直接了当，前期转向很少，后期也是绕最小的S形弯。如果说这是真人操作我也愿意相信。
最后的一点点想法都放在这里了。有朝一日做出能100%成功吃满全图的贪吃蛇，再来更新v1.0吧……
思路主要参考
https://blog.csdn.net/fox64194167/article/details/19965069
您竟然看到了这里……悄悄引个流吧 [doge]
