c++ - 最快的跨平台 A* 实现？

Question

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

实现

谷歌返回:

• http://www.heyes-jones.com/astar.html (该网站上的大多数链接都已失效。)
• http://www.grinninglizard.com/MicroPather (据说比 Heyes-Jones 慢。)
• http://www.ceng.metu.edu.tr/~cuneyt/codes.html (通用 C++ 代码。)
• http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/ (对游戏感兴趣，不是 A*。)
• Stack Overflow on Dijkstra's Algorithm

还有其他人吗？

轮子

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

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

Answer 1

查看其他寻路算法(如 Breath-First、Depth-First、Minimax、Negmax 等)并权衡您的场景的正面和负面。

也提升 has an A-star implementation .尝试关注 these instructions在 iPhone 上构建 boost，但它可能不适合你:它不是 boost 的“完整端口”，它可能会出错。

以下来自Algorithms in a Nutshell (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 );
}