最快的跨平台 A* 实施？

有这么多可用的实现，使用小网格的 C++ 执行速度最快（CPU 占用最少、二进制文件最小）、跨平台（Linux、Mac、Windows、iPhone）A* 实现是什么？

实施

谷歌返回：

• http://www.heyes-jones.com/astar.html http://www.heyes-jones.com/astar.html（该网站上的大多数链接都已失效。）
• http://www.grinninglizard.com/MicroPather http://www.grinninglizard.com/MicroPather（据说比 Heyes-Jones 慢。）
• http://www.ceng.metu.edu.tr/~cuneyt/codes.html http://www.ceng.metu.edu.tr/~cuneyt/codes.html（通用 C++ 代码。）
• http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/ http://opensteer.sourceforge.net/（对游戏感兴趣，而不是 A*。）
• Dijkstra 算法的堆栈溢出 https://stackoverflow.com/questions/938338/what-is-the-fastest-dijkstra-implementation-you-know-in-c

还有其他人吗？

车轮

正如所提出的，这个问题涉及重用（插入游戏），而不是重新发明（至少在性能被证明是一个问题之前）。事实可能证明 Dijkstra 实现（或通用寻路算法）更适合，或者最快的实现还不够快。我很欣赏替代算法的建议，但问题不是“我应该自己推出 A* 吗？”

• 乔尔谈软件——非此处发明综合症 http://www.joelonsoftware.com/articles/fog0000000007.html
• 编码恐怖：不要重新发明轮子 http://www.codinghorror.com/blog/archives/001145.html
• 克服“非此发明综合症” http://www.developer.com/open/article.php/3338791/Overcoming-Not-Invented-Here-Syndrome.htm

查看其他寻路算法（例如宽度优先、深度优先、Minimax、Negamax 等）并权衡您的场景的优点和缺点。

升压也拥有 A 星级实施 http://www.boost.org/doc/libs/1_41_0/libs/graph/example/astar-cities.cpp。尝试以下这些说明 http://www.mani.de/backstage/?p=159在 iPhone 上构建 boost，但它可能不适合你：它不是 boost 的“完整端口”，并且可能会出错。

以下内容来自简而言之，算法 http://oreilly.com/catalog/9780596516246（Java，不是 C++，但也许你想移植它）：

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 );
}