Jump Point Search: Better than A* ?

News & General Discussion
1

Check out this demo: PathFinding.js

Typical pathfinding demo right?

Check out “Jump Point Search”.

Here’s a reference I found on it: Jump Point Search | Shortest Path

My thread title isn’t entirely accurate but I just wanted to catch your attention on this.

As A* is an optimization on plain Dijkstra’s, Jump Point Search itself is an optimization on A*.

Taking from the link I gave, here’s the search space for typical A*:

697×699 5.37 KB

Here’s A* with Rectangular Symmetry Reduction. You’ll notice a reduced search space it has to look into to get the path.

697×697 5.56 KB

Now here’s A* with Jump Point Search. Those few red squares are all it needed to get that path.

699×697 5.44 KB

Now I’m sure this won’t be applicable to every situation, but I think Jump Point Search is really good for its purposes.

2

The algorithm itself is much slower but it makes up by not needing needing to run even close the amount of others. Much better than A*!

~lanDog

3

Looks like a nifty way to speed up A* but only when dealing with uniform grids. Hard to apply it to generalized graph search.

And it works best on maps with lots of large open areas… but those maps are exactly the kind that would tend to benefit most from non-uniform navmesh (because you can cover the whole open space with one big poly etc). So I’m not sure how useful it really is in practice.

4

implentation of dijkrast in c #?