网格实现中的PathFinding算法

Question

阅读Dijkstra的路径查找算法，我发现适用于“基于网格的”游戏的每个示例都与“单元”是可通过的或不能通过的情况有关。我最好用一张图片来检验：

​

​

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

在网上搜索，我发现了Dijkstra算法在案例I中的许多实现。

1. 是否有可能在第二种情况下实施？
2. 如果是，你能给我一个建议吗？
3. 在这种情况下，我是否应该使用另一种算法(网格将是32x14)？

Answer 1

是的，这是可能的。通过将单元格建模为节点，将您的细胞转换成一个图形，如果没有墙将两个单元格连接到一个边缘，则只将它们连接起来。

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

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