如何处理A*寻路中的障碍以达到"次佳"目标？

Question

我正在为基于网格的自上而下游戏进行A*寻路.我遇到的问题可能最容易理解,如下图所示.星号是玩家/ NPC.黄色星号是当前想要通往X的NPC.红色星号是NPC,在这种情况下是障碍物.黄色细胞是墙壁,白色细胞是地板.虽然目标的整个路径确实无法到达,但我仍然希望获得到下一个最佳位置的路径(在这种情况下,编号为8的点).

我可以轻松地绕过障碍物,但不知道如何按照我的描述完成.如果我一旦遇到障碍就停止它,它在3点停止时无法正常运行.如果我重新开始到距离最终目标最低距离的关闭列表中的图块,如果最终目标在另一个目标上以墙的一面为例,它也可以把事情弄得很糟糕.

有什么建议？我觉得我错过了其他明显的东西,所以请在这里原谅一个白痴.

蒂姆,谢谢

Answer 1

这是一个基于问题放松的想法:

首先,解决没有NPC的图的所有顶点的最短路径问题.您可以从目标节点开始使用Dijkstra算法的单个应用程序,以获得到达/来自每个顶点的目标的最短路径.

然后尝试在完整问题中找到最短路径.使用A*获取运行Dijkstra作为启发式获得的最短路径信息; 它是可以接受的,因为NPC问题中的最短路径始终至少与松弛问题中的最短路径一样长.跟踪到目前为止的最佳路径,并在搜索空间耗尽时返回(当我在评论中发布).

如果你觉得这很贵,那么你就会意识到你只需要经营Dijkstra一次; 您可以在同一图表上重复使用为每次A*运行获得的信息.

(警告:我没有尝试过任何这个.)