8

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 enter image description here

Dijkstra: 1 minute 39 seconds enter image description here

Jump Point Search: Less than 3 seconds enter image description here

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?

  • 1
    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? – yannis May 13 '13 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. – l46kok May 13 '13 at 9:47
  • 6
    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. – yannis May 13 '13 at 9:55
  • @YannisRizos Dang, I should've known better :( – l46kok May 13 '13 at 10:25
  • 1
    it's slow in order to show the progress of the algorithm, not because e.g. "HTML5 is slow", etc. – Steven Lu Jun 16 '13 at 2:07
5

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.

1

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.

JPS Search 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.