之前在微博上看到一张图。

这张图一看就知道是程序控制的,因为普通人没这么无聊,而且图片中蛇的运动很高瞻远瞩,可以判断肯定不是单纯的搜索算法。正好最近复习数据结构,那就尝试也实现一个人工智能来玩贪吃蛇吧。

<>语言选择

人生苦短,我用Python。

<>在此之前

首先,我们得先做一个能玩的贪吃蛇游戏, 并沉迷其中。

游戏思路和代码很简单,在一个矩形里不断出现随机位置的食物,让蛇在矩形内不断吃食物就行了。用代码实现就是用数组表示地图和坐标,再用一个二维数组储存一格格蛇身的位置。循环监听键盘事件,按下按键后就转向,遍历所有的对象,把他们画出来。

这样我们就做出来一个贪吃蛇游戏(滑稽)。那么问题来了,既然是人工智能,那就肯定不能是人来操作,对于机器而言,这个游戏的终极目标就是吃食物。给定一个起点(蛇头)和一个终点(食物)找到一条可行的路径到达,在不考虑其他条件的时候,这个问题就是蛇头到食物的曼哈顿距离。OK,那我们就开始实现这个最简单的版本。

绿线表示欧氏距离,红线为曼哈顿距离,蓝线和黄线代表等价的曼哈顿距离

<>初级版本

为了找到蛇头到食物的路径,我们必须在游戏地图上进行搜索。搜索路径的算法有很多种,比如DFS,BFS和A*。这里我们遵循Python之禅:“对于一个特定的问题,只要有一种最好的方法来解决就好了”,于是我们使用BFS算法(广度优先搜索,其实是我只会BFS)。为了编程的方便,我借鉴了Hawstein的思路,用一维数组来表示二维的地图,上下移动时只需要+/-width即可。

BFS查寻最短路径
首先把食物的坐标放入队列,只要队列非空就把队头出队,然后把它周围的4个点放入队列,不断地循环操作,
直到覆盖整个地图。在遍历过程中应该注意:1.蛇的身体和墙不能访问。2.为了提高效率,有重合的格子如果被访问过就不用再访问了。当整个循环结束后,除了蛇的身体,所有的地图网格中的数字等于从它到食物的曼哈顿间距。之后就从蛇头开始,沿着最短路径运行就行了。

在小蛇欢快的跑了一段时间后,突然程序报错了,最终画面定格为这样。

蓝色是蛇头,绿色是蛇尾,红色是食物

我们的蛇陷入了人生低谷,由于每次都是沿着BFS算出来的最短路径走,笨蛇终于把自己给笨死了,这时BFS查寻不到可行的路径,程序会直接结束。所以,在实际情况下,如果一味沿着最短的曼哈顿距离运行,很容易让自己陷入无路可走的情况。这个时候我们就需要更好的算法来规划运行路径。

<>没事走两步版本

上面那张图我们可以看出,蛇并不是完全没有出路,只需要走几格就能再次查寻到路径。所以在当前情况无解时,我们可以让蛇随便找个能跑的地方走一步,走完后再BFS查寻,如果还是找不到就继续走,反复循环。

这样我们的小蛇就能多跑一会,可惜最终仍难逃死亡厄运。

BFS+没事走两步

这张图上,虽然确实能直接吃到食物,但是吃完后蛇头被蛇身包住,进了死胡同。也就是说,没事走两步并不能拯救蛇,因为这家伙看到食物就奋不顾身的冲过去了,根本没有考虑后果,所以为了让它能跑的更欢快,必须要更有远见。

<>提莫队长探路版本

在网上查阅了很多文章,发现大家对这个问题居然还有挺多的研究。总结了下搜集的方法,基本上分为两种:

在吃食物之前,派出一条虚拟的蛇去探探路,如果虚拟蛇吃完后是安全的,那就让真正的蛇去吃。

蛇头追着蛇尾走,在所有的路径中如果有一条路径能经过食物就选择这条路走。

对比两种思路,方法二虽然思路清晰过程少,但是由于路径很多(等价曼哈顿距离),不容易判断哪个是最优解。因此我们选择方法一。

俗话说“团战可以输,提莫必须死”。所以我们首先把这只提莫杀死,让它的灵魂替我们探路,这样就不用把它给画出来了。但是,对于方法一来说,怎么样的布局才算是安全的呢?解决办法还是得从我们最开始提到的那张铺满屏幕的GIF图片来找,在那张图里面,即使蛇已经很长了,蛇仍然能够风骚走位,而且是跟着蛇尾跑的,并且在能吃到食物的时候也没有马上跑过去,而是拉开足够的距离后才吃。我们之前写程序的时候,都是让蛇沿着最短的距离去吃食物,在刚开始还好,一旦蛇比较长,这个方法就会把蛇给害死。所以我们不一定非得偷懒去走最短的路,而是应该考虑如何高效利用剩余的游戏区域,沿着可持续发展,绿色环保的道路走下去,践行科学发展观,实现伟大复兴的中国梦……咳咳,说跑偏了。所以,安全的定义应该是,在吃完食物后,还应该能找到自己的尾巴。因此,我们的算法应当是这样的:

算法伪代码
最后我们来看看提莫队长版的蛇是怎么跑的吧。

把速度放慢点再看

可以看出,因为食物是随机生成的,所以蛇有可能吃不到,不一定能全部铺满地图。不知道为什么用Pygame渲染的时候,水平方向上出现了几个像素的偏差,如果有知道的大佬欢迎评论区解答。

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:[email protected]
QQ群:766591547
关注微信