此网格实现中的寻路算法

Question

阅读有关 Dijkstra 寻路算法的文章，我发现适用于 "grid based" 游戏的每个示例都与您的 "cell" 通过或不通过的情况有关。我最好用图片来解释：

我需要为案例 II 实现一个从 A 到 B 的寻路算法（将 Cell 列表返回到 "follow"）。从图中可以看出，在这个模型中没有 "unpassable" 的单元格，但是每个单元格都存储了 4 个信息，这些信息决定了在一个单元格内，你是否可以上、下、左、右.

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

1. 案例二是否可以实现？
2. 如果是，请问可以给我一个建议吗？
3. 我应该为这种情况使用另一种算法吗（网格将是 32x14）？

Answer 1

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

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

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