WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
贪吃蛇自动寻路算法的研究
贪吃蛇自动寻路算法的研究

碎碎念

为了能够随心所欲的测试贪吃蛇的寻路算法,我先造了一个轮子。它支持可视化界面、随机开始暂停重来、使用标准输入流与标准输出流与程序交互、同时将Debug信息输出到调试窗口。将轮子制造完之后,我自行脑补了几个看上去还算靠谱的算法:基于最短路的估价算法、基于随机的算法。

Github

Github:内有Java源代码、可执行程序、与样例程序。

Gluttonous Snake 模拟平台

https://blog.wnjxyk.cn/wp-content/uploads/2018/12/013ddebb-0cea-4b0c-b09e-a4600fcfa6fe.png

界面介绍

左侧是游戏模拟界面,食物是一个黄色的方块,蛇由若干个渐变颜色的方块组成。

右侧是从上往下分别是:控制按钮、游戏信息、速度控制(或暂停)、控制程序选择、Debug窗口

支持功能

  1. 可视化界面与简单操作界面

  2. 支持加速、减速、暂停贪吃蛇

  3. 使用标准输入流、输出流、错误流与可执行文件进行交互,不限制算法实现语言,

  4. 自动输出交互信息,同时将错误流输出到Debug窗口,Debug简单

输入格式

第一行有两个整数nk,分别表示贪吃蛇游戏地图大小与贪吃蛇的长度。

接下来的k行,这k行中的第i行里会有一组坐标 x_i, y_i ,表示贪吃蛇的第i节的位置。

最后一行也是一组坐标x_{fodd}, y_{food}表示食物的位置。

接下来这组样例输入文件,可以帮助你进一步理解输入格式。


5 3 2 3 1 3 1 2 1 1

这组样例表示,这是一个5 \times 5的地图,贪吃蛇的长度为3,食物的位置在(1, 1)

输出格式

输出文件之需要一行,之需要输出一个整数k \in [0, 4)代表接下来贪吃蛇前进的方向(注意,不合法,程序会自动忽略这个指令)

0、1、2、3分别对应上、下、左、右,接下来的这个坐标变化数组可以帮助你理解其中的对应关系(dx代表x的变化量、dy代表y的变化量,另外在图中x从上向下代表行、y从左到右代表列)


public static final int dx[] = {-1, 1, 0, 0}; public static final int dy[] = {0, 0, -1, 1};

使用小贴士

  1. 对于C/C++选手,可以使用scanfcin直接输入数据,使用printfcout返回结果,使用cerr来输出错误信息,注意使用fflush来将输出缓冲区清空,其他语言类似。
  2. 输出数据的末尾必须有一个空行,也就是说必须以endl\n这类的换行符结束。
  3. 你可能需要一个Java Runtime Environment来运行这个程序。
  4. 一开始运行的时候窗体尺寸可能不太合适,拉伸调整后,下一次程序会记住它。

自动寻路算法

我自行脑补了两种自动寻路算法,它们都基于一个基本准则:当能找到食物且吃完食物依旧能找到自己的尾巴的时候,去寻找食物,否则我们去寻找尾巴。基于这个准则,很可能会出现一些死循环的情况,这时候就需要用一些其他方法来处理,这里我使用了两种方法,第一种是对路径进行估价然后选择最优的走,另一种是在行走的时候随机做一些决策来跳出循环。

基于路径估价的方法

算法的流程是这个样子的:
1. 将头位置设置为起点,蛇的身体(除尾巴外)作为障碍物,使用BFS判断是否可以到达食物,并记录第一步怎么走,假设方向为d_{food}
2. 如果吃掉食物就能胜利且能吃掉食物,就输出d_{food},然后结束程序。
3. 模拟蛇吃到食物的状态,再使用BFS判定那个时候蛇能不能追到自己的尾巴,如果能追到自己的尾巴,就输出d_{food}并结束程序。
4. 使用二分+SPFA,求一条从头到尾的距离食物平均曼哈顿距离最大的路径,同时在SPFA的时候设置额外积分,让这条路径倾向于在头前面积累一定量的空格,输出这条路径的第一步,程序结束。

简单的来说这个程序的思路就是如果吃食物安全就吃食物,否则就移动尽量让食物周围的空间宽裕些,同时让蛇头前面有一定数量的可分配空间。

这种方法效率很高,基本上3000步就可以吃到98%以上,但是对于结束局面很容易陷入僵局而死循环。吃的效率高但是不容易全吃完。

https://blog.wnjxyk.cn/wp-content/uploads/2018/12/Ctrl_Compress.gif

基于随机决策的方法

枚举四个方向,分别为模拟向这个方向走一步的状态,然后获得以下参数:
1. 是否能到尾巴
2. 是否能到食物
3. 图中联通块的数量
4. 蛇身体距离食物的曼哈顿距离之和
然后按照以下规则,优先级从高到低对这四个方向进行排序:
1. 如果再吃一个就要胜利了,或者再吃两个就要胜利了且食物与空格子连在一起,那么能吃到食物的方向排在前面。
2. 能找到尾巴的方向排在前面
3. 能吃到食物的方向排在前面
4. 如果剩余格子不足地图大小的10%:
* 先比较联通块数量少的放在前面
* 10%的概率让距离食物曼哈顿距离最大的方案放在前面,否则让蛇头距离食物路径短的方案在前面
5. 如果剩余格子多余地图大小的10%:
* 先比较联通块数量少的放在前面
* 10%的概率让距离食物曼哈顿距离最大的方案放在前面,否则让蛇头距离食物路径短的方案在前面
最后输出排名第一的方案。

基本思路就是,优先找尾巴,找得到尾巴找食物,找得到食物的时候,如果快结束了就让联通卡尽可能的少,否则10%概率给食物周围腾空间,90%概率去吃食物。

这种方法,因为包含随机,所以一般要7000步左右才能胜利,也是因为随机的存在所以可以跳出死循环,对最终局面能很好处理,全吃完的效率高。

https://blog.wnjxyk.cn/wp-content/uploads/2018/12/RandCtrl_Compress.gif

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

发表评论

textsms
account_circle
email

WNJXYKのBlog

贪吃蛇自动寻路算法的研究
碎碎念 为了能够随心所欲的测试贪吃蛇的寻路算法,我先造了一个轮子。它支持可视化界面、随机开始暂停重来、使用标准输入流与标准输出流与程序交互、同时将Debug信息输出到调试窗口。将…
扫描二维码继续阅读
2018-12-05
<--! http2https -->