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）。