最快的跨平台的A *的实现？ [英] Fastest cross-platform A* implementation?

问题描述

有了这么多的实现可用，什么是最快的执行（至少CPU密集型的，最小的二进制），跨平台（Linux操作系统，在Mac，Windows，iPhone）A *实现C ++使用小网格？

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?

实现

谷歌返回：

• http://www.heyes-jones.com/astar.html （在该网站上的大多数链接都死了。）
• http://www.grinninglizard.com/MicroPather （据说比Heyes - 琼斯慢。）
• <一个href="http://www.ceng.metu.edu.tr/~cuneyt/$c$cs.html">http://www.ceng.metu.edu.tr/~cuneyt/$c$cs.html （一般C ++ code。）
• <一个href="http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html">http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/ （有趣的游戏，而不是A *。）
• <一个href="http://stackoverflow.com/questions/938338/what-is-the-fastest-dijkstra-implementation-you-know-in-c">Stack溢出的Dijkstra算法

• 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

任何其他方面？

轮子

的问题，如要求，涉及重复使用（插入到游戏），不再造（至少直到性能示是一个问题）。它可能会变成一个Dijkstra算法实现（或通用寻路算法）更适合，或者说，最快的实现是不够快。我AP preciate替代算法的建议，但问题是没有，我应该推出自己的A *？

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

• 乔尔的软件 - 非我发明综合症
• 编码恐怖：不要重新发明轮子
• <一个href="http://www.developer.com/open/article.php/3338791/Overcoming-Not-Invented-Here-Syndrome.htm">Overcoming在非我发明综合症

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

推荐答案

再看看其他的路径查找算法（如呼吸，首先，深度优先，极大极小，Negmax等），体重肯定和否定为您的方案。

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

升压也具有A星实现。试试下面的这些说明在iPhone上打造提升，但它可能无法为你工作：它不是推动的全通，它可能会报错了。

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.

以下是从算法果壳中的（Java的，而不是C ++，但也许你想端口吧）：

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

这篇关于最快的跨平台的A *的实现？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！