Snake-AI 正在参加 2021 年度 OSC 中国开源项目评选,请投票支持!
Snake-AI 在 2021 年度 OSC 中国开源项目评选 中已获得 {{ projectVoteCount }} 票,请投票支持!
2021 年度 OSC 中国开源项目评选 正在火热进行中,快来投票支持你喜欢的开源项目!
2021 年度 OSC 中国开源项目评选 >>> 中场回顾
Snake-AI 获得 2021 年度 OSC 中国开源项目评选「最佳人气项目」 !
授权协议 MIT
开发语言 C/C++ 查看源码 »
操作系统 跨平台
软件类型 开源软件
所属分类 游戏/娱乐休闲游戏
开源组织
地区 国产
投 递 者
适用人群 未知
收录时间 2016-11-11

软件简介

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完全问题,此算法得出的结果路径只是一个近似最长路径。

    效果展示:

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

展开阅读全文

代码

的 Gitee 指数为
超过 的项目

评论

点击加入讨论🔥(16)
暂无内容
发表了博客
{{o.pubDate | formatDate}}

{{formatAllHtml(o.title)}}

{{parseInt(o.replyCount) | bigNumberTransform}}
{{parseInt(o.viewCount) | bigNumberTransform}}
没有更多内容
暂无内容
发表了问答
{{o.pubDate | formatDate}}

{{formatAllHtml(o.title)}}

{{parseInt(o.replyCount) | bigNumberTransform}}
{{parseInt(o.viewCount) | bigNumberTransform}}
没有更多内容
暂无内容
暂无内容
16 评论
170 收藏
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部