在大地图中实现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
当我使用A star Pathfinder.java计算地图上从一个点到另一点的路线时，地图的尺寸很大，尺寸约为8000x8000.
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进行计算，并在大型地图(8000x8000)中使用，性能/计算速度非常低/很慢(效率不高).我尝试将计算结果乘以100增加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 star算法或其他建议来解决此问题的方法来提高路线计算性能?我需要帮助来解决问题.
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.
此外，如果世界是静态的(即已知布局是先验)，则可以预先计算很多信息以帮助加快搜索速度.存在几种算法可以完成此任务. 沼泽是一种预先计算易于被不必要搜索的区域的方法. (即沼泽).除非进入或离开沼泽，否则无需在运行时搜索区域.沼泽的加速很大程度上取决于世界的地形.更具欺骗性的地图(即倾向于将搜索引向沼泽地的地图)将大有裨益.
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，yikes)上，这可能会显着提高性能. 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可以跳过"搜索中的许多节点，并大大减少搜索时间.我看过它使A *搜索时间减少了24倍，其他人则看到了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.
其他链接:
- 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
这篇关于在大地图中实现A星(A *)路径算法，性能低下的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
