我正在为基于网格的自上而下游戏进行A *寻路。下图中可能最容易理解我遇到的问题。星号是玩家/NPC。黄色星号是当前要转到X的NPC。红色星号是在这种情况下成为障碍的NPC。黄色的单元格是墙壁，白色的单元格是地板。尽管到达目标的整个路径确实无法实现，但我仍然想获得到达下一个最佳位置的路径(在这种情况下，点编号为8)。
我可以轻松地绕过障碍物，但是不确定如何完全按照我的描述进行。如果我在碰到障碍物后将其停止，则它无法停止在3处。如果我将路径重定向到与最终目标距离最小的封闭列表中的图块(如果最终目标位于另一个目标上)以墙的侧面为例，它也可能使事情变得很糟。
有什么建议么？我觉得我缺少其他明显的东西，因此请原谅这里的愚蠢行为。
谢谢，
提姆
最佳答案
这是一个基于problem relaxation的想法:
首先，为没有NPC的图的所有顶点求解最短路径问题。您可以使用从目标节点开始的Dijkstra's algorithm单个应用程序来获取每个顶点上/目标的最短路径。
然后尝试找到完整问题中的最短路径。将A *与通过运行Dijkstra获得的最短路径信息一起使用；这是可以接受的，因为NPC问题中的最短路径总是至少与松弛问题中的最短路径一样长。跟踪到目前为止的最佳路径，并在搜索空间用尽时返回(如我在评论中所述)。
如果您认为这很昂贵，那么请意识到您只需要运行Dijkstra一次。您可以在同一图表上重复使用每次运行A *所获得的信息。
(注意者:我没有尝试任何一种方法。)
关于path-finding - 如何处理A *寻路中的障碍以达到 'next best'目标？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13071260/