While trying out the below applet, I saw that this path finding algorithm called Jump Point Search yields significantly faster result than A* and Dijkstra.
http://qiao.github.io/PathFinding.js/visual/
A*: 46 seconds
Dijkstra: 1 minute 39 seconds
Jump Point Search: Less than 3 seconds
Needless to say, I’m quite astounded at the result. From visual representation, Jump Point Search seems to be making a lot of random guesses (probably very intelligent ones) at finding the path (from the block selection at least), but I haven’t yet found a test case where this algorithm yielded worse results than A* and Dijkstra.
How does this algorithm work? How is it so efficient in comparison with A* and Dijkstra?
6
The basic idea is that JPS allows to throw away many candidate paths early, therefore reducing the amount of computations required.
In many maps, multiple paths with the same cost lead to same destination, such as a game map with large open areas. JSP allows pruning those paths.
An in-depth explanation can be found here.
With the latest version of the tool, JPS is actually shown to be slower than A* for many types of graphs, because they now show the JPS recursion as well.
Gray nodes are examined nodes
This is true in the real world, too; while JPS will usually enqueue far-fewer nodes, it usually examines many more. Whether that results in an actual speedup depends on the graph.