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

algorithms

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?

Best Answer

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.

Related Solutions

Javascript – How does one unit test an algorithm

There a couple of technique you can use here:

1) Replace the random number generator with one that produces canned values, and check that the expected values are gotten

   old_random = Math.random;
   Math.random = function() { return 0.5; };
   assert_equals(random_pick(), expected_random_pick);

2) Run the algorithm a whole lots of times, and sum up the results

weights = {0:.1, 2:.5, 6:0.4}
totals = {}
count = 10000;
for(x = 0; x < count; x++)
{
    totals[random_pick(weights)] += 1 / count;
}
assert(totals[0] - weights[0] < 0.1)
assert(totals[2] - weights[2] < 0.1)
assert(totals[6] - weights[6] < 0.1)

The idea here is that if you run the algorithm enough times the law of large numbers will make the totals similar the theoretically expected ones. Then you check that.

How does the Fibonacci exponentiation by squaring algorithm work

It's called the "matrix form" - take a look at Wikipedia

You can compute next Fibonacci number (k+2) by multiplying matrix on a vector of two previous elements (k + 1 and k). Hence, k + 3 can be computed by multiplying matrix on vector of (k + 2 and k + 1). This equals squared matrix multiplied on (k + 1 and k). So on.

Your code simply squares the matrix, taking into account odd powers.

Best Answer

Related Solutions

Javascript – How does one unit test an algorithm

How does the Fibonacci exponentiation by squaring algorithm work

Related Topic