Comment by suby | Hacker News Reader

Comment by suby | Hacker News Reader

Parent Full thread

If you're interested in pathfinding, you might enjoy this video. http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-th...

Taken from the description:

In 2011, Harabor and Grastien introduced Jump Point Search (JPS) that achieves up to a 10x speed improvement over A* on uniform cost grids. In the last year, an additional 10x speed improvement to JPS, called JPS+ was independently developed by Steve Rabin as well as Harabor and Grastien. This improved algorithm is over 100x faster than A* on maps with open areas and over 2x faster than A* on worst-case maps. This incredible speed-up is due to pre-computation, eliminating the recursion in JPS and focusing only on touching select relevant nodes during the search.

There is another pathfinding algorithm with smaller pre-computation step and comparable (if not higher) speed. It allows you to do benchmarks on various maps, and it compares itself to other algorithms. I also think it's simpler than JPS.

http://mikolalysenko.github.io/l1-path-finder/www/

Unfortunately, they require large precompute time and static maps. If your maps change, you can't use it.

And 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/

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 that covers some of the optimizations for pathfinding on grids.

Reply on news.ycombinator.com