4 ms·
Unfortunately, they require large precompute time and static maps. If your maps change, you can't use it.
by kefka 11y ago
Unfortunately, they require large precompute time and static maps. If your maps change, you can't use it.
- amitp 11y agoAnd if your maps don't change, you can use precomputation with A* , making it even faster than JPS+. 1. Preprocess the graph to make it smaller. Visibility graphs are a first step, but if you have grid movement you can remove the redundancies (e.g. N-N-W taking you to the same place as W-N-N) to make an even smaller pathfinding graph. Here's a library implementing one of many such algorithms: http://mikolalysenko.github.io/l1-path-finder/www/ http://mikolalysenko.github.io/l1-path-finder/www/ 2. Preprocess the graph to get better distance estimates. The closer your A* heuristic is to the actual distance, the faster A* will run. “Differential heuristics” use the triangle inequality: if you have exact distances to one point L, then you can say dist(A, B) >= dist(L, B) - dist(L, A). There are other approaches too. There's a recent paper http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf http://www.cs.du.edu/~sturtevant/papers/GPPC-2014.pdf that covers some of the optimizations for pathfinding on grids.