Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
    
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 Rizos 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
5  
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 Rizos May 13 '13 at 9:55
    
@YannisRizos Dang, I should've known better :( –  l46kok May 13 '13 at 10:25
    
@YannisRizos So either the API, the code or both is really, really terrible to take that long - on a side not JPS draws barely anything, which can explain the time, while the others cover the screen, though I can't quite explain the time diff between A* and Dijkstra - only around 20 block difference, takes twice as long. Question still holds though, although not quite to such a large extent - 7ms VS 13ms VS 2ms. –  Dukeling May 13 '13 at 12:54

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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