|
如何讓A*尋路更快？元帥三顧茅廬，請來南陽二叉堆先生幫忙優(yōu)化尋找“開啟士兵名錄”中最低F值的過程，將尋路速度提高了2到3倍，而且越大的地圖效果越明顯。下面隆重介紹二叉堆先生：
下圖是一個二叉堆的例子，形式上看，它從頂點開始，每個節(jié)點有兩個子節(jié)點，每個子節(jié)點又各自有自己的兩個子節(jié)點；數(shù)值上看，每個節(jié)點的兩個子節(jié)點都比它大或和它相等。
在二叉堆里我們要求：
* 最小的元素在頂端
* 每個元素都比它的父節(jié)點大，或者和父節(jié)點相等。
只要滿足這兩個條件，其他的元素怎么排都行。如上面的例子，最小的元素10在最頂端，第二小的元素20在10的下面，但是第三小的元素24在20的下面，也就是第三層，更大的30反而在第二層。
這樣一“堆”東西我們在程序中怎么用呢？幸運的是，二叉堆可以用一個簡單的一維數(shù)組來存儲，如下圖所示。
假設(shè)一個元素的位置是n（第一個元素的位置為1，而不是通常數(shù)組的第一個索引0），那么它兩個子節(jié)點分別是 n × 2 和 n × 2 + 1 ，父節(jié)點是n除以2取整。比如第3個元素（例中是20）的兩個子節(jié)點位置是6和11，父節(jié)點位置是1。
對于二叉堆我們通常有三種操作：添加、刪除和修改元素：
* 添加元素
首先把要添加的元素加到數(shù)組的末尾，然后和它的父節(jié)點（位置為當(dāng)前位置除以2取整，比如第4個元素的父節(jié)點位置是2，第7個元素的父節(jié)點位置是3）比較，如果新元素比父節(jié)點元素小則交換這兩個元素，然后再和新位置的父節(jié)點比較，直到它的父節(jié)點不再比它大，或者已經(jīng)到達(dá)頂端，及第1的位置。
* 刪除元素
刪除元素的過程類似，只不過添加元素是“向上冒”，而刪除元素是“向下沉”：刪除位置1的元素，把最后一個元素移到最前面，然后和它的兩個子節(jié)點比較，如果較小的子節(jié)點比它小就將它們交換，直到兩個子節(jié)點都比它大。
* 修改元素
和添加元素完全一樣的“向上冒”過程，只是要注意被修改的元素在二叉堆中的位置。
可以看出，使用二叉堆只需很少的幾步就可以完成排序，很大程度上提高了尋路速度。
關(guān)于二叉堆先生需要了解的就是這么多了，下面來看看他怎么幫助元帥工作：
* 每次派出的“預(yù)備士兵”都會獲得一個唯一的編號（ID），一直到尋路結(jié)束，它所有的數(shù)據(jù)包括位置、F值、G值、“父將”編號都將按這個ID存儲。
* 每次有新的“開啟士兵”加入，二叉堆先生將它的編號加入“開啟士兵名錄”并重新排序，使F值最低的ID始終排在最前面
* 當(dāng)有“開啟士兵”晉為“關(guān)閉將軍”，刪除“開啟士兵名錄”的第一個元素并重新排序
* 當(dāng)某個“開啟士兵”的F值被修改，更新其數(shù)據(jù)并重新排序
注意，“開啟士兵名錄”里存的只是人員的編號，數(shù)據(jù)全都另外存儲。不太明白？沒關(guān)系，元帥將在 第三部分 來次真刀實槍的大演兵。
經(jīng)典論壇討論:
http://bbs.blueidea.com/thread-2738527-1-1.html
出處：藍(lán)色理想
責(zé)任編輯：elesa
上一頁 牛刀小試 - A*尋路算法簡介 下一頁 鋒芒畢露 - AS3代碼和示例
◎進(jìn)入論壇Flash專欄版塊參加討論
|
第 1 頁 
第 3 頁 如虎添翼 - 使用二叉堆優(yōu)化
