algorithm - PacMan:主要使用了哪些启发式算法？

Question

除了 A*、BFS、DFS 等，Pacman 中还有哪些其他常用的寻路算法/启发式算法？如果 pacman 可以找到不止一种水果，我认为我提到的方法不会起作用。

我需要一些好的寻路算法，PacMan 可以使用这些算法以尽可能少的步数走完迷宫。我试图四处寻找指南，但到目前为止还没有运气。曼哈顿距离的 A* 随处可见，但它只适用于只有一个(或两个？或者最多几个？)水果的迷宫。

顺便说一句，为了简单起见，假设周围没有幽灵。

原始 PacMan 问题的一些示例: First , Second和 Third

Answer 1

如果您知道迷宫的外观，启发式方法对我有用:

1. 找到迷宫中当前最远的两个水果之间的实际距离 - 我们称之为 x。
2. 找到从当前 Pacman 位置到前两个水果中较近位置的实际距离 - 我们称其为 y。

然后，答案就是:x + y。

请注意，实际距离不是曼哈顿距离，而是迷宫中的实际距离 - 您可以计算它(如果需要，甚至可以预先计算)，因为您知道迷宫的外观(您知道所有的墙， ...)。此信息(迷宫中某些两点之间的实际距离)是静态的，因为墙壁不会改变。

这个 x + y 公式的解释可能是这样的:

• x - 无论哪种方式，您都必须走这段距离，至少在最后
• y - 当您位于最远的两个水果中时，最好收集靠近它的食物，这样您就不必返回

如果您将此作为伯克利 AI 类(class)项目的一部分来解决，为了计算两点之间的实际距离，您可以使用函数 mazeDistance(pos1, pos2, gameState)，它已经实现并且是使用你的 bfs 实现。此外，这种启发式方法是可接受的 和一致的，至少对于他们的测试用例而言。顺便说一句，通过这种启发式方法，我设法在 trickySearch 迷宫中仅扩展了 376 个节点。