SnakeMine

这两天写了个自动蛇蛇,不过现在还是会死:当前版本旧版(运算会吃更多资源,比当前版本存活得久一点)。

github 最多赞的版本一篇旧论文

寻路本身使用贪心或者 A*(D*) 即可,可以小小地修改一下以满足题意:

  • 如果下一格不安全(没有可以到达尾部的空格路线,注意这里不需要维护蛇身,直接在当前空格子里搜即可),剪掉
  • 如果下一格会碰到墙/身,剪掉
  • 对于 A* 来说,根据蛇身运动维护一下闭集就成了 D*
  • 搜索深度太大,在线跑的话要适时停止搜索
  • 停止搜索就离死不远了(x)这时我们可以尝试下面某一种策略:
    • 用最长的路线追尾
    • 不管三七二十一,接近食物,万一就差这么几步呢
    • 远离食物

另外,A* 原版走出来的路折线太多,可以稍微修改一下启发函数,加上折点个数 * 系数即可。

但是,以上方法在后期搜索起来基本是难解问题的程度,为此我们需要在某一个阶段后搜索 Hamil­ton 环以减少步数消耗,参考开头给出的 github 链接。

基本方法是:


自动扫雷没什么算法,直接看谁能开开哪个即可。需要说的是无猜扫雷的生成,基本上只需要一个无脑版本:

该方法在雷数过多时几乎无解,所以有相关论文给出了一些其他姿势。(注意:原问题依然难解)

发表评论

电子邮件地址不会被公开。 必填项已用*标注