林 偉 2001.12
這里的A*優化只是針對網上一些關于A*算法介紹的文章來寫的，至于我接觸過的A*代碼可能都算不上專業級別因此我從這些代碼開始優化也只是覺得這些代碼的優點在于說明算法，而在效率與實用性方面就有些欠缺。
A*是啟發試搜索加動態規劃。具體實現依靠兩個隊列Open隊列和Close隊列。從一點開始探走幾個相鄰的格子如果可以移動且當前移動為起點到哪個格子的歷史最佳方法則把那個格子按照估價值從小到大插入Open隊列里面，幾個方向試探結素后取出估價值最小的節點放入Close再從這里開始試探幾個相鄰的方向同樣放入Open隊列里面，放入Open的條件是1.這步在地圖上面是可以移動的，2.這步所在節點在Open里面并不存在，3.從起點到這步的實際距離比這點的歷史最小距離還短滿足這三個條件就把節點放入Open隊列。具體的算法網友們已經描述的再清楚不過了大致算法如下:
findpath()
{
?? 把S點加入Open隊列（按該點到E點的距離排序+走過的步數從小到大排序）
?? 1、排序隊列Open隊列中距離最小的第一個點出列，并保存入Close隊列中
?? 2、從出列的點出發，分別向4個（或8個）方向中的一個各走出一步
?? 3、并估算第2步所走到位置到目標點的距離，并把該位置按估價距離從小到大排序后并放入Open隊列中
?? 4、如果該點從四個方向上都不能移動，則把該點從Close隊列中刪除
?? 5、回到第一點，直到找到E點則結束
?? 從目標點回溯樹，直到樹根則可以找到最佳路徑，并保存在path[]中
}
|
具體實現和詳細算法可以看這段代碼(sort_queue和store_queue是open和close隊列)
|
我覺得要使它可以勝任即時戰略游戲第一點要改的就是規定搜尋的規模，即限制close_queue的大小，一旦超過大小而并沒有到達終點，則取一個搜尋過的最接近終點的點(從它到終點的估價距離最短)作為搜索的終點。二一旦Open隊列空了無法取出節點時搜索結束沒有找到終點，此時還是按照上面的方法找一個最接近終點的點代替終點。
這樣搜索就不會漫無邊際地進行下去了。上面的程序大家稍微觀察就會發現幾處影響速度的致命地方，啟發試搜索是不變的，而看程序每次加入取出兩個隊列時都要進行繁瑣的內存分配，這是項耗費時間的工作，其次需要檢查是否在隊列中，這點也是很慢的，最后就是保存動態規劃數據(歷史最短距離)的數組進行還原，并且每次尋路都要還原若大的數組，這是無法接受的。
我所說的優化是從數據結構入手解決上面的問題讓Open/Close兩隊列處理時不再涉及內存分配問題，首先建立一個與地圖上面每個節點一一對應的節點數組Node[maph][mapw];Node里面有一個指針Next和Father，Next指相所在隊列的下一個節點，Father指向它的父節點。由于Open/Close兩隊列不可能出現一個節點在某個隊列同時出現兩次的情況因此Open隊列描述時只要讓它指向一個節點地址&Node[y][x]然后讓Node[y][x]的Next指向隊列下一個節點，如果沒有節點則這點的Next為NULL，同樣的道理Close也是這樣描述的如此來看每次搜尋的時候就不必內存分配了，插入節點(x,y)時只要改動Node[maph][mapw]上面的數據和Open/Close兩個指針就輕松搞定了見程序的AddToOpenQueue等幾個函數。在初始化的時候一次性分配**Node為Node[maph][mapw](TAstarNode的定義如下表)Open/Close為兩個TAstarNode指針以后就不再分配內存了，初始化讓Open/Close都等于NULL在Open中加入節點(x,y)就按照普通連表的方法插入&Node[y][x]換而言之，就是讓Open/Close指向Node[maph][mapw]中的某個元素，然后這個元素又指向下一個元素形成鏈表，由于算法中每次加入Open/Close的節點前檢查如果存在了就不再加入因此Open/Close不會有重復的元素。
struct TAstarNode
{
ADWORD Pos; // ((y<<16)|x)初始化時設定以后不變
short ActualCost; // 保存從起點到該節點的實際開銷
short EstimateCost; // 保存此點的估價開銷由JudgeCost函數提供初始化為MAX
TAstarNode *Father; // 此點的父節點
TAstarNode *Next; // 在Open或者Next鏈表中的下一個節點
char Modified; // 1位該節點是否被修改過，2/3位代表是否于Open/Close表
} **Node,*Open,*Close; // Node[maph][mapw]和Open/Close隊列
|
|
右圖為Node[h][w]和Open表的示范，初始化Node時設置EstimateCost為MAX另外需要一個變量描述改動狀態(Modified)，如果改動過最佳記錄則狀態第0位為1，如果在Open隊列中則地1位為1，如果在Close中則第2位為1那么只要通過位運算就可以知道節點和隊列的關系了，另外用一個數組來記錄修改過最佳距離的節點位置，并且依據前面的狀態變量來判斷如果以前已經記錄過就不再記錄了，當路徑搜索完以后就根據這個數組來還原數據了。
請看右邊的搜索試列圖，可以簡單看出OPEN隊列在插入/刪除時并不需要內存分配而只要改變其指針和Node[h][w]中節點的Next指針就行了。這是激動人心的提高，
|
|
?
?
?
?
?
?
有了前面兩段的優化，路徑算法已經省去了許多不必要的工序了，再看下實用性方面，首先判斷地圖是否可以移動不要在算法中直接判斷而最好設置一個虛函數MoveAble(x,y)來實現(程序中我用函數指針代替)，因為在游戲中某塊地圖對于地面單位和空中單位還有水下單位可以移動的情況都不同因此直接操作地圖元素并不是明智的選擇，再者估價函數JudgeCost(x,y)也應該設置成虛函數或者函數指針來實現，畢竟求估價值的方法很靈活，這里不能限制死了。
還有每次尋路搜索哪些方向呢？用DirMask來描述0-7位代表從上開始順時針一圈的八個方向情況，0代表不搜索，1代表搜索，那么四個方向搜索可以用0x55(1010101b)來代替，八個方向可以用0xff來設定，如此一來你可以設定只進行搜索3個方向的尋路，這樣可以滿足一些簡單的尋路任務了，比如RPG中NPC敵人的移動就可以這樣來設定。最后就是范圍問題的設定了，Open表的最大大小可以設置為100-200(四個方向)或200-300(八個方向)而Close表的大小即處理節點的最多數目可以設置成(MapH*MapW)/16這樣的設定在士兵走入一個桶形地形時并不會花費很大的開銷去尋找通路，而是走到桶形地形的尖端。其具體值可以適當調整，當然數值越大搜索就越廣，開銷也就越大(MapH*Map)/16這個數值我自己感覺比較接近星際的尋路特點
其它優化，由于Open隊列中的數據全部是連表插入排序的，當數據多時效率并不會見得高。這時如果還要繼續優化手段也很多，比如建立Hash散列表，或者用二叉樹來代替連表排序，大家可以參考前導公司的寫的A*代碼里面就用了散列表這點很優秀，但它任然擺脫不了大量的內存分配/釋放。因此此處我覺得不怎么高明。
到是估價值的計算方法很多，但是寫的好壞也關系到搜索的規模：坐標差之絕對值乘加權值求和，平方和開方還有些怪的呢，可以看看前導的代碼估價函數是怎么寫的。我看到網上有文章說當前節點到終點的估計距離不能比實際距離大，說什么才能叫做A*算法，否則只能叫A算法(人工智能書上說的)，因為不一定是最短路徑，呵呵但是如果只是滿足估價值小于真實值也不一定就可以找到最短路徑故暫且不論，先看JudgeCost的意義--使搜索更靠近終點，勢必減小JudgeCost將會增加搜索的寬度及規模，增加JudgeCost則使搜索跟快地向終點靠攏。下面是使用不同估價函數的對比：
|
|
|
JudgeCost=abs(dx)+abs(dy)
|
JudgeCost=abs(dx),abs(dy)加權求和
|
上圖兩種估價函數的求法，星號是路徑點是搜索過的節點，當JudgeCost大于真實值時從一個節點出發算法更愿意搜索一個靠終點近的點，換言之JudgeCost越大算法就越買力向終點靠攏，從左右兩副圖可以清楚看到(點擊放大)。所以我們使用坐標差加權求和來處理或者直接求和乘與一個數字(比如8)在地形復雜的時候就更加顯出這種方法的實用性了，良種式子的規模差距還要比上圖嚴重的多。所以通用地用加權求和dx=abs(x-endx),dy=abs(y-endy);if (dx>dy) result =10*dx+6*dy; else result=10*dy+6*dx;就是這個意思，所用的乘10和乘6是試驗證明比較好用的數字了，如此一來搜索的規模就被控制得又減小了，是不可忽視的。
還有幾點要注意的，集體尋路要采用跟隨政策，共用一條路徑，中途遇到移動物分三步走：嘗試加入一個斜方的路徑節點看是否可以饒過;不能就等待移動物體自己走開;到了時間不走再另外搜尋路徑，大場景要預先設定一些路徑節點中轉站再進行遠距離搜索時可以大大提高效率，用方向保存路徑比用坐標保存節省至少1/4的空間。。。。碰到敵人部隊就開槍，自己部隊則可以不走了，或者發送兩條指令給擋住路的士兵的指令隊列1.移開當前位置并等待;2.回到當前位置，這樣可以產生一個一個順序讓路的精彩效果，紅警里面早已有實現:-)
講遠了，那是行軍問題了，前段時間給一個高中生輔導NOI復賽，那小子竟然在講到廣度優先時問了路徑算法，一時興起就寫了這篇文章以及一段三百多行的程序，順便供大家參考:-) 一家之言，歡迎來信討論: skywindt@yeah.net
Copyright LinWei 2001/12/19