algorithm - 非网格地图中的沼泽/死胡同修剪

Question

在使用非网格地图时，是否有任何现有算法可以在寻路中查找和避免有问题的区域（沼泽、死胡同）？有很多可用于避开这些区域或通过跳转点递归等方式伪避开这些区域的网格，但我还没有找到任何对四叉树、导航网格或其他非均匀地图有用的东西。

Answer 1

死角检测和沼泽不是特定于网格的。他们只是在网格地图上进行评估。

Answer 2

这样的事情可能确实存在——每年都会发表数百篇寻路和运动规划论文，但我认为你需要问自己一个更大的问题——你为什么要这样做？

使用导航网格或稀疏网格表示的想法是通过减少图中节点的数量来减少找到解决方案所需的时间。如果您的搜索太慢，只需修剪图中的节点和边数。通过在您开始之前从离线搜索中手动删除任何死胡同，您将减少每次搜索的开销。

如果即使在您修剪了图形之后，搜索仍然很慢并且您可以容忍搜索问题的近似解决方案，请考虑使用加权 A*，您可以重新计划降低通货膨胀因子，直到您确实获得最佳成本。

规划算法充满了妥协，只要确保你了解你选择做什么的利弊。

最后一个建议是，确保您在使用的规划器中正确实现了原语 - 像 A* 这样的算法依赖于正确实现优先级队列，特别是确保reduce-key为 O(log n) 或更好。