Fastest cross-platform A* implementation?
With so many implementations available, what is the fastest executing (least CPU intensive, smallest binary), cross-platform (Linux, Mac, Windows, iPhone) A* implementation for C++ using a small grid?
Implementations
Google returns:
- http://www.heyes-jones.com/astar.html (Most links on that site are dead.)
- http://www.grinninglizard.com/MicroPather (Said to be slower than Heyes-Jones'.)
- http://www.ceng.metu.edu.tr/~cuneyt/codes.html (Generic C++ code.)
- http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
- http://opensteer.sourceforge.net/ (Interesting for games, not A*.)
- Stack Overflow on Dijkstra's Algorithm
Any others?
The Wheel
The question, as asked, pertains to reuse (plug into a game), not reinvention (at least not until performance is shown to be an issue). It might turn out that a Dijkstra implementation (or generic pathfinding algorithm) is better suited, or that the fastest implementations are not fast enough. I appreciate the suggestions of alternative algorithms, however the question is not, "Should I roll my own A*?"
Answer
When you have specific bounds that you can work with, you're usually better off writing the algorithm yourself. In particular your small state space lends itself to optimisations that spend memory up-front to reduce CPU time, and the fact that you're using a grid rather than an arbitrary state space allows you to do things like optimise your successor node generation, or be able to treat all partial paths that end on the same grid square as equivalent (which a normal A* search will not and cannot assume).
(PS. OpenSteer, a collection of steering behaviours, is nothing to do with A*, which is a search algorithm, except that you can notionally use one, the other, or both to traverse a space. One isn't a replacement for the other in most reasonable circumstances.)