A* search for pathfinding in games
LoveAStar in action 
- Runs optimally (for a static map, on my Dell XPS 8100, can build 62 consecutive paths on a 25 x 25 square grid while staying above 30 FPS)
- Extendable to any map type (square, rectangles, hexagons, world maps, possibly even 3D spaces)
- Easy to implement. Ships with instructions for "flattening" a map to be used in my version of A*.
Download @ GitHub: 
View the original thread @ Love forums: