# How does Jump Point Search algorithm work and why is it so efficient?

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?

• It's clear from your screenshots that A* took 7ms to complete (not 46s), Dijkstra 13ms (not 1m 39s) and JPS 2ms (not 3s). Where did you get your numbers from? Commented May 13, 2013 at 9:19
• By manually timing them with a timer. Human errors might indicate that im off by maybe few seconds or more but there is no way that it took as long as the times mentioned in the applet. Maybe it is referring to something else or it is a bug. Commented May 13, 2013 at 9:47
• Oh my, did you really do that? The times the tool reports are correct: This is how long it took each algorithm to complete. The (significant) delay after that is for the presentation of the algorithms' paths. SVG animation is one of the coolest things in HTML5, but it's (still) slowwww. Commented May 13, 2013 at 9:55
• @YannisRizos Dang, I should've known better :( Commented May 13, 2013 at 10:25
• it's slow in order to show the progress of the algorithm, not because e.g. "HTML5 is slow", etc. Commented Jun 16, 2013 at 2:07

## 2 Answers

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.