我正在为基于网格的自上而下游戏进行 A* 寻路。我遇到的问题可能在下图中最容易理解。星号是玩家/NPC。黄色星号是当前想要前往 X 的 NPC。红色星号是在这种情况下是障碍物的 NPC。黄色单元格是墙壁，白色单元格是地板。虽然通往目标的整个路径确实无法到达，但我仍然想找到通往下一个最佳位置的路径（在这种情况下，点编号为 8）。
我可以很容易地让它绕过障碍物，但不确定如何完全按照我的描述去做。如果我在它遇到障碍物后停止它，它不会在 3 处停止正常运行。如果我重新路径到封闭列表中与最终目标距离最短的图块，如果最终目标在另一个以墙的一侧为例，它也会把事情搞得一团糟。
有什么建议么？我觉得我错过了一些明显的东西，所以请原谅这里的白痴。
谢谢，蒂姆
这是一个基于问题放松的想法：
首先，解决没有 NPC 的图的所有顶点的最短路径问题。您可以使用从目标节点开始的Dijkstra 算法的单个应用程序，以获取到每个顶点的目标的最短路径。
然后尝试在完整问题中找到最短路径。将 A* 与通过运行 Dijkstra's 作为启发式获得的最短路径信息一起使用；这是可以接受的，因为 NPC 问题中的最短路径总是至少与松弛问题中的最短路径一样长。跟踪迄今为止的最佳路径，并在搜索空间用尽时返回（正如我在评论中发布的那样）。
如果您认为这很昂贵，请意识到您只需要运行一次 Dijkstra's；您可以在同一张图上重复使用每次运行 A* 获得的信息。
（警告购买者：我没有尝试过这些。）
一种方法是在不考虑阻塞 NPC 的情况下计算从源到目的地的路径，然后检查路径上是否有任何阻塞 NPC。如果是这样，考虑路径上的第一个阻塞 NPC，然后再次计算路径。冲洗并重复，直到您无法再到达目的地。发生这种情况时，您可以将最后成功路径上最后一个阻塞 NPC 之前的点作为“下一个最佳”目的地。
这应该适用于您的示例，但如果目的地有两个被阻塞的入口，则此方法适用于更远的入口。此外，在最坏的情况下，您必须运行最短路径算法的次数与 NPC 的次数一样多。
larsmans 提出的方法比这要好得多，因为您只需运行一次 Dijkstra 和 A*。我仅将此作为您可以采取的各种方法的想法。