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?

Improve this question
6
  • 2
    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, 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.
    – TtT23
    May 13, 2013 at 9:47
  • 9
    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, 2013 at 9:55
  • @YannisRizos Dang, I should've known better :(
    – TtT23
    May 13, 2013 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, 2013 at 2:07

2 Answers 2

Reset to default
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.

Improve this answer
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.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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