algorithm - 此网格实现中的寻路算法

Question

阅读 Dijkstra 的寻路算法，我发现适用于“基于网格”的游戏的每个示例都与您拥有可通过或不可通过的“单元格”的情况有关。我最好用一张图片来解释:

我需要为案例 II 实现一个从 A 到 B 的寻路算法(返回要“跟随”的 Cell 列表)。从图中可以看出，在这个模型中没有“不可通过”的单元格，但是每个单元格都存储了 4 个信息，这些信息决定了在单元格内是否可以上、下、左、右。

在网上搜索我发现了很多 Dijkstra 算法对案例 I 的实现。

1. 是否可以为案例 II 实现它？
2. 如果是，你能给我一个建议吗？
3. 我应该为这种情况使用另一种算法吗(网格将是 32x14)？

Answer 1

是的，这是可能的。通过将单元格建模为节点，将单元格转换为图形，如果没有墙将它们分开，则只用边连接两个单元格。

但是，对于这样一个简单的示例，Dijkstra 并不是最好的算法。如果图中所有边的距离都为 1，您可以简单地使用 BFS 搜索来找到最快的路径。

此外，路径是网格这一事实可能意味着您甚至可以找到更快的算法来解决问题。但是，这只有在您的网格非常大时才有意义。对于您的 32x14 网格，我非常怀疑复杂的算法是否会比 BFS 更快。