Dear reader,

This site finally got its much-needed overhaul. I tried to keep existing pages at their original URLs.
Should you find an error, please do tell me at [email protected].
Feel free to visit the new website, which may contain more documentation pertaining to your search.

Thank you for visiting, I hope you'll find what you're looking for.

Old blog

 or  go to the new site.

The A* algorithm explained

I just spent the whole day implementing a pathfinding algorithm: A*. The A* algorithm is based on Dijkstra, with the addition of a heuristic (estimation) that allows to favor one path rather than another.

The A* algorithm also has an interesting property: you can easily alter the estimates to make it more accurate or faster (not both, of course ;). That’s why the path depicted above is not actually the shortest one. That’s also why I spent the whole day searching why my implementation of A* was slower than the one I found on the web…

This is all properly explained on Amit’s A* pages. You can also find an example implementation and training material in Java on the Memoization blog. Thanks to these two people for their excellent content :)