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
Written by Andrew Fray
Related protips
Have a fresh tip? Share with Coderwall community!
Post
Post a tip
Best
#Ai
Authors
Sponsored by #native_company# — Learn More
#native_title#
#native_desc#