大地图实现A星(A*)路径算法，性能低 [英] Implement A star (A*) path algorithm in large map, low performance
问题描述
我正在使用这个 A 星 (A*) Pathfinder.java 来计算 &在 Android 地图应用程序中生成我的路线.https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java
I'm using this A star (A*) Pathfinder.java to calculate & generate my route in an Android map app. https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java
地图的尺寸很大，尺寸在8000x8000左右，当我使用A星Pathfinder.java计算地图中从一个点到另一个点的路线时.
The size of the map is large, dimensions around 8000x8000, when I use the A star Pathfinder.java to calculate the route from one to another point in the map.
A星探路者1×1计算，用于大地图(8000x8000)，性能/计算速度相当低/慢(效率不高).我试图将计算增加到 100 x 100，它工作正常，但绘制的路线路径曲线不平滑.
The A star Pathfinder calculate 1 by 1 and used in the large map (8000x8000), the performance/calculation speed is quite low/slow (not efficient). I have tried to increase the calculation to 100 by 100, it work fine but the route path drawn is not smooth in curve.
无论如何，是否可以使用 A 星算法或任何其他解决问题的建议来提高路线计算性能?我需要帮助来解决这个问题.
Is there anyway to improve the route calculation performance with the A star algorithm or any other sugguest to solve the issue? I need help to solve the issue.
推荐答案
实施:如果您正在寻找代码审查，请将工作代码发布到 CodeReview.StackExchange.com.他们可能会给你一些优化技巧.
Implementation: If you're looking for a code review, post the working code over at CodeReview.StackExchange.com. They can probably give you some optimization tips.
算法:以下是从算法角度考虑的几个因素.
Algorithm: Here are several considerations from an algorithmic perspective.
首先，看看你的启发式.如果启发式估计太低，A* 将退化为 Dikstra 算法.如果启发式估计太高，则 A* 退化为贪婪的最佳优先搜索.具有可接受启发式的 A* 位于中间的某个位置:它产生了最佳路径，但保持最佳性会花费您额外的计算时间.如果您愿意牺牲最优性，您可以选择一种有时高估与目标的距离的启发式方法.这样做并不能保证路径是最优的，但算法的贪婪性可以减少执行时间.
First, take a look at your heuristic. If the heuristic estimates too low, A* degenerates to Dikstra's algorithm. If the heuristic estimates too high, A* degenerates to a Greedy Best First Search. A* with an admissible heuristic sits somewhere in the middle: it produces an optimal path, but maintaining optimality costs you additional computation time. If you are willing to sacrifice optimality, you may select a heuristic which sometimes over-estimates the distance to the goal. By doing so, the paths are not guaranteed to be optimal, but the greediness of the algorithm could reduce execution time.
此外，如果世界是静态的(即布局先验)，您可以预先计算大量信息以帮助加快搜索速度.存在多种算法来完成此任务.Swamps 是一种预先计算往往被不必要搜索的区域的方法(即沼泽).除非进入或离开沼泽，否则不需要在运行时搜索区域.归因于沼泽的加速在很大程度上取决于世界的地形；更具欺骗性的地图(即倾向于将搜索引向沼泽的地图)大有裨益.
Also, if the world is static (i.e. the layout is known a priori), you can pre-compute much information to help speed-up your search. Several algorithms exist to accomplish this task. Swamps is an approach that pre-computes regions that tend to be searched needlessly (i.e. the swamps). Unless travelling into or out of a swamp, the regions need not be searched at runtime. The speed-up attributed to Swamps depends heavily on the world's topography; more deceptive maps (i.e. ones that tend to lead the search toward swamps) have much to benefit.
另一种方法是使用分层寻路方法，例如 HPA*.这可能会在与您的地图(8000x8000，哎呀)一样大的地图上显着提高性能.HPA* 通过将区域分组为链接的本地集群并先验计算跨越集群边界的成本来运行.然后，搜索在多个级别进行:高级别工作通过利用预先计算的成本来集中搜索，低级别工作确定将使用的确切路径.
Another approach is to use a hierarchical pathfinding approach such as HPA*. This could have significant performance increases on a map as large as yours (8000x8000, yikes). HPA* operates by grouping regions into linked local clusters and computing the cost for crossing cluster boundaries a priori. Then, the search proceeds in multiple levels: the high-level effort focuses the search by leveraging the pre-computed costs, and the low-level effort determines the exact path that will be used.
此外，存在通过利用运行时环境特征来减少 A* 探索的节点数量的算法.例如，跳转点搜索 (JPS) 利用了网格图(如您正在使用的图)通常表现出对称性这一事实.如果您的世界中的移动具有恒定成本，则 JPS 可以跳过"搜索中的许多节点并大量减少搜索时间.我已经看到它减少了 24 倍的 A* 搜索时间，其他人看到了超过 30 倍的改进.
Also, algorithms exist to reduce the number of nodes explored by A* by exploiting characteristics of the environment at runtime. For instance, Jump Point Search (JPS) exploits the fact that grid graphs (like the one you're using) often exhibit symmetries. If movement in your world has constant cost, JPS can "skip over" many nodes in the search and reduce search times by a considerable amount. I've seen it reduce A* search time by 24x, others have seen over a 30x improvement.
最后一点:据我所知，您使用的是 L1 路径(即 4 基本方向).通过预处理航路点之间的路径并使用差分启发式算法，您可能会受益匪浅.请参阅这篇文章，了解有关 JavaScript 的演示和讨论实施这里.
One final note: From what I can tell, you're using L1 paths (i.e. 4-cardinal directions). You may have much to gain by preprocessing paths between waypoints and using a differential heuristic. See this article for a demo and the discussion of a JavaScript implementation here.
附加链接:
这篇关于大地图实现A星(A*)路径算法，性能低的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
