Last Updated: February 25, 2016
·
509
· tenpn

Optimise A* on regular-cost grids with Jump Point Search

This is one of those so-obvious-why-has-no-one-thought-of-it-before moments. Jump Point Search is an A* optimisation for regular-cost grids that avoids pushing cells onto the open list if they're not going to be substantially different from their peers. Here's a great explanation:

http://zerowidth.com/2013/05/05/jump-point-search-explained.html

And here's the very-readable original paper by Harabor and Grastien:

http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-aaai11.pdf