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
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 :)