除了 A*、BFS、DFS 等之外，Pacman 中还广泛使用其他哪些好的寻路算法/启发式算法？如果吃豆人可以找到不止一种水果，我认为我提到的那些不会起作用。
我需要一些好的寻路算法，PacMan 可以使用它们以尽可能少的步数完成迷宫。我试图四处寻找指南，但到目前为止还没有运气。曼哈顿距离的 A* 随处可见，但它只适用于只有一个（或两个？或者可能最多几个？）水果的迷宫。
顺便说一句，为了简单起见，假设周围没有鬼魂。
原始 PacMan 问题的一些示例：First https://code.google.com/p/pacman-search/source/browse/trunk/+pacman-search+--username+hnly228078@gmail.com/src/layouts/bigSearch.lay?r=2, Second https://code.google.com/p/pacman-search/source/browse/trunk/+pacman-search+--username+hnly228078@gmail.com/src/layouts/trickySearch.lay?r=2 and Third https://code.google.com/p/pacman-search/source/browse/trunk/+pacman-search+--username+hnly228078@gmail.com/src/layouts/mediumCorners.lay?r=2
如果你知道迷宫的外观，启发式对我有用：
- 找到迷宫中当前最远的两个水果之间的真实距离 - 让我们称之为
x.
- 找到从当前吃豆人位置到前两个水果中较近的一个的真实距离 - 让我们称之为
y.
那么，答案就是：x + y.
请注意，实际距离不是曼哈顿距离，而是real迷宫中的距离 - 你可以计算它（如果你愿意的话甚至可以预先计算），因为你知道迷宫的外观（你知道所有的墙壁，......）。该信息（迷宫中某些两点之间的实际距离）是静态的，因为墙壁不会改变。
对此的解释x + y公式可能是这样的：
-
x- 无论哪种方式，你都必须走这段距离，至少在最后
-
y- 当您到达两个最远的水果中的一些时，最好收集靠近它的食物，这样您就不必返回
如果您正在解决这个问题作为伯克利人工智能类项目的一部分，为了计算两点之间的实际距离，您可以使用函数mazeDistance(pos1, pos2, gameState)它已经实现并且正在使用您的 bfs 实现。另外，这个启发式是可以接受的 and 持续的，至少对于他们的测试用例来说是这样。顺便说一句，通过这种启发，我成功地仅扩展了 376 个节点trickySearch maze.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
