android - 大 map 实现A星(A*)路径算法，性能低

Question

我正在使用这个 A 星 (A*) Pathfinder.java 在 Android map 应用程序中计算和生成我的路线。 https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java

map 的尺寸​​很大，尺寸在8000x8000左右，当我使用A星Pathfinder.java计算 map 中一个点到另一个点的路线时。

A star Pathfinder 1 by 1计算，用于大 map (8000x8000)，性能/计算速度相当低/慢(效率不高)。我尝试将计算增加到 100 x 100，它工作正常但绘制的路线路径曲线不平滑。

有没有办法通过A星算法或任何其他建议来提高路由计算性能来解决这个问题？我需要帮助来解决这个问题。

Answer 1

实现:如果您正在寻找代码审查，请在 CodeReview.StackExchange.com 上发布工作代码。他们可能会为您提供一些优化提示。

算法:以下是从算法角度考虑的几个问题。

首先，看看您的启发式算法。如果启发式估计值太低，A* 就会退化为 Dikstra 算法。如果启发式估计值太高，A* 就会退化为贪心最佳优先搜索。具有可接受启发式的 A* 位于中间的某个位置:它产生最佳路径，但保持最佳性会花费额外的计算时间。如果您愿意牺牲最优性，您可以选择一种有时高估目标距离的启发式算法。通过这样做，不能保证路径是最优的，但算法的贪婪性可以减少执行时间。

此外，如果世界是静态的(即布局是已知的先验)，您可以预先计算大量信息以帮助加快搜索速度。存在几种算法来完成此任务。 Swamps是一种预先计算往往会被不必要地搜索的区域(即沼泽​​)的方法。除非进出沼泽，否则不需要在运行时搜索区域。归因于沼泽的加速在很大程度上取决于世界的地形；更具欺骗性的 map (即那些倾向于将搜索引向沼泽的 map )有很多好处。

另一种方法是使用分层寻路方法，例如 HPA* .这可能会在像您的 map (8000x8000，哎呀)一样大的 map 上显着提高性能。 HPA* 通过将区域分组为链接的本地集群并计算跨越集群边界的成本来先验。然后，搜索在多个级别进行:高级工作通过利用预先计算的成本来集中搜索，低级工作确定将使用的确切路径。

此外，还存在通过在运行时利用环境特征来减少 A* 探索的节点数量的算法。例如，Jump Point Search (JPS)利用网格图(就像您正在使用的那个)经常表现出对称性这一事实。如果您世界中的移动具有恒定成本，则 JPS 可以“跳过”搜索中的许多节点并显着减少搜索时间。我看到它减少了 24 倍的 A* 搜索时间，其他人看到了超过 30 倍的改进。

最后一点:据我所知，您使用的是 L1 路径(即 4 个基本方向)。通过预处理航路点之间的路径和使用差分启发式算法，您可能会收获很多。参见 this article用于演示和 JavaScript 实现的讨论 here .

附加链接:

• Great visualizations of JPS in action
• More info for JPS
• Variations of A*
• Amit's A* Pages: the best A* resource I know
• How to speed up A* blog post