如何使用A*管理“无路径”场景

Question

我有一个没有权重的2D网格上带有A*脚本的人工智能。什么是理想的或典型的方式来管理一个“无路径”的情况与这些人工智能，例如，人工智能是从他们的最终目标被无法行走的砖块？我可以看到开放列表的上限，但这似乎是武断的--毕竟，通往目标的道路可能很长--但是，达到这个目标的典型方式是什么呢？

Answer 1

通常，A*应该对它应该执行的迭代次数有一个限制。没有可以使用的“默认限制”，因为可以使用多个策略对此进行测试。

TLDR：使用分治简化较小问题的解决方案，以获得最佳结果，并将A*限制在受限空间或迭代量上。

从最坏到最好。

1. 设置硬限制--这是最简单的解决方案，也是最坏的解决方案。因为您不知道问题在哪里，或者路径是否可走，如果达到路径限制，很难决定应该做什么。
2. A*从头到尾()--这样做“不应该”提高算法的性能，如果路径满足，您就有答案了。但是如果没有，您可以跟踪起点和终点之间的最近点，并将其设置为“临时目的地”。然后从那里再试一次(您可以保存您已经找到的路径并从那里扩展它)。这种方法的缺点是在某些边缘情况下可能会走错路。
3. 低质量A*用于图形路径点路径查找--如果您知道有些地方有很长的路径，可能需要很长时间才能找到一条路径，您可以对世界地图进行块块处理，并计算基于路径的路由，例如: 32x32或64x64等等，在A*中将块作为单个节点。创建一个检查此块是否可步行的算法。然后，不要使用A*创建整个路由，而是使用Dijkstra的算法，使用预定义的路径点(最好在运行时之前生成)预先确定路径，然后使用A*在块内移动，该块将目标是另一个块中的可移动网格元素。通过这种方式，您知道如何进入与目的地相同的块，从那里开始，发现块内没有路径的惩罚是最小的，因为您有一个非常有限的区域要检查。

Answer 2

如果两个瓷砖之间从来没有任何可行走的路径，那么它们就没有理由成为同一个图的一部分。如果映射是静态的，则可以将映射预处理为保证在所有瓷砖之间具有有效路径的区段。

如果映射是完全动态的，那么您可能必须设置一个严格的节点数量上限。

如果只有特定的节点可以被阻塞/解除阻塞，那么您可能需要一个多层次的策略。也就是说，为每个部分创建一个节点，并在这个图中运行一个初步的路径查找。

对于被NPC阻塞的节点，需要另一种解决方案，例如在路径查找过程中忽略节点，并在冲突发生时处理冲突。