贪吃蛇游戏的人工智能 Snake-AI

• 授权协议: MIT
• 开发语言: C/C++
• 操作系统: 跨平台
• 软件首页: https://github.com/stevennL/Snake-AI
• 软件文档: https://github.com/stevennL/Snake-AI/blob/master/README-CN.md
• 官方下载: https://github.com/stevennL/Snake-AI/archive/master.zip

软件介绍

Snake-AI，这是一个用 C/C++ 语言编写的贪吃蛇游戏的人工智能。

AI 的目的是让蛇尽可能的吃更多的食物，直到吃满整个地图。想参与这个项目，请查看todos。

Demo

使用方法

编译与运行：

$ make
$ make run

为了解详细使用方法, 请查看主函数main()

算法介绍

• 函数Snake.decideNext(): 计算蛇S1的下一个移动方向D

1. 计算从蛇S1的头部到达食物的最短路径P1。

2. 派一条与蛇S1完全一样的虚拟蛇S2沿路径P1吃掉食物。

3. 计算从蛇S2的头部到其尾部的最长路径P2。如果路径P2存在，将移动方向D设置为路径P1的第一个方向，否则进行步骤4。

4. 计算从蛇S1的头部到达其尾部的最长路径P3。如果P3存在，将移动方向D设置为路径P3的第一个方向，否则进行步骤5。

5. 将移动方向D设置为离食物最远的方向。

• 函数Map.findMaxPath(): 计算两个位置间的最长路径

  算法建立在DFS与贪心算法的基础上。每次遍历邻接点时，离目标位置最远（使用曼哈顿距离估计）的位置将会被优先遍历到。另外，为了使路径尽可能直，如果两个位置到目标位置的距离相等，在当前移动方向上的位置将被优先遍历到。这个问题是一个NP完全问题，此算法得出的结果路径只是一个近似最长路径。

  效果展示:

  （绿色区域为搜索算法扫描到的区域，红色区域为最后计算出的最长路径，每个位置上的数字表示了从该位置开始到目标位置的估计距离）

本文地址：https://codercto.com/soft/d/16785.html