Ai算法:“RaceTrack”游戏的AI算法

有没有人知道(或可以建议)为RaceTrack铅笔纸游戏的 AI 的好算法?

因为你有 9 个可能的选择,在每一步,你需要看至少 6-10 个步骤来决定一个好的策略,bruteforce 变得非常昂贵,即使你可以排除一些选择,因为与边界相交。

目前,我试图为每个选择分配一些质量值,以决定哪些选择要排除-但我不知道如何分配这样的质量值的好规则。

14

我已经做了一个 C ++ 求解器,它有点太长了(187 行),以适应这里,所以我把它放在 pastebin 中:http://pastebin.com/3G4dfTjR该程序要么计算一个最佳(最小可能的移动次数)解决方案,要么报告没有可能。

用法

赛道startX startY goalX goalY [circleX circleY radius]运行程序。

该程序假定为 100x100 网格,该网格可以选择包含一个圆形障碍物,您可以指定其中心和半径。您必须另外指定汽车的初始位置和单个目标位置。尽管这些约束有些限制,但查看代码应该很明显,它们通常不会限制算法-所有相关逻辑都封装在isMoveValid()isGoalState()的多个位置中,因此,如果有人可以麻烦实现这些常规位图

唯一稍微复杂的是使目标位置与起始位置相同(或接近,但“在另一侧”),如果您希望轨道成为赛道,这就是您所需要的。在这种情况下,为了避免求解器简单地将汽车转向或立即停止,您需要指定一条不可见的“起跑线”,并更改isMoveValid()以禁止该线上的“向后”运动。

它的工作原理

因为每次移动的成本恰好为 1,所以可以使用广度优先搜索通过 4D 状态空间的状态来确定最佳解决方案。每当我们访问给定的状态 s 时,它由一个 4 元组(x,y,dx,dy)组成,其中 dx 和 dy 是我们用来到达(x,y)的速度矢量,因此我们可以通过一次移动从 s 到达的所有 9 个状态

BFS 比 Dijkstra 的算法或 A * 搜索更简单,因此可能更快,后者是更通用的算法,允许移动具有各种成本-我们在这里不需要的灵活性。如果混淆其启发式方法的障碍很少,A * 可能会更快,但是在每个步骤中,它都需要查找最低成本节点,这通常是使用堆完成的,而对于 BFS,最低成本节点始终位于队列的前面。

示例

秒表赛道 30 3 90 10

Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
No obstacle.
11-step solution:
(90, 10) (dx=10, dy=4)
(80, 6) (dx=9, dy=3)
(71, 3) (dx=8, dy=2)
(63, 1) (dx=7, dy=1)
(56, 0) (dx=6, dy=0)
(50, 0) (dx=5, dy=0)
(45, 0) (dx=5, dy=0)
(40, 0) (dx=4, dy=0)
(36, 0) (dx=3, dy=-1)
(33, 1) (dx=2, dy=-1)
(31, 2) (dx=1, dy=-1)
(30, 3) (dx=0, dy=0)
128113 states were examined in the process.
stopwatch: Terminated. Elapsed time: 343ms
stopwatch: Process completed with exit code 0.

秒表赛道 30 3 90 10 50 20 25

Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
A circular obstacle of radius 25 is centred at (50, 20).
22-step solution:
(90, 10) (dx=5, dy=-8)
(85, 18) (dx=5, dy=-7)
(80, 25) (dx=4, dy=-6)
(76, 31) (dx=4, dy=-5)
(72, 36) (dx=5, dy=-4)
(67, 40) (dx=6, dy=-3)
(61, 43) (dx=7, dy=-2)
(54, 45) (dx=8, dy=-1)
(46, 46) (dx=7, dy=0)
(39, 46) (dx=6, dy=1)
(33, 45) (dx=5, dy=2)
(28, 43) (dx=4, dy=3)
(24, 40) (dx=3, dy=4)
(21, 36) (dx=2, dy=5)
(19, 31) (dx=1, dy=6)
(18, 25) (dx=0, dy=6)
(18, 19) (dx=-1, dy=5)
(19, 14) (dx=-2, dy=4)
(21, 10) (dx=-3, dy=3)
(24, 7) (dx=-3, dy=2)
(27, 5) (dx=-2, dy=1)
(29, 4) (dx=-1, dy=1)
(30, 3) (dx=0, dy=0)
949565 states were examined in the process.
stopwatch: Terminated. Elapsed time: 3076ms
stopwatch: Process completed with exit code 0.

请注意,这里的最佳解决方案首先必须“双回”,向上和周围,然后再向下,因为圆形障碍物一直延伸到网格的底部。

小错误:如果您将目标位置设置为等于初始位置,则发布的代码将给出简短的(但长度不为零!)答案。显然,这可以作为特殊情况进行检查,但是当我意识到这一点时,我已经将代码放在 pastebin 上...:)

5

其他人推荐 A *,这可能是要走的路,但是这种方法有一个问题。让我首先说,从一个节点到另一个节点的“成本”总是 1,因为你想最小化步骤的数量,根本不涉及其他成本。

但是我想说的重要一点是,位置(x,y)不是 A * 的搜索图中的唯一节点!该节点的特征在于 x 和 y,还在于汽车来自的节点的 x 和 y 坐标(或速度分量 vx 和 vy)。因此,您不能仅在 2 维网格上遍历 A * 算法;它实际上应该是 4 维的。也就是说,A * 仍然是

至于启发式,你可以得到真正的创意,但我建议像距离完成减去当前速度,其中距离是预先计算的每个点在规则的 2D 网格 (使用 Dijkstra 算法)。

不过,一个问题是 A * 总是会产生最佳路线,所以使用这种算法的 AI 不会很有趣,因为它总是会赢(假设起始位置是公平的)。

5

到目前为止,我不认为任何人已经解决了你的问题的一个关键点:你如何想出一个好的“质量值”?在人工智能中,你提到的质量值通常被称为“启发式”。理想情况下,你的启发式方告诉你在当前位置 / 速度下到达终点所需的最小移动次数。实际上,我们必须满足于更容易计算的东西。

一个重要的准则是,一个好的启发式方法应该是admissable;也就是说,它不应该高估达到目标的成本(在你的情况下,达到终点的移动次数)。

提出可接受的启发式方法的一种常见技术是放松原始问题。在游戏中,您通常可以通过更改游戏以使其变得更容易(例如,通过放弃规则)来做到这一点。例如,在 RaceTrack 中,您可以拉直轨道以使其更容易。对于直线轨道,最好的策略显然是连续加速。因此,可接受的启发式方法是计算从当前位置到终点的恒定距离()

您可以通过放宽不同的规则来提出其他启发式方法,但是在启发式方法的准确性和所需的计算量之间通常需要权衡。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(326)
Python与或非逻辑符号:Python-docx忽略非unicode符号 如“大于或等于”
上一篇
牛头q技能图标:Quasar q-icon在资产文件夹中使用图标
下一篇

相关推荐

  • Ios节奏大师:AKFrequencyTracker与节奏

    关于Ios节奏大师的问题,在tempo tracker中经常遇到,使用 AKFrequencyTracker 时,我喜欢添加“节奏”功能,以根据音符的节奏和惊奇来识别音符…

    2023-10-27 06:12:10
    0 24 96
  • C++回溯法:c++ 中的递归回溯(recursive backtracking c++)

    关于C++回溯法的问题,在recursive backtracking c++中经常遇到,我正在尝试编写一个程序,该程序将使用回溯来创建一个数独求解器。我已经能够创建一个黑色的数独网格,我可以检查一个移动是否是有效的移动。我的程序工作正常,直到一个正方形有多个数字选择。…

    2024-03-18 05:58:19
    0 20 48
  • 大华平台管理服务器:使用systemd管理Trackmania服务器

    关于大华平台管理服务器的问题,在trackmania server list中经常遇到,嗨,我刚刚设置了一个 trackmania 服务器,通过命令行启动时工作正常。现在我想用 systemd 管理它,所以它在启动时启动,如果它崩溃,它会重新启动。…

    2024-03-03 11:07:33
    0 92 98
  • 云服务器免费租用:Rackspace(云)服务器上的 Apache服务器

    关于云服务器免费租用的问题,在rackspace server中经常遇到,我试图从 django web 开发服务器转移到 Apache 服务器。该网站托管在我正在使用 ssh 访问的 rackspace 服务器上。我已经在服务器上安装了 apache。…

    2024-02-06 14:19:36
    0 34 12
  • C++输入多组数据:在 C++程序中访问AppleMagicTrackpad输入数据

    关于C++输入多组数据的问题,在apple touchpad中经常遇到,我想读取触控板多点触控手势和坐标数据到我的 C ++ 程序。…

    2022-11-23 08:36:28
    0 36 19
  • Crackles:用简单的图形播放 iOS网络音频时发出的裂纹和噪音

    关于Crackles的问题,在audio graph中经常遇到,当使用createMediaElementSource()将音频元素与网络音频图连接时,我注意到这偶尔会导致在 iOS 设备(iPhone,iPad)上播放时出现裂纹。在使用(便宜的)Android 设备或运行完全相同代码的 macOS 桌面时,我从未遇到过这些问题。…

    2023-10-23 05:17:27
    0 71 67
  • docker游戏服务器:如何使用Docker搭建高性能的游戏服务器

    Docker游戏服务器是一种将游戏服务器部署到容器中的方式,它可以帮助游戏开发者快速、轻松地部署游戏服务器,并且可以更轻松地扩展游戏服务器的容量。…

    2023-04-27 09:55:33
    0 93 88
  • win7玩cf卡顿怎么解决:解决Win7环境下CF游戏卡顿问题

    尝试更新系统:可能是由于系统缺少某些补丁或者更新导致CF卡顿,可以尝试在Windows Update中进行检查更新,并安装最新的补丁和更新。更新显卡驱动:可能是由于显卡驱动过旧或者不兼容导致CF卡顿,可以尝试更新显卡驱动,可以到显卡厂商官网下载最新的驱动进行安装。…

    2023-05-27 11:45:17
    0 83 33

发表评论

登录 后才能评论

评论列表(68条)