0

只是为了提高我的 java 脚本技能，我正在尝试用 js 开发一个 pacman 游戏。有一个 20 x 20 的网格。这个网格有 0 和 1，表示是否有墙或路径。现在我想开发一个算法让恶魔跟随吃豆人。我不确定我应该使用哪种算法。

所以我对函数的输入将是 foo(current position, pacman position,grid, path)

var maze = [            [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0],
                        [0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
                        [0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
                        [0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
                        [0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
                        [0,1,1,1,1,1,0,0,0,1,1,0,0,0,1,1,1,1,1,0],
                        [0,1,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,0],
                        [0,1,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0],
                        [1,1,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1,1],
                        [0,1,0,0,0,1,1,0,0,0,0,0,0,1,1,0,0,0,1,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0],
                        [0,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,0],
                        [0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0],
                        [0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1,0,1,0],
                        [0,1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,1,0,1,0],
                        [0,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,0],
                        [0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0]];
4

3 回答 3

3

对于未加权图，您有几个选项可以找到最短路径：

  • BFS - 最简单的解决方案 - BFS 是完整且最优的 - 如果存在，它将找到最短路径。
  • Bi-Directional BFS - 基本相同，但从两侧进行 BFS，并在两个 BFS 相遇时结束。它显着减少了发现的顶点数量。我在这个线程中解释了更多关于如何做到这一点以及为什么它很好。
  • 启发式A* 算法- 它是一种知情算法，因此通常比其他算法更快，但更难编程。使用可接受的启发式函数，例如manhattan distances。

就个人而言-我认为在这种情况下我会使用 BFS-但从 pacman 开始，直到您发现所有“目标”（恶魔位置）-它将为您提供从每个恶魔到 pacman 的最短路径。
请注意，如果您只有几个恶魔和一个大棋盘，则执行 A* 数次（每个恶魔一次）可能是更好的解决方案。

人们可能应该对其进行基准测试，看看哪个实际上更好。

于 2013-10-19T07:29:43.580 回答
0

如果您需要找到从源到所有顶点的最短路径，请从源执行广度优先搜索，并将每个顶点的父节点存储在单独的数组中。跟随父节点将为您提供从每个顶点到它的路径父母。

于 2013-10-19T07:29:24.320 回答
0

我认为深度优先搜索也适用于此。与广度优先搜索相比，使用 DFS 时无需存储所有叶子节点。但它有时无法找到解决方案。这里的输入并没有那么复杂，所以我认为 DFS 已经足够好了。

此外，A* 搜索算法是最佳选择，因为它比不知情的搜索更快，并且始终完整且最优。它保证解决方案是最优的。对于复杂的情况，创建一个有效的启发式函数确实需要成本。在这里，您可以使用曼哈顿距离或欧几里得距离。

于 2013-10-19T19:56:29.307 回答