Fastest cross-platform A* implementation?

Question

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*?"

• Joel on Software - Not Invented Here Syndrome
• Coding Horror: Don't Reinvent the Wheel
• Overcoming the "Not Invented Here Syndrome"

Answer 1

Look at other path-finding algorithms (like Breath-First, Depth-First, Minimax, Negmax etc.) and weigh the positives and negatives for your scenario.

Boost also has an A-star implementation. Try following these instructions to build boost on iPhone, but it might not work for you: it is not a "full port" of boost and it might error out.

The following is from Algorithms in a Nutshell (Java, not C++ but maybe you'd like to port it):

public Solution search( INode initial, INode goal ) {
  // Start from the initial state
  INodeSet open = StateStorageFactory.create( StateStorageFactory.TREE );
  INode copy = initial.copy();
  scoringFunction.score( copy );
  open.insert( copy );

  // Use Hashtable to store states we have already visited.
  INodeSet closed = StateStorageFactory.create( StateStorageFactory. HASH );
  while( !open.isEmpty() ) {
    // Remove node with smallest evaluation function and mark closed.
    INode n = open.remove();

    closed.insert( n );

    // Return if goal state reached.
    if( n.equals( goal ) ) { return new Solution( initial, n ); }

    // Compute successor moves and update OPEN/CLOSED lists.
    DepthTransition trans = (DepthTransition)n.storedData();
    int depth = 1;

    if( trans ! = null ) { depth = trans.depth + 1; }

    DoubleLinkedList<IMove> moves = n.validMoves();

    for( Iterator<IMove> it = moves.iterator(); it.hasNext(); ) {
      IMove move = it.next();

      // Make move and score the new board state.
      INode successor = n.copy();
      move.execute( successor );

      // Record previous move for solution trace and compute
      // evaluation function to see if we have improved upon
      // a state already closed
      successor.storedData( new DepthTransition( move, n, depth ) );
      scoringFunction.score( successor );

      // If already visited, see if we are revisiting with lower
      // cost. If not, just continue; otherwise, pull out of closed
      // and process
      INode past = closed.contains( successor );

      if( past ! = null ) {
        if( successor.score() >= past.score() ) {
          continue;
        }

        // we revisit with our lower cost.
        closed.remove( past );
      }

      // place into open.
      open.insert( successor );
    }
  }

  // No solution.
  return new Solution( initial, goal, false );
}

Answer 2

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

Answer 3

I have two general pieces of advice:

• If your domain is restricted to a grid, maybe you will find better results by searching "pathfinding" rather the more generic A*.
• If your domain is not strictly searching paths along a surface, you could get more benefits for your effort if you spend your time improving your heuristics rather than trying to optimise the algorithm itself.

Answer 4

I suggest you implement the algorithm by yourself. Follow the pseudo code at: A* Search Algorithm and it should be straight forward. The "openset" should be implemented as a min-heap, which is also trivial; or you can use priority_queue from STL.

Answer 5

There's a generic C++ A* implementation at http://www.ceng.metu.edu.tr/~cuneyt/codes.html. It looks like it's all cross-platform standard C++.