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:

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

1
14
5/23/2017 11:54:06 AM

Accepted Answer

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 );
}
6
1/19/2013 6:08:14 PM

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


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon