关于寻路算法的一些思考（3）：A*算法的实现
概述
剝除代碼，A* 算法非常簡單。算法維護兩個集合：OPEN 集和 CLOSED 集。OPEN 集包含待檢測節點。初始狀態，OPEN集僅包含一個元素：開始位置。CLOSED集包含已檢測節點。初始狀態，CLOSED集為空。從圖形上來看，OPEN集是已訪問區域的邊界，CLOSED集是已訪問區域的內部。每個節點還包含一個指向父節點的指針，以確定追蹤關系。
算法有一個主循環，重復地從OPEN集中取最優節點n（即f值最小的節點）來檢測。如果n是目標節點，那么算法結束；否則，將節點n從OPEN集刪除，并添加到CLOSED集中，然后查看n的所有鄰節點n’。如果鄰節點在CLOSED集，它已被檢測過，則無需再檢測（*）；如果鄰節點在OPEN集，它將會被檢測，則無需此時檢測（*）；否則，將該鄰節點加入OPEN集，設置其父節點為n，到n’的路徑開銷g(n’) = g(n) + movementcost(n, n’)。
這里有更詳細的介紹，其中包含交互圖。
（*）這里我略過了一個小細節。你應當檢查節點的g值，如果新計算得到的路徑開銷比該g值低，那么要重新打開該節點（即重新放入OPEN集）。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | OPEN = priority queue containing START CLOSED = empty set while lowest rank in OPEN is not the GOAL: ??current = remove lowest rank item from OPEN ??add current to CLOSED ??for neighbors of current: ????cost = g(current) + movementcost(current, neighbor) ????if neighbor in OPEN and cost less than g(neighbor): ??????remove neighbor from OPEN, because new path is better ????if neighbor in CLOSED and cost less than g(neighbor): ** ??????remove neighbor from CLOSED ????if neighbor not in OPEN and neighbor not in CLOSED: ??????set g(neighbor) to cost ??????add neighbor to OPEN ??????set priority queue rank to g(neighbor) + h(neighbor) ??????set neighbor's parent to current reconstruct reverse path from goal to start by following parent pointers |
（**）如果啟發式函數值始終是可信的，這種情況就不應當出現。然而在游戲中，經常會得到不可信的啟發式函數。
請點擊這里?查看Python和C++實現.
連通性
如果游戲中起點和終點在圖上根本就不連通，此時A*算法會耗時很久，因為從起點開始，它需要查探所有的節點，直到它意識到根本沒有可行的路徑。因此，我們可以先確定連通分支，僅當起點和終點在同一個連通分支時，才使用A*算法。
性能
A*算法的主循環從一個優先級隊列中讀取節點，分析該節點，然后再向優先級隊列插入新的節點。算法還追蹤哪些節點被訪問過。要提高算法的性能，考慮以下幾方面：
- 能縮減圖的大小嗎？這能減少需處理的節點數目，包括在最終路徑上和不在最終路徑上的節點。可以考慮用導航網格（navigation meshes）代替網格（grids），還可以考慮分層地圖表示（hierarchical map representations）。
- 能提高啟發式函數的準確性嗎？這可以減少不在最終路徑上的節點數目。啟發式函數值越接近真實路徑長度（不是距離），A*算法需要檢查的節點就越少。可以考慮用于網格的啟發式函數，也可以考慮用于一般圖形（包括網格）的ALT（A*，路標Landmarks，三角不等式Triangle Inequality）。
- 能讓優先級隊列更快嗎？考慮使用其他數據結構來構建優先級隊列。也可以參考邊緣搜索的做法，對節點進行批處理。還可以考慮近似排序算法。
- 能讓啟發式函數更快嗎？每個open節點都要調用啟發式函數，可以考慮緩存函數的計算結果，也可以采用內聯調用。
關于網格地圖，我有一些建議。
源代碼和演示
演示（demos）
這些demos運行于瀏覽器端：
- 我寫了一篇帶交互式演示的文章，它是對A*的介紹。
- 我為方形網格、六角形網格、三角網格都編了flash演示。這些demos采用Actionscript 3編寫，點此查看源代碼（其中，Pathfinder.as可視作主算法，Graph.as是圖形的抽象接口）。
- 這里有在公路圖（不是網格）上運行的demos，針對如下算法：A*、廣度優先搜索、Dijkstra算法、貪婪最佳優先搜索。
- 用Javascript寫的A* demo可以改變道路權重，源代碼在github，使用MIT的開源代碼許可。Demo中可以中斷計算，因此可以每幀運行幾個迭代。
- James Macgill 寫的java applet.
- 可以選擇A*或Dijkstra算法的交互式demo.
- 這個demo很好，而且包含javascript源碼
- 這個demo很好，源碼也是可見的。
- 另一個javascript demo
- 這個頁面介紹跳點搜索，其中有在線demo。
- 采用Actionscript的A* 教程，在接近結尾的地方有一個demo。
- 這個demo是javascript寫的，代碼可讀，但是我不知道其源代碼許可是什么。
- 這個A* demo和跳點搜索demo用Unity編寫。
代碼
如果你用C++，一定要看看Mikko Mononen的Recast。
如果你計劃自己實現圖搜索，這里是我的Python和C++實現指南。
我收集了一些源代碼鏈接，但是我還沒有仔細看這些項目，所以也沒有更具體的建議：
- C++:?[1][2][3][4]
- Java:?[1][2][3]
- Javascript:?[1][2][3][4][5]
- Python:?[1]
- Objective C + Cocos2D: parts?[1]?and?[2]
- Lua:?[1][2]more
- Ruby:?[1][2][3]
- C#:?[1][priority queue helper class]
- Unity:?[1]
- Assembly:?[1]
- Actionscript 3 (Flash):?[1][2][3][4][5]
- Flex (Flash):?[1]
- Go:?[1]
- Prolog:?[1]
- Processing:?[1]
集合表示
要表示OPEN集和CLOSED集，你首先能想到什么？如果你像我一樣，可能就會考慮“數組”。你也可能想到“鏈表。有很多數據結構都可以用，我們應當依據需要的操作來選擇一個。
對OPEN集主要執行三個操作：主循環重復地尋找最優節點，然后刪除它；訪問鄰節點時檢查節點是否在集合中；訪問鄰節點時插入新節點。插入和刪除最優都是優先級隊列的典型操作。
數據結構的選擇不僅依賴于操作，還與每個操作運行的次數有關。成員隸屬測試對每個已訪問節點的每個鄰節點運行一次，插入對每個要考慮的節點運行一次，刪除最優對每個已訪問的節點運行一次。大部分考慮的節點都會被訪問，沒有被訪問的是搜索空間的邊緣節點。評估各種數據結構下操作的開銷時，我們應當考慮最大邊緣值（F）。
另外還有第四種操作，這種操作相對較少，但仍需要實現。如果當前檢測的節點已經在OPEN集中（經常出現的情況），并且其f值低于OPEN集中原來的值（很少見的情況），那么需要調整OPEN集中的值。調整操作包括刪除節點（這個節點的f值不是最優的）以及再插入該節點。這兩步操作可以優化為一步移動節點的“增加優先級”操作（也被稱為“降鍵”）。
我的建議：一般最好的選擇是采用二叉堆。如果有現成的二叉堆庫，直接用就可以了。如果沒有，開始就使用有序數組或無序數組，當要求更高的性能時，切換到二叉堆。如果OPEN集中的元素超過10,000個，就要考慮使用更復雜的數據結構，比如桶系統（bucketing system）。
無序數組或鏈表
最簡單的數據結構就是無序數組或鏈表了。成員隸屬測試很慢，要掃描整個結構，時間復雜度為O(F)。插入很快，只需追加到結尾，時間復雜度O(1)。查找最優元素很慢，要掃描整個結構，時間復雜度O(F)。刪除最優元素，采用數組的時間復雜度是O(F)，鏈表是O(1)。“增加優先級”操作花費O(F)找節點，然后花費O(1)改變其值。
有序數組
要想刪除最優元素更快，可以維護一個有序數組。那么可以做二分查找，成員隸屬測試就是O(log F)。插入則很慢，要移動所有元素從而給新元素讓出位置，時間復雜度O(F)。查找最優元素只需取最后一個元素，時間復雜度O(1)。如果我們確保最優元素在數組末尾，刪除最優元素是O(1)。增加優先級操作花O(log F)找節點，花O(F)改變其值或位置。
要確保數組是有序的，以使最優元素在最后。
有序鏈表
有序數組的插入很慢。如果用鏈表，插入就很快。而成員隸屬測試則很慢，需要掃描鏈表，時間復雜度O(F)。插入只需O(1)，但是要用O(F)去找到正確的插入位置。查找最優元素依然很快，最優元素在鏈尾，時間復雜度O(1)。刪除最優元素也是O(1)。增加優先級操作花O(F)找節點，花O(1)改變其值或位置。
二叉堆
二叉堆（不要和內存堆搞混了）是樹型結構，存儲在數組中。大部分樹采用指針指向孩子節點，二叉堆則使用下標確定孩子節點。
采用二叉堆時，成員隸屬測試需要掃描整個結構，時間復雜度O(F)。插入和刪除最優元素都是O(log F)。
增加優先級操作很有技巧性，找節點用O(F)，而增大其優先級竟然只要O(log F)。然而，大部分優先級隊列庫中都沒有該操作。幸運的是，這個操作不是絕對必要的。因此我建議，除非特別需要，不用考慮該操作。我們可以通過向優先級隊列插入新元素來代替增加優先級操作。雖然最終可能一個節點要處理兩次，但是相比實現增加優先級操作，這個開銷比較少。
C++中，可以使用優先級隊列（priority_queue）類，這個類沒有增加優先級方法，也可以使用支持這個操作的Boost庫可變優先級隊列。Python中使用的是heapq庫。
你可以混合使用多種數據結構。采用哈希表或索引數組做成員隸屬測試，采用優先級隊列管理優先級；詳情請看下文的混合部分。
二叉堆的一個變種是d元堆（d-ary heap），其中每個節點的孩子數大于2。插入和增加優先級操作更快一些，而刪除操作則略慢一點。它們可能有更好的緩存性能。
有序跳躍列表（sorted skip lists）
無序鏈表的查找操作很慢，可以使用跳躍列表加快查找速度。對于跳躍列表，如果有排序鍵，成員隸屬測試只要O(log F)。如果知道插入位置，同鏈表一樣，跳躍列表的插入也是O(1)。如果排序鍵是f，查找最優節點很快，是O(1)。刪除一個節點是O(1)。增加優先級操作包括查找節點，刪除該節點，再插入該節點。
如果將地圖位置作為跳躍列表的鍵，成員隸屬測試是O(log F)；執行過成員隸屬測試后，插入是O(1)；查找最優節點是O(F)；刪除一個節點是O(1)。這比無序鏈表要好，因為它的成員隸屬測試更快。
如果將f值作為跳躍列表的鍵，成員隸屬測試是O(F)；插入是O(1)；查找最優節點是O(1)；刪除一個節點是O(1)。這并不比有序鏈表好。
索引數組（indexed arrays）
如果節點集合有限，且大小還可以的話，我們可以采用直接索引結構，用一個索引函數i(n)將每個節點n映射到數組的一個下標。無序數組和有序數組的大小都對應于OPEN集的最大尺寸，而索引數組的數組大小則始終是max(i(n))。如果函數是密集的（即不存在未使用的索引），max(i(n))是圖中的節點數目。只要地圖是網格結構，函數就很容易是密集的。
假設函數i(n)時間復雜度是O(1)，成員隸屬測試就是O(1)，因為只需要檢測Array[i(n)]有沒有數據。插入也是O(1)，因為只需要設置Array[i(n)]。查找和刪除最優節點是O(numnodes)，因為需要查找整個數據結構。增加優先級操作是O(1)。
哈希表
索引數組占用大量內存來存儲所有不在OPEN集中的節點。還有一種選擇是使用哈希表，其中哈希函數h(n)將每個節點n映射到一個哈希碼。保持哈希表大小是N的兩倍，以保證低沖突率。假設h(n)時間復雜度是O(1)，成員隸屬測試和插入預期時間復雜度是O(1)；刪除最優時間復雜度是O(numnodes)，因為需要搜索整個結構；增加優先級操作是O(1)。
伸展樹（splay trees）
堆是基于樹的一種結構，它的操作預期時間復雜度是O(log F)。然而問題是，在A*算法中，常見的操作是，刪除一個低開銷節點（引起O(log F)的操作，因為必須將數值從樹底向上移）后，緊跟著添加多個低開銷節點（引起O(log F)的操作，因為這些值被插入樹底，然后再向上調整到樹根）。這種情況下，預期情況就等價于最壞情況了。如果能找到一種數據結構，使預期情況更好，即使最壞情況沒有變好，A*算法的性能也可以有所提高。
伸展樹是一種自調整的樹型結構。對樹節點的任何訪問，都會將那個節點向樹頂方向移動，最終呈現“緩存”的效果，即不常用節點在底部，從而不會減慢操作。不管伸展樹多大，結果都是這樣，因為操作僅像“緩存大小”一樣慢。在A*算法中，低開銷節點很常用，高開銷節點則不常用，所以可以將那些高開銷節點移到樹底。
采用伸展樹，成員隸屬測試、插入、刪除最優、增加優先級的預期時間復雜度都是O(log F)，最壞情況時間復雜度都是O(F)，然而緩存使最壞情況通常不會發生。然而如果啟發式函數低估開銷，由于Dijkstra算法和A*算法的一些奇特特性，伸展樹可能就不是最好的選擇了。特別地，對于節點n和其鄰節點n’，如果f(n’) >= f(n)，那么所有的插入可能都發生在樹的一側，最終導致樹失衡。我還沒有測試這種情況。
HOT隊列
還有一種數據結構可能比堆要好。通常你可以限制優先級隊列中值的范圍。給定一個范圍限制，往往會有更好的算法。例如，任意值排序時間復雜度是O(N log N)，但是如果有固定范圍，桶排序或基數排序可以在O(N)時間內完成。
我們可以采用HOT（Heap On Top）隊列，以有效利用f(n’) >= f(n)的情況，其中n’是n的一個鄰節點。我們將刪除f(n) 最小的節點n，然后插入滿足下列情況的鄰節點n’：f(n) <= f(n’) <= f(n) + delta，其中delta <= C，常量C是從一個節點到鄰節點的開銷的最大變化。由于f(n)是OPEN集中的最小f值，且所有插入的節點其f值都小于等于f(n) + delta，因此OPEN集中的所有f值都在0到delta的范圍內。就像桶/基數排序一樣，我們可以維護一些“桶”來對OPEN集中的節點排序。
用K個桶，可以將任何O(N)花費降低到其平均值O(N/K)。HOT隊列中，最前面的桶是一個二叉堆，其他的桶都是無序數組。對于最前面的桶，成員隸屬測試預期時間復雜度是O(F/K)，插入和刪除最優時間復雜度是O(log (F/K))。對于其他桶，成員隸屬測試時間復雜度是O(F/K)，插入是O(1)，而刪除最優元素永遠不會發生。如果最前面的桶空了，就要將下一個桶從無序數組轉換為二叉堆。事實證明，這一操作（”heapify”）運行時間是O(F/K)。增加優先級操作最好是處理為O(F/K)的刪除和隨后O(log (F/K))或O(1)的插入。
事實上，A*算法中，大部分放入OPEN集的節點都不需要。HOT隊列結構脫穎而出，因為它只堆化（heapified）需要的元素（開銷不大），不需要的節點都在O(1)時間內被插入。唯一大于O(1)的操作是從堆中刪除節點，其時間復雜度也僅是O(log (F/K))。
此外，如果C小的話，可以設置K = C，那么最小的桶甚至不需要是堆，因為一個桶中的所有節點f值都相同。插入和刪除最優都是O(1)！有個人報告說，當OPEN集最多有800個節點時，HOT隊列和堆一樣快；當最多有1500個節點時，HOT隊列比堆快20%。我預測隨著節點數的增加，HOT隊列會越來越快。
HOT隊列的一個簡單變種是兩級隊列：將好節點放到一種數據結果（堆或數組），將壞節點放入另一種數據結構（數組或鏈表）。因為大部分放入OPEN集的節點都是壞節點，所以它們從不被檢測，而且將它們放入大數組也沒什么壞處。
數據結構比較
要記住，我們不僅要確定漸近（”大O”）行為，也要找一個低常數。要說為什么，我們考慮一個O(log F)的算法和一個O(F)的算法，其中F是堆中的元素個數。那么在你的機器上，第一個算法的實現可能運行10,000 * log(F)秒，而第二個算法的實現可能運行2 * F秒。如果F = 256，那么第一個是80,000秒，而第二個僅需512秒。這種情況下，“更快的”算法用時更長。僅當F > 200,000時算法才開始變得更快。
你不能只比較兩個算法，還需要比較那些算法的實現，還需要知道數據的大致規模。上述例子中，當F > 200,000，第一種實現更快。但如果在游戲中，F始終低于30,000，第二種實現更好。
沒有一種基本數據結構是完全令人滿意的。無序的數組或鏈表，插入代價很低，但成員隸屬測試和刪除代價則很高。有序的數組或鏈表，成員隸屬測試代價稍微低些，刪除代價很低，而插入代價則很高。二叉堆插入和刪除代價稍微低些，成員隸屬測試代價則很高。伸展樹的所有操作代價都稍微低些。HOT隊列插入代價低，刪除代價相當低，成員隸屬測試稍微低些。索引數組，成員隸屬測試和插入代價都很低，但刪除代價異常高，而且也會占用大量內存。哈希表性能同索引數組差不多，不過占用內存通常要少得多，而且刪除代價僅僅是高，而不是異常高。
參閱Lee Killough的優先級隊列頁面，獲得更多有關更先進的優先級隊列的論文和實現。
混合表示
要獲得更好的性能，你會采用混合數據結構。我的A*代碼中，用一個索引數組實現O(1)的成員隸屬測試，用一個二叉堆實現O(log F)的插入和刪除最優元素。至于增加優先級，我用索引數組在O(1)時間內測試我是否真的需要改變優先級（通過在索引數組中存儲g值），偶爾地，如果真的需要增加優先級，我采用二叉堆實現O(F)的增加優先級操作。你也可以用索引數組存儲每個節點在堆中的位置；這樣的話，增加優先級操作時間復雜度是O(log F)。
游戲交互循環
交互式（特別是實時）游戲的需求可能會影響計算最優路徑的能力。相比最好的答案，可能更重要的是有答案。盡管如此，其他所有事都還是一樣的，更短的路徑總是更好的。
通常來說，計算接近起點的路徑比計算接近目標的路徑更為重要。立即開始原理：即使沿一個次優路徑，也要盡快移動單元，然后再計算更好的路徑。實時游戲中，A*的時延往往比吞吐量更重要。
單元要么跟隨直覺（簡單地移動），要么聽從大腦（預先計算路徑）。除非大腦跟他們說不要那樣做，單元都將跟隨直覺行事。（這個方法在大自然中有應用，而且Rodney Brook在機器人架構中也用到了。）我們不是一次性計算所有的路徑，而是每一個或兩個或三個游戲循環，計算一次路徑。此后單元按照直覺開始移動（可能僅僅朝目標沿直線運動），然后重新開始循環，再為單元計算路徑。這種方法可以攤平尋路開銷，而不是一次性全做完。
提前退出
通常A*算法找到目標節點后退出主循環，但也可能提前退出，那么得到的是一段局部路徑。在找到目標節點前任何時刻退出，算法返回到OPEN集當前最優節點的路徑。這個節點最有可能達到目標，因此這是一個合理的去處。
與提前退出類似的情況包括：已經檢測了一定數量的節點；A*算法已經運行了數毫秒；或者檢查的節點距開始位置已經有一段距離。當使用路徑拼接時，較之完整路徑，拼接路徑的限制應當更小。
可中斷算法
如果基本上不需要尋路服務，或者用于存儲OPEN集和CLOSED集的數據結構很小，一種可選的方案是：存儲算法的狀態，退出游戲循環，然后再回到A*算法退出的地方繼續。
群體移動
路徑請求的到達不是均勻分布的。實時戰略游戲中，一個常見的情況是，玩家選擇多個單元，并命令它們向同一個目標移動。這造成了尋路系統的高負載。
這時，為某個單元找到的路徑很有可能對其他單元也有用。那么一種想法是，可以找從單元中心點到目標中心點的路徑P，然后對所有單元都應用這條路徑的大部分，僅僅將前10步和后10步路，替換成為每個單元所找的路。單元i獲得的路徑是：從開始位置到P[10]的路徑，接著是P[10..len(P)-10]的共享路徑，再接著是從P[len(P)-10]到終點的路徑。
另請參閱：將路徑放到一塊叫做路徑拼接，這部分在這些筆記的另一個模塊中有介紹。
為每個單元找的路很短（大概平均10個步驟），長的路都是共享的。大部分路徑只要找一次，然后在所有單元中共享。但如果所有單元都沿同樣的路徑移動，可能無法給用戶留下深刻印象。為了改善系統的這種表象，讓單元沿稍稍不同的路走。一種方法是，單元選擇鄰近位置，自行修改路徑。
另一種方法是，讓單元意識到其它單元的存在（可能隨機選一個“領頭”單元，或者選那個最清楚現狀的單元），并只為領頭單元尋找一條路徑，然后采用集群算法，將單元作為一個群體移動。
有些A*變種，可以處理移動目標，或者對目標理解逐漸加深的情況。其中一些適用于處理多個單元向相同目標移動的情況，它們將A*反過來用（找從目標到單元的路徑）。
改進
如果地圖上基本沒有障礙物，取而代之，增加了地形變化的開銷，那么可以降低實際地形開銷，來計算初始路徑。例如，如果草原開銷是1，丘陵開銷是2，大山開銷是3，那么A*會為了避免在大山上走1步，考慮在草原走3步。而如果假設草原開銷是1，丘陵是1.1，大山是1.2，那么A*在計算最初的路徑時，就不會花很多時間去避免走大山，尋路就更快。（這與精確啟發式函數的成效近似。）知道一條路徑后，單元就立刻開始移動，游戲循環可以繼續。當備用CPU可用時，用真實的移動開銷計算一個更好的路徑。
總結
以上是生活随笔為你收集整理的关于寻路算法的一些思考（3）：A*算法的实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 关于寻路算法的一些思考（2）：Heuri
- 下一篇： 关于寻路算法的一些思考（4）：A* 算法