在A*寻路中使用二叉堆
在A*尋路中使用二叉堆
作者：Patrick Lester（2003年4月11日更新）
譯者：Panic 2005年3月28日
譯者序：
??? 這一篇文章，是“A* Pathfinding for Beginners.”，也就是我翻譯的另一篇文章A*尋路初探 GameDev.net的補充，在這篇文章里，作者再一次展現了他闡述復雜話題的非凡能力，用通俗易懂的語句清晰的解釋了容易讓人迷惑的問題。還是那句話，如果你看了這篇文章仍然無法領會作者的意圖，那只能怪我的翻譯太蹩腳了。請參考原文做進一步的理解。
???
??? 這里講解的二叉堆，其實是以堆的形式存在的二叉樹，這個特殊的結構把A*算法對開啟列表的排序需求演繹的出神入化，毫無疑問是A*的最佳拍檔。
???
??? 最后，希望這篇文章對你有所幫助。
???
原文鏈接：http://www.policyalmanac.org/games/binaryHeaps.htm?? [已經無法打開]
以下是翻譯的正文：
這篇文章是我的主題文章“A* Pathfinding for Beginners.”的補充。在讀這篇文章之前，你應該先讀那一篇文章，或者對A*做透徹的理解。
A*算法中最緩慢的部分就是在開啟列表中尋找F值最低的節點或者方格。取決于地圖的大小，你可能有十幾，成百甚至上千的節點需要在某個時候使用A*搜索。無需多講，反復搜索這么大的列表會嚴重拖慢整個過程。然而，這些時間在極大程度上受你存儲列表的方式影響。
有序和無序的開啟列表：簡單的方法
最簡單的方法就是順序存儲每個節點，然后每次需要提取最低耗費元素的時候都遍歷整個列表。這提供可快速的插入速度，但是移除速度可能是最慢的，因為你需要檢查每個元素才能夠確定哪個才是F值最低的。
通常你可以保持你列表處于有序狀態來提升效率。這花費了稍微多一點的預處理時間，因為你每次插入新元素都必須把他們放在恰當的位置。不過移除元素倒是很快。你只要移除第一個元素就可以了，它一定是F值最低的。
有很多方法可以保持你的數據有序（選擇排序，冒泡排序，快速排序，等等）并且你可以用你最熟悉的搜索引擎找到這方面的文章。不過我們至少可以先提幾種想法。最簡單的方法可能是，當你需要添加新元素的時候，從列表開始的地方，依次比較每個元素的F值和要插入的F值的大小。一旦找到一個相等或者更高的F值，你就可以把新元素插入到列表中那個元素的前面。取決于你使用的計算機于亞，使用class或者struct實現的鏈表可能是不錯的方法。
這種方法可以通過保持列表中所有元素的平均值來得到改進，使用這個平均值來決定是從頭（如上所說）還是從尾開始處理。總的說來，比平均F值低的新元素將被從頭開始處理，而比平均F值高的則從末尾開始。這種方法可以節省一半的時間。
復雜一些，但是更快的方法是把這一想法提高到新的層次使用快速排序，它基本上是從比較新元素和列表中間元素的F值開始。如果新元素的F值低，你接著把它和1/4處元素進行比較，如果還是更低你就比較它和1/8處的元素，如此這般，不斷的折半你的列表并且比較，直到找到合適的位置。這個描述很簡單，你可能會想到網上尋找快速排序的更多資料。這比至此描述的任何方法都快。
二叉堆
二叉堆和剛才說的快速排序很像，經常被那些苛求A*速度的人使用。根據我的經驗，二叉堆平均提高尋路速度2-3倍，對于包含大量節點的地圖(也就是說100×100節點或者更多）效果更明顯。友情提醒，然而二叉堆很難處理，除非你使用含有大量節點的地圖，速度至關重要，否則不值得為它頭痛。
文章其他的部分深入說明了二叉堆和它在A*算法中的用途。如果你對我的文章存有疑惑，在文章末尾進一步閱讀的小節中提供了更多的觀點。
仍然有興趣？好，我們繼續。。。
在有序列表中，每個元素都按照由低到高或由高到低的順序保存在恰當的位置。這很有用，但是還不夠。事實上，我們并不關心數字127是否比128在更低的位置上。我們只是想讓F值最低的元素能放在列表頂端以便容易訪問。列表的其他部分即使是混亂的也不必在意。列表的其他部分只有在我們需要另一個F值最低的元素的時候，才有必要保持有序。
基本上，我們真正需要的是一個“堆”，確切的說，是個二叉堆。二叉堆是一組元素，其中最大或者最小（取決于需要）的元素在堆頂端。既然我們要尋找F值最小的元素，我們就把它放在堆頂端。這個元素有兩個子節點，每個的F值等于，或者略高于這個元素。每個子節點又有兩個子節點，他們又有和他們相等或略高的子節點。。。依次類推。這里是一個堆可能的樣子：
注意，F值最低的元素(10)在最頂端，第二低的元素(20)是它的一個子節點。可是，其后就沒有任何疑問了。在這個特定的二叉堆里，第三低的元素是24，它離堆頂有兩步的距離，它比30小，但是30卻在左側離堆頂一步之遙的地方。簡單的堆放，其他的元素在堆的哪個位置并不重要，每個單獨的元素只需要和它的父節點相等或者更高，而和它的兩個子節點相比，更低或者相等，這就可以了。這些條件在這里都完全符合，所以這是個有效的二叉堆。
很好，你可能會想，這的確有趣，但是如何把它付諸實施呢？嗯，關于二叉堆的一個有趣的事實是，你可以簡單的把它存儲在一個一維數組中。
在這個數組中，堆頂端的元素應該是數組的第一個元素(是下標1而不是0)。兩個子節點會在2和3的位置。這兩個節點的4個子節點應該在4－7的位置。
總的來說，任何元素的兩個子節點可以通過把當前元素的位置乘以2（得到第一個子節點）和乘2加1（得到第二個子節點）來得到。就這樣，例如堆中第三個元素（數值是20）的兩個子節點，可以在位置2*3 = 6和2*3 +1 = 7這兩個位置找到。那兩個位置上的數字非別是30和24，當你查看堆的時候就能理解。
你其實不必要知道這些，除了表明堆中沒有斷層之外知道這些沒有任何價值。7個元素，就完整的填滿了一個三層堆的每一層。然而這并不是必要的。為了讓我們的堆有效，我們只需要填充最底層之上的每一行。最底層自身可以是任意數值的元素，同時，新的元素按照從左到右的順序添加。這篇文章描述的方法就是這樣做的，所以你不必多慮。
往堆中添加新元素
當我們實際在尋路算法中使用二叉堆的時候，還需要考慮更多，但是現在我們只是學習一下如何使用二叉堆。我跳過這部分以便更容易理解基本的東西。我會在文章后面的部分給出處理這一切的完整公式，但了解這些細節仍然十分重要。
大致的，為了往堆里添加元素，我們把它放在數組的末尾。然后和它在 當前位置/2 處的父節點比較，分數部分被圓整。如果新元素的F值更低，我們就交換這兩個元素。然后我們比較這個元素和它的新父節點，在 （當前位置）/2 ，小數部分圓整，的地方。如果它的F值更低，我們再次交換。我們重復這個過程直到這個元素不再比它的父節點低，或者這個元素已經到達頂端，處于數組的位置1。
我們來看如何把一個F值為17的元素添加到已經存在的堆中。我們的堆里現在有7個元素，新元素將被添加到第8個位置。這就是堆看起來的樣子，新元素被加了下劃線。
10 30 20 34 38 30 24 17
接下來我們比較它和它的父節點，在 8/2 也就是 4的位置上。位置4當前元素的F值是34。既然17比34低，我們交換兩元素的位置。現在我們的堆看起來是這樣的:
10 30 20 17 38 30 24 34
然后我們把它和新的父節點比較。因為我們在位置4，我們就把它和 4/2 = 2 這個位置上的元素比較。那個元素的F值是30。因為17比30低，我們再次交換，現在堆看起來是這樣的：
10 17 20 30 38 30 24 34
接著我們比較它和新的父節點。現在我們在第二個位置，我們把它和 2/2 = 1，也就是堆頂端的比較。這次，17不比10更低，我們停止，堆保持成現在的樣子。
從堆中刪除元素
從堆中刪除元素是個類似的過程，但是差不多是反過來的。首先，我們刪除位置1的元素，現在它空了。然后，我們取堆的最后一個元素，移動到位置1。在堆中，這是結束的條件。以前的末元素被加了下劃線。
34 17 20 30 38 30 24
然后我們比較它和兩個子節點，它們分別在位置(當前位置*2)和(當前位置* 2 + 1)。如果它比兩個子節點的F值都低，就保持原位。反之，就把它和較低的子節點交換。那么，在這里，該元素的兩個子節點的位置在 1 * 2 = 2和 1*2 + 1 = 3。顯然，34不比任何一個子節點低，所以我們把它和較低的子節點，也就是17，交換。結果看起來是這樣：
17 34 20 30 38 30 24
接著我們把它和新的子節點比較，它們在 2*2 = 4，和2*2 + 1 = 5的位置上。它不比任何一個子節點低，所以我們把它和較低的一個子節點交換（位置4上的30）。現在是這樣：
17 30 20 34 38 30 24
最后一次，我們比較它和新的子節點。照例，子節點在位置 4*2 = 8和4*2+1 = 9的位置上。但是那些位置上并沒有元素，因為列表沒那么長。我們已經到達了堆的底端，所以我們停下來。
二叉堆為什么這么快？
現在你知道了堆基本的插入和刪除方法，你應該明白為什么它比其他方法，比如說插入排序更快。假設你有個有1000個節點的開啟列表，在一格有很多節點的相當大的地圖上，這不是不可能（記住，即使是100×100的地圖，上面也有10,000個節點）。如果你使用插入排序，從起點開始，到找到新元素恰當的位置，在把新元素插入之前，平均需要做500次比較。
使用二叉堆，你從底端開始，可能只要1－3次比較就能把新元素插入到正確的位置。你還需要9次比較用來從開啟列表中移除一個元素，同時保持堆仍然有序。在A*中，你通常每次只需要移除一個元素(F值最低的元素)，在任意位置添加0到5個新節點(就像主文章里描述的2D尋路)。這總共花費的時間大約是同樣數量節點進行插入排序的1%。差別隨你地圖的增大(也就是節點更多)呈幾何增長。地圖越小，就越沒優勢，這也是為什么你的地圖和節點越少，二叉堆的價值就越低的原因。
順便，使用二叉堆并不意味著你的尋路算法會快100倍。在下面還講了一些棘手的問題。額外的，A*不僅僅是為開啟列表排序。然而，根據我的經驗，用二叉堆在大部分場合可以提高2－3倍的速度，更長的路徑，速度提高的更多。
創建開啟列表數組
現在我們了解了二叉堆，那么如何使用它呢？首先要做的是構造我們的一維數組。為此，我們先要確定它的大小。一般來說，列表大小不會超過地圖上的節點總數（在最壞的情況下，我們搜索整個地圖尋找路徑）。在一個方形二維地圖中，就如我的主文章中描述的，我們的節點不超過 地圖寬 × 地圖高。那么我們的一維數組就是那個大小。在這個例子里，我們叫這個數組 openList()。堆最頂端的元素被存儲在openList(1)，第二個元素在openList(2)，依此類推。
使用指針
現在我們有了正確大小的數組，幾乎可以開始用來尋路了。不過，在進一步的添加或者刪除操作之前，我們再看看原始的堆。
現在，它只是個F值的列表，而且已經被正確安排。但是我們忽略了一個重要的元素。是的，我們有一系列的F值按順序保存在堆里，但是我們沒有他們代表哪一格的任何線索。基本上，我們只是知道10是堆中最低的F值。但那指的是那個格子？
為了解決這個問題，我們必須改變數組中元素的值。我們不儲存排序好的F值，取而代之的是保存關聯到地圖網格的唯一標志。我的方法是為每個新加入堆的元素創建一個唯一ID叫做squaresChecked。每次往開啟列表中添加新元素，我們給squaresChecked增加1，并把它作為列表中新元素的唯一ID。第一個添加進列表的是#1，第二個是#2，依此類推。
最后，我們把具體的F值存儲在單獨的一維數組中，我把它叫做 Dcost()。和開啟列表相同，我們把它的大小定為(地圖寬 x 地圖高)。我們同時存儲節點的x和y坐標在類似的一維數組中，叫做 openX() 和 openY()。看起來就像下面的圖：
盡管這看起來有點復雜，但它和前面講的堆是相同的。只是儲存的信息更多了。
#5元素，有最低的F值10，仍然在堆頂，在一維數組的第一列。不過現在我們在堆里存儲它的唯一ID 5，而不是它的F值。換句話說，openList(1) = 5。這個唯一數值用來查找元素的F值，以及地圖x和y坐標。這個元素的F值是Fcost(5) = 10，x坐標是openX(5) = 12，y坐標是openY(5) = 22。
頂端的元素有兩個子節點，數值是2和6，他們的F值是30和20，分別存儲在opneList()中2和3的位置，等等。基本上，我們的堆和以前相同，只是多了一些關于元素在地圖上的位置，F值是多少，等等的信息。
在堆中添加新元素(第二部分）
好，我們實際的把這種技術用在A*尋路的開啟列表排序中。我們使用的技術和先前描述的大體相同。
我們添加到開啟列表中的第一個元素，一般是起始節點，被分配了一個數值是1的唯一ID，然后放入開啟列表的#1位置。也就是 openList(1) = 1.我們還跟蹤開啟列表中元素的數量，現在也是1。我們把它保存在名為numberOfOpenListItems的變量里。
當我們往開啟列表中添加新元素的時候，首先我們計算G，H和F值，就如在主文章中所述。然后按照前面講的方法把他們添加進開啟列表。
首先我們給新元素分配一格唯一 ID號，也就是squaresChecked變量的用途。每次我們添加一個新節點，就給這個變量加1，然后把它的數值分配給新節點。然后給numberOfOpenListItems加1。然后把它添加到開啟列表的底部，所有這些可以翻譯成：
? squaresChecked = squaresChecked +1
? numberOfOpenListItems = numberOfOpenListItems+1
? openList(numberOfOpenListItems) = squaresChecked
然后我們依次把它和父節點比較直到它到達正確的位置。這是這些操作的代碼：
? m = numberOfOpenListItems
? While m <> 1 ;While item hasn't bubbled to the top (m=1)
???? ;Check if child is <= parent. If so, swap them.
???? If Fcost(openList(m)) <= Fcost(openList(m/2)) Then
??????? temp = openList(m/2)
??????? openList(m/2) = openList(m)
??????? openList(m) = temp
??????? m = m/2
???? Else
??????? Exit ;exit the while/wend loop
???? End If
? Wend
從堆中刪除元素(第二部分)
無疑，我們不能只建立堆，當不需要的時候，我們也要從堆中刪除元素。特別的，在A*尋路中，我們在檢查和切換到關閉列表之后，從堆頂需要刪除F值最低的元素。
如前所述，你從把末元素移動到堆頂開始，然后把堆中的元素總數減1。偽代碼是這樣：
? openList(1) = openList(numberOfOpenListItems)
? numberOfOpenListItems = numberOfOpenListItems - 1
接著我們需要依次比較它和兩個子節點的數值。如果它的F值更高，我們就把它和更低F值的子節點交換。然后我們把它和新的子節點比較（看它是否更低）。如果它的F值比兩個子節點更高，我們把它和較低的一個交換。我們重復這個過程直到找到它的正確位置，這可能會一直持續到堆底，但并不是完全必要。偽代碼看起來是這樣：
v = 1
;Repeat the following until the item sinks to its proper spot in the binary heap.
Repeat
? u = v
? If 2*u+1 <= numberOfOpenListItems ;if both children exist
??? ;Select the lowest of the two children.
??? If Fcost(openList(u)) >= Fcost(openList(2*u))then v = 2*u ;SEE NOTE BELOW
??? If Fcost(openList(v)) >= Fcost(openList(2*u+1))then v = 2*u+1 ;SEE NOTE BELOW
? Else If 2*u <= numberOfOpenListItems ;if only child #1 exists
??? ;Check if the F cost is greater than the child
??? If Fcost(openList(u)) >= Fcost(openList(2*u))then v = 2*u
? End If
? If u <> v then ; If parent's F > one or both of its children, swap them
??? temp = openList(u)
??? openList(u) = openList(v)
??? openList(v) = temp
? Else
??? Exit ;if item <= both children, exit repeat/forever loop
? End if
Forever ;Repeat forever
請注意兩行代碼中粗體(紅色)的u和v的數值。在第二行，你應該使用 v而不是u，這不是很顯而易見。這確保了你把它和較低的子節點交換。如果做錯會造成不完整的堆，完全打亂你的尋路。
對開啟列表的元素重排序
就如在主文章中描述的，有時候你會發現現有的開啟列表中的元素會改變。這種情況發生的時候，我們不必要取出這個元素重新來過。只要從當前位置開始，用它新的（更低的）F值和它的父節點比較。如果它的F值低到足以替換它的父節點，你就把它替換掉（不然你就會得到一個錯誤的堆，一切都完了）。一般，你使用和“在堆中添加新元素”的小節中相同的代碼，并做額外處理如下：
不幸的是，因為你的數據是在一個龐大，無序的堆里，你需要遍歷整個堆查找先有開啟列表中的元素。你主要要查找由openX(openList()) 和openY(openList())獲取的確切坐標的格子，找到之后，你就可以從那一點開始，像往常那樣做必要的比較和交換。
最后的注解
好了，我希望你仍然能讀懂，沒有被搞昏頭。如果你不著急，并且希望在自己的尋路算法中使用二叉堆，那么這就是我的建議。
首先，把二叉堆放一放。把注意力放在你的A*尋路算法上，使用簡單點的排序算法，保證算法正常工作沒有bug。一開始你并不需要它很快速，你只需要它能工作。
其次，在你把二叉堆添加到代碼中之前，試著把二叉堆寫成獨立的功能，用適當的方法添加和刪除元素。確保你寫的程序中，可以看到整個過程中每一步的操作，也許可以把結果打印在屏幕上，如果你愿意。你還得包含一些中途退出的代碼，以便在必要的時候結束整個流程。如果二叉堆寫的不對，你很容易就會陷入到無限循環中。
一旦你確信兩個程序都運行無誤，備份他們，然后開始把他們結合起來。除非你比我還聰明，否則一開始你難免遇到麻煩。輸出都是些錯誤信息 并且/或者 看到尋路者因為bug走出各種怪異的方向。不過最終你會搞定一切。
進一步閱讀
和以往一樣，網上有很多其他的關于這個話題的好文章。這里有些入門的。第一篇用圖示。第二篇說明了怎么用一個簡單的數組（如果我的說明很麻煩的話）實現二叉堆。第三篇探討了尋路算法中堆的一般用途。
??? * http://www.onthenet.com.au/~grahamis/int2008/week11/lect11.html
??? * http://www.purists.org/pqueue/
??? * http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#S5
最后，你可能想看看我的尋路代碼，這里可以找到。它和文中的偽代碼相互照應，注釋詳盡，有C++和Blitz兩個版本，Blitz是一個比其他大多數都容易理解的語言。不使用C++的程序員會很容易理解Basic版本的代碼。
好，就這么多。
現在，照例，祝你好運。
總結
以上是生活随笔為你收集整理的在A*寻路中使用二叉堆的全部內容，希望文章能夠幫你解決所遇到的問題。
