最快的跨平臺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++。