>我正在按照维基百科上的伪代码实现具有优先级队列的 A* 算法，以找到从一个源到无限大网格中到达另一个目的地的最短路径。当目标无法到达时，问题就出现了，例如，被墙壁包围(没有无限长的墙壁(，算法不会停止，因此它陷入了无限循环。我对解决方案的直观想法是做一些预处理工作，例如根据源和目标添加边界，或者在搜索之前检查目标是否被包围(这并不容易(。对无法到达的提早停车有什么建议吗？谢谢。
只要你没有任何无限的墙，你可以从源运行 A* 到目标，同时运行 A* 从目标到源。
如果目的地被围墙包围，那么最终目的地>源 A* 将没有选择。
如果源被墙壁包围，则源>目标 A* 最终将没有选项。
否则他们会在某个时候见面。 每当发生这种情况时，您都可以使用一个路径长度作为另一个的完美启发式方法。
只有在知道起点和终点位于图形的不同组成部分中时，才能停止。假设您没有无限长的墙壁，则只有在起点或目的地完全封闭时才会发生这种情况。但是检查这一点并非易事，因为您不知道何时停止该检查。
如前所述，这个问题似乎没有简单的解决办法。如果您能提供有关设置的更多详细信息，则也许可以执行更多操作。例如，如果墙都是线段，那么您可以使用计算几何算法(角度扫描？(来查看点是否被墙包围。