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