javascript - 最短路径算法未加权图

Question

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

所以我对该函数的输入将是 foo( 当前位置，pacman 位置，网格，路径)

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]];

Answer 1

对于未加权的图，您有多种选择来寻找最短路径:

• BFS - 最简单的解决方案 - BFS 是完整且最优的 - 它会找到最短路径(如果存在的话)。
• Bi-Directional BFS - 基本相同，但从两侧进行 BFS，并在两个 BFS 相遇时结束。它显着减少了发现的顶点数量。我在 this thread 中详细解释了如何做以及为什么它很好。 .
• 启发式 A* Algorithm - 它是一种明智的算法，因此通常比其他算法更快，但更难编程。使用 admissible heuristic function有了它，就像manhattan distances .

个人 - 我想在这种情况下我会使用 BFS - 但从 pacman 开始，直到你发现所有“目标”(恶魔位置) - 它会给你从每个恶魔到 pacman 的最短路径。
请注意，如果您只有几个恶魔和一 block 大棋盘，则多次执行 A*(每个恶魔一次)可能是更好的解决方案。

可能应该对其进行基准测试，看看哪个更好。