Github寻宝 | 贪吃蛇游戏AI版,代码就得这么写!

本期案例是一个C++ 项目,同时也是经典小游戏——贪吃蛇的升级版。(该项目由Github用户stevennl贡献,英文原版可访问Github网站:https://github.com/stevennl/Snake)

Snake:贪吃蛇游戏 AI 版,该项目着重于AI算法,通过算法实现让小蛇通过吃豆,最后身体填满整个地图而结束,所以它不应该只是局限于固定的模式(例如我们游戏中常见的条形)。

Demo

AI算法基于Hamiltonian循环,速度较慢但更容易成功。

AI算法基于图片搜索,速度更快但更难成功。

步骤

1、安装CMake(https://cmake.org/download/)

2、使用以下命令生成构建文件

3、构建文件将根据操作系统类型在构建目录中生成。使用它们来构建这个项目

4、键盘控制

提示:当蛇运行时,程序员可以按空格键暂停,按W / A / S / D键逐步移动。任何时候,如果想让蛇再次开始运行,只需再次按空格键即可。

算法

1、最短路径

2、最长路径

3、AI算法

最短路径

我们使用广度优先搜索来找到最短路径,预测路径尽可能地保持直线,所以在地图上空的点越少,越有助于提高人工智能的成功率。

下图显示了该算法在18 * 18地图上的工作原理。 在搜索时扫描绿色区域,红色区域是最短路径。该点上的每个数字表示其到起始点的最小距离。

最长路径

假设我们要在4 * 4地图上找到从A点到B点的最长路径。该算法首先生成两个点之间的最短路径,然后扩展路径上的每对点,直到找不到扩展。由于最长路径问题是NP-hard,所以这个算法只是一个近似。

下图显示了在18 * 18地图上生成的最长路径,其中点0和点1分别是开始点和终点。

AI算法

这是一条贪吃蛇的完整画面:

从图中我们可以看出,为了用蛇的身体填充地图,当游戏结束时,整个身体必须形成一个Hamiltonian循环。为了确保存在Hamiltonian循环,地图必须具有偶数(或不是奇数)量的行或列。

有两个版本的AI算法可供选择,第一个是基于Hamiltonian循环,另一个是基于图搜索,它们都在Snake.decideNext中实现。

1、基于Hamiltonian循环

该算法首先在地图上生成Hamiltonian点,然后沿着点循环移动蛇。 为了避免固定周期循环,蛇必须有能力尽可能快地吃食物。

生成Hamiltonian循环的项目文件Snake.buildHamilton

假设我们要在4 * 4地图上建立一个Hamiltonian循环。那么我们的目标是将路径索引分配给地图上的每个点。下图显示了可能的Hamiltonian循环:

为了构建上述循环,我们首先修正点0,1和2,因为它们是蛇的初始位置。然后我们使点1不可达,并生成从第2点到第0点的最长路径。最后,我们加入起始点和结束点,形成一个Hamiltonian循环:

快捷方式:

有时,蛇可以直接吃食物,而不是跟随Hamiltonian循环。下面的图片简要解释了这个想法。

2、基于图片搜索的方式

要找到蛇S1的下一个移动方向是D,AI遵循以下步骤:

(1)计算从蛇S1的头到食物的最短路径P1。如果P1存在,请转到步骤2.否则,请转到步骤4。

(2)移动虚拟蛇S2(与S1相同)沿P1路径食用食物。

(3)计算从蛇S2的头到尾部的最长路径P2。如果存在P2,则令D为路径P1的第一个方向。否则,请转到步骤4。

(4)计算从蛇S1的头部到尾部的最长路径P3。如果存在P3,则令D为路径P3的第一个方向。否则,请转到步骤5。

(5)让D成为让蛇离食物最远的方向。

以上是该项目的简要说明,如果想要具体项目文件和说明请访问Gitub链接(https://github.com/stevennl/Snake)。


本文分享自微信公众号 - 奇点(qddata)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-02-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吉浦迅科技

TensorFlow版本号升至1.0,正式版即将到来

2015年11月份,谷歌宣布开源了深度学习框架TensorFlow,一年之后,TensorFlow就已经成长为了GitHub上最受欢迎的深度学习框架,尽管那时候...

40490
来自专栏玩转JavaEE

SpringBoot中使用POI,快速实现Excel导入导出

本文是vhr系列的第十一篇,vhr项目地址https://github.com/lenve/vhr 导出Excel 整体来说,Excel有.xls和.xls...

1K50
来自专栏玩转JavaEE

SpringBoot中发送QQ邮件

本文是vhr系列的第十二篇,项目地址https://github.com/lenve/vhr 邮件发送也是一个老生常谈的问题了,代码虽然简单,但是许多小伙伴...

36760
来自专栏互联网杂技

结合个人经历总结的前端入门方法

结合个人经历总结的前端入门方法,总结从零基础到具备前端基本技能的道路、学习方法、资料。由于能力有限,不能保证面面俱到,只是作为入门参考,面向初学者,让初学者少走...

46560
来自专栏玩转JavaEE

SpringBoot中自定义参数绑定

本文是vhr系列的第十篇,vhr项目地址https://github.com/lenve/vhr 正常情况下,前端传递来的参数都能直接被SpringMVC接...

50950
来自专栏架构师小秘圈

为什么说英语是一个码农成熟的标志?

作为在中国工作的程序员,不懂得英语似乎也不妨碍找到好工作,升职加薪。但程序员这个工种则稍有不同,因为程序,尤其是高级语言,基本上都是由英语 和数字表达式构成的。...

729110
来自专栏量子位

炸了!这届ICLR论文被指太“渣”?Goodfellow围追堵截要说法

安妮 夏乙 发自 凹非寺 量子位 出品 | 公众号 QbitAI 搞机器学习的这帮人在Twitter上又炸了。 起因是一名叫Anish Athalye的小哥率先...

37850
来自专栏古时的风筝

使用 github 做代码管理,知道这些就够了

只要掌握了下面的常用命令,基本上用使用 github 就没有问题。github 有两种认证方式,一种是通过 ssh 私钥的方式,一种通过 https 的账号名...

37480
来自专栏算法channel

算法channel使用指南(V2.0)

01 引言 欢迎关注 算法channel ! 交流思想,分享知识,找到迈入机器学习大门的系统学习方法,并在这条道路上不断攀登,这是小编创办本公众号的初衷。 本...

36880
来自专栏EAWorld

React Native 移动技术在企业架构的应用

很高兴在今天下午与各位有这样一次关于驱动原生(React Native) 技术的交流。 此次交流的内容,主要是我在Pworld2016 大会的讲解内容,本想比较...

38750

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励