如何使用 A* 管理 "no-path" 场景
How to manage a "no-path" scenario with A*
我在没有权重的二维网格上使用带有 A* 脚本的 AI。使用这些 AI 管理“无路径”情况的理想或典型方法是什么，例如AI 被无法行走的瓷砖挡住了最终目标？我可以看到打开列表的上限，但这似乎是任意的——毕竟通往目标的路径可能很长——但是处理这个问题的典型方法是什么？
通常，A* 应该对其执行的迭代次数有限制。没有您可以使用的“默认限制”，因为您可以使用多种策略对此进行测试。
TLDR：使用 Divide and conquer 简化较小问题的解决方案以获得最佳结果，并将 A* 限制在 space 或迭代范围内金额。
从最差到最好列出。
- 设置硬限制 - 这是最简单的解决方案，也是最坏的解决方案。因为你不知道问题出在哪里，或者这条路是否可以走，所以很难决定如果你达到了你的路径限制你应该做什么。
- A* 从头到尾立即完成 - 这样做“应该”不会提高算法的性能，如果路径满足，您就有答案。但如果他们不这样做，您可以追踪到起点和终点之间最近点的位置，并将其设置为“临时目的地”。然后从那里再试一次（你可以保存你已经得到的路径并从那里扩展它）。这种方法的缺点是在某些边缘情况下您可能会走错路。
- Low-quality A* for graph waypoint pathfinding - 如果你知道有些地方的路线很长，可能需要很长时间才能找到路线，你可以对世界地图进行分块 - 并基于例如 32x32 或 64x64 等计算路线。分块作为 A* 中的单个节点。创建一个算法来检查这个块是否可步行。然后，不是使用 A* 制作整个路线，而是使用 Dijkstra 的算法，该算法将使用预定义的 waypoints 预先确定路径（最好在运行时之前生成），然后使用 A* 移动到块内，该块将以另一个中的可行走网格元素为目标块。这样你就知道如何进入与你的目的地相同的块，并且从那里发现块内没有路径的惩罚是最小的，因为你要检查的区域非常有限。
如果两个图块之间从来没有任何可行走的路径，那么它们就没有理由成为同一个图的一部分。如果地图是静态的，您可以使用 Djikstra pre-process 将地图分成保证所有图块之间具有有效路径的部分。
如果地图是完全动态的，您可能必须设置节点数的硬性上限。
如果只有特定节点可以 blocked/unblocked，您可能需要 multi-level 策略。 IE。为每个部分创建一个节点，并 运行 在此图中进行初步路径查找。
对于诸如节点被 NPC 阻止之类的事情，需要另一种解决方案，例如在 path-finding 期间忽略它们并在它们发生时处理冲突。
我在没有权重的二维网格上使用带有 A* 脚本的 AI。使用这些 AI 管理“无路径”情况的理想或典型方法是什么，例如AI 被无法行走的瓷砖挡住了最终目标？我可以看到打开列表的上限，但这似乎是任意的——毕竟通往目标的路径可能很长——但是处理这个问题的典型方法是什么？
通常，A* 应该对其执行的迭代次数有限制。没有您可以使用的“默认限制”，因为您可以使用多种策略对此进行测试。
TLDR：使用 Divide and conquer 简化较小问题的解决方案以获得最佳结果，并将 A* 限制在 space 或迭代范围内金额。
从最差到最好列出。
- 设置硬限制 - 这是最简单的解决方案，也是最坏的解决方案。因为你不知道问题出在哪里，或者这条路是否可以走，所以很难决定如果你达到了你的路径限制你应该做什么。
- A* 从头到尾立即完成 - 这样做“应该”不会提高算法的性能，如果路径满足，您就有答案。但如果他们不这样做，您可以追踪到起点和终点之间最近点的位置，并将其设置为“临时目的地”。然后从那里再试一次（你可以保存你已经得到的路径并从那里扩展它）。这种方法的缺点是在某些边缘情况下您可能会走错路。
- Low-quality A* for graph waypoint pathfinding - 如果你知道有些地方的路线很长，可能需要很长时间才能找到路线，你可以对世界地图进行分块 - 并基于例如 32x32 或 64x64 等计算路线。分块作为 A* 中的单个节点。创建一个算法来检查这个块是否可步行。然后，不是使用 A* 制作整个路线，而是使用 Dijkstra 的算法，该算法将使用预定义的 waypoints 预先确定路径（最好在运行时之前生成），然后使用 A* 移动到块内，该块将以另一个中的可行走网格元素为目标块。这样你就知道如何进入与你的目的地相同的块，并且从那里发现块内没有路径的惩罚是最小的，因为你要检查的区域非常有限。
如果两个图块之间从来没有任何可行走的路径，那么它们就没有理由成为同一个图的一部分。如果地图是静态的，您可以使用 Djikstra pre-process 将地图分成保证所有图块之间具有有效路径的部分。
如果地图是完全动态的，您可能必须设置节点数的硬性上限。
如果只有特定节点可以 blocked/unblocked，您可能需要 multi-level 策略。 IE。为每个部分创建一个节点，并 运行 在此图中进行初步路径查找。
对于诸如节点被 NPC 阻止之类的事情，需要另一种解决方案，例如在 path-finding 期间忽略它们并在它们发生时处理冲突。