3 ms·

If you're interested in pathfinding, you might enjoy this video. http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than%20jps+%20goal%20bounding http:/

by suby 11y ago

If you're interested in pathfinding, you might enjoy this video. http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than%20jps+%20goal%20bounding 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.

kefka 11y ago
Unfortunately, they require large precompute time and static maps. If your maps change, you can't use it.
- amitp 11y ago
  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/ 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.
ingenter 11y ago
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/ http://mikolalysenko.github.io/l1-path-finder/www/

by suby 11y ago

kefka 11y ago

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

amitp 11y ago
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/ 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.

ingenter 11y ago

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/ http://mikolalysenko.github.io/l1-path-finder/www/