path-finding - 棋盘游戏寻路——寻找多条最优路径

Question

我有一个非常简单的寻路任务 - 一个在 8x8 网格上玩的棋盘游戏，每个方 block 要么可以通过，要么不能通过。我正在寻找的是一种算法，它将为我提供从某个方 block A 到方 block B 的最佳 n 条路径(假设有任何路径)。

我一直在研究 A*，但据我所知，没有明确的方法来扩展它以找到不止一条路径。

所以，关键是它给出的路径实际上是最短的 n 条路径，它不会遗漏任何一条。效率也很重要。谁能提出合适的算法，或为我指明正确的方向？

Answer 1

Dijkstra 算法适用于大多数此类情况，但由于您在 8x8 网格上，我将假设每个单元格之间的所有距离都相等且是静态的。在这种情况下，BFS(广度优先搜索)应该很适合您。