最快的跨平台A *实施？

Question

有了这么多的实现，什么是最快的执行（CPU密集度最小，最小的二进制），跨平台（Linux，Mac，Windows，iPhone）使用小型网格的C++实现？

实现

谷歌返回：

• http://www.heyes-jones.com/astar.html（在该网站上大部分链接都死了。）
• http://www.grinninglizard.com/MicroPather（据说比Heyes - 琼斯慢。）
• 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

看看其他的路径寻找算法（如呼吸优先，深度优先，Minimax，Negmax等），并衡量您的情况的积极和消极。

Boost也has an A-star implementation。尝试遵循these instructions以在iPhone上提升效果，但它可能无法适用于您：它不是提升的“完整端口”，可能会出错。

以下是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); 
} 

Answer 2

我建议你自己实现的算法。按照伪代码：A* Search Algorithm，它应该是直截了当的。 “开放”应该作为一个小堆来实施，这也是微不足道的;或者你可以使用STL中的priority_queue。

Answer 3

当您有特定的边界可以使用时，通常您最好自己编写算法。特别是，您的小型状态空间适合优化，预先花费内存以减少CPU时间，并且您使用网格而不是任意状态空间的事实允许您执行诸如优化后续节点生成等事情，或者能够处理所有以相同网格平方结束的部分路径（这是普通的A *搜索不会也不能假设的）。 （PS.OpenSteer，一个转向行为的集合，与A *无关，它是一种搜索算法，除了你可以在概念上使用一个，另一个或两者来遍历一个空间，其中一个并不是这样，吨另在最合理的情况下更换）

Answer 4

我有两点建议一般件：

• 如果您的域名被限制为一个网格，也许你会发现更好的结果通过搜索“寻路”而不是更通用的A *。
• 如果您的域并非严格搜索曲面上的路径，那么如果您花时间改进启发式算法，而不是尝试优化算法本身，则可以为您的工作获得更多好处。

Answer 5

有一个通用的C++在http://www.ceng.metu.edu.tr/~cuneyt/codes.html A *的实现。它看起来像是所有跨平台的标准C++。