【经典案例】贪吃蛇 AI 的实现 snake AI

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.findMinPath(): 计算两个位置间的最短路径

    算法建立在BFS的基础上。为了使路径尽可能直,每次遍历邻接点时,在当前移动方向上的位置会被优先遍历。

    效果展示:

    (绿色区域为搜索算法扫描到的区域,红色区域为最后计算出的最短路径,每个位置上的数字表示了从起始位置开始到该位置的最短距离)

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

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

    效果展示:

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

 

下载地址https://github.com/chuyangliu/Snake

 

开心一下:

汽车嫁给火车,可不久就离婚了。大家问原因,汽车伤心地说:“他天天担心我被撞,我呢,时时怕他出轨,真受不了。
1.本站所有资源仅用于学习及研究使用,请必须在24小时内删除所下载资源,切勿用于商业用途,否则由此引发的法律纠纷及连带责任本站和发布者概不承担。资源除标明原创外均来自网络整理,版权归原作者或本站特约原创作者所有,如侵犯到您权益请联系本站删除! 2.本站站内提供的所有可下载资源(软件等等)本站保证未做任何负面改动(不包含修复bug和完善功能等正面优化或二次开发);但本网站不能保证资源的准确性、安全性和完整性,用户下载后自行斟酌,我们以交流学习为目的,并不是所有的源码都100%无错或无bug;同时本站用户必须明白,小鱼源码对提供下载的软件等不拥有任何权利(本站原创和特约原创作者除外),其版权归该资源的合法拥有者所有。 3.请您认真阅读上述内容,购买即以为着您同意上述内容。
小鱼源码下载网 » 【经典案例】贪吃蛇 AI 的实现 snake AI

精品源码,商业服务,发布得积分,VIP免费下

开通会员 发布资源