關(guān)于A*算法實(shí)用性優(yōu)化的個(gè)人想法
林 偉 2001.12

　　這里的A*優(yōu)化只是針對網(wǎng)上一些關(guān)于A*算法介紹的文章來寫的，至于我接觸過的A*代碼可能都算不上專業(yè)級別因此我從這些代碼開始優(yōu)化也只是覺得這些代碼的優(yōu)點(diǎn)在于說明算法，而在效率與實(shí)用性方面就有些欠缺。

　　A*是啟發(fā)試搜索加動態(tài)規(guī)劃。具體實(shí)現(xiàn)依靠兩個(gè)隊(duì)列Open隊(duì)列和Close隊(duì)列。從一點(diǎn)開始探走幾個(gè)相鄰的格子如果可以移動且當(dāng)前移動為起點(diǎn)到哪個(gè)格子的歷史最佳方法則把那個(gè)格子按照估價(jià)值從小到大插入Open隊(duì)列里面，幾個(gè)方向試探結(jié)素后取出估價(jià)值最小的節(jié)點(diǎn)放入Close再從這里開始試探幾個(gè)相鄰的方向同樣放入Open隊(duì)列里面，放入Open的條件是1.這步在地圖上面是可以移動的，2.這步所在節(jié)點(diǎn)在Open里面并不存在，3.從起點(diǎn)到這步的實(shí)際距離比這點(diǎn)的歷史最小距離還短滿足這三個(gè)條件就把節(jié)點(diǎn)放入Open隊(duì)列。具體的算法網(wǎng)友們已經(jīng)描述的再清楚不過了大致算法如下:

findpath()
{ 
  　把S點(diǎn)加入Open隊(duì)列（按該點(diǎn)到E點(diǎn)的距離排序+走過的步數(shù)從小到大排序）
  　1、排序隊(duì)列Open隊(duì)列中距離最小的第一個(gè)點(diǎn)出列，并保存入Close隊(duì)列中
  　2、從出列的點(diǎn)出發(fā)，分別向4個(gè)（或8個(gè)）方向中的一個(gè)各走出一步
  　3、并估算第2步所走到位置到目標(biāo)點(diǎn)的距離，并把該位置按估價(jià)距離從小到大排序后并放入Open隊(duì)列中
  　4、如果該點(diǎn)從四個(gè)方向上都不能移動，則把該點(diǎn)從Close隊(duì)列中刪除
  　5、回到第一點(diǎn)，直到找到E點(diǎn)則結(jié)束
  　從目標(biāo)點(diǎn)回溯樹，直到樹根則可以找到最佳路徑，并保存在path[]中
} 
具體實(shí)現(xiàn)和詳細(xì)算法可以看這段代碼(sort_queue和store_queue是open和close隊(duì)列) 

　　我覺得要使它可以勝任即時(shí)戰(zhàn)略游戲第一點(diǎn)要改的就是規(guī)定搜尋的規(guī)模，即限制close_queue的大小，一旦超過大小而并沒有到達(dá)終點(diǎn)，則取一個(gè)搜尋過的最接近終點(diǎn)的點(diǎn)(從它到終點(diǎn)的估價(jià)距離最短)作為搜索的終點(diǎn)。二一旦Open隊(duì)列空了無法取出節(jié)點(diǎn)時(shí)搜索結(jié)束沒有找到終點(diǎn)，此時(shí)還是按照上面的方法找一個(gè)最接近終點(diǎn)的點(diǎn)代替終點(diǎn)。

　　
　　這樣搜索就不會漫無邊際地進(jìn)行下去了。上面的程序大家稍微觀察就會發(fā)現(xiàn)幾處影響速度的致命地方，啟發(fā)試搜索是不變的，而看程序每次加入取出兩個(gè)隊(duì)列時(shí)都要進(jìn)行繁瑣的內(nèi)存分配，這是項(xiàng)耗費(fèi)時(shí)間的工作，其次需要檢查是否在隊(duì)列中，這點(diǎn)也是很慢的，最后就是保存動態(tài)規(guī)劃數(shù)據(jù)(歷史最短距離)的數(shù)組進(jìn)行還原，并且每次尋路都要還原若大的數(shù)組，這是無法接受的。

　　我所說的優(yōu)化是從數(shù)據(jù)結(jié)構(gòu)入手解決上面的問題讓Open/Close兩隊(duì)列處理時(shí)不再涉及內(nèi)存分配問題，首先建立一個(gè)與地圖上面每個(gè)節(jié)點(diǎn)一一對應(yīng)的節(jié)點(diǎn)數(shù)組Node[maph][mapw];Node里面有一個(gè)指針Next和Father，Next指相所在隊(duì)列的下一個(gè)節(jié)點(diǎn)，F(xiàn)ather指向它的父節(jié)點(diǎn)。由于Open/Close兩隊(duì)列不可能出現(xiàn)一個(gè)節(jié)點(diǎn)在某個(gè)隊(duì)列同時(shí)出現(xiàn)兩次的情況因此Open隊(duì)列描述時(shí)只要讓它指向一個(gè)節(jié)點(diǎn)地址&Node[y][x]然后讓Node[y][x]的Next指向隊(duì)列下一個(gè)節(jié)點(diǎn)，如果沒有節(jié)點(diǎn)則這點(diǎn)的Next為NULL，同樣的道理Close也是這樣描述的如此來看每次搜尋的時(shí)候就不必內(nèi)存分配了，插入節(jié)點(diǎn)(x,y)時(shí)只要改動Node[maph][mapw]上面的數(shù)據(jù)和Open/Close兩個(gè)指針就輕松搞定了見程序的AddToOpenQueue等幾個(gè)函數(shù)。在初始化的時(shí)候一次性分配**Node為Node[maph][mapw](TAstarNode的定義如下表)Open/Close為兩個(gè)TAstarNode指針以后就不再分配內(nèi)存了，初始化讓Open/Close都等于NULL在Open中加入節(jié)點(diǎn)(x,y)就按照普通連表的方法插入&Node[y][x]換而言之，就是讓Open/Close指向Node[maph][mapw]中的某個(gè)元素，然后這個(gè)元素又指向下一個(gè)元素形成鏈表，由于算法中每次加入Open/Close的節(jié)點(diǎn)前檢查如果存在了就不再加入因此Open/Close不會有重復(fù)的元素。

struct TAstarNode
{
　ADWORD Pos;　　　　　// ((y<<16)|x)初始化時(shí)設(shè)定以后不變
　short ActualCost;　　// 保存從起點(diǎn)到該節(jié)點(diǎn)的實(shí)際開銷
　short EstimateCost;　// 保存此點(diǎn)的估價(jià)開銷由JudgeCost函數(shù)提供初始化為MAX
　TAstarNode *Father;　// 此點(diǎn)的父節(jié)點(diǎn)
　TAstarNode *Next;　　// 在Open或者Next鏈表中的下一個(gè)節(jié)點(diǎn)
　char Modified;　　　 // 1位該節(jié)點(diǎn)是否被修改過，2/3位代表是否于Open/Close表
} **Node,*Open,*Close; // Node[maph][mapw]和Open/Close隊(duì)列 

　　右圖為Node[h][w]和Open表的示范，初始化Node時(shí)設(shè)置EstimateCost為MAX另外需要一個(gè)變量描述改動狀態(tài)(Modified)，如果改動過最佳記錄則狀態(tài)第0位為1，如果在Open隊(duì)列中則地1位為1，如果在Close中則第2位為1那么只要通過位運(yùn)算就可以知道節(jié)點(diǎn)和隊(duì)列的關(guān)系了，另外用一個(gè)數(shù)組來記錄修改過最佳距離的節(jié)點(diǎn)位置，并且依據(jù)前面的狀態(tài)變量來判斷如果以前已經(jīng)記錄過就不再記錄了，當(dāng)路徑搜索完以后就根據(jù)這個(gè)數(shù)組來還原數(shù)據(jù)了。

　　請看右邊的搜索試列圖，可以簡單看出OPEN隊(duì)列在插入/刪除時(shí)并不需要內(nèi)存分配而只要改變其指針和Node[h][w]中節(jié)點(diǎn)的Next指針就行了。這是激動人心的提高，
  
　　

 

 

 

 

 

 

　　有了前面兩段的優(yōu)化，路徑算法已經(jīng)省去了許多不必要的工序了，再看下實(shí)用性方面，首先判斷地圖是否可以移動不要在算法中直接判斷而最好設(shè)置一個(gè)虛函數(shù)MoveAble(x,y)來實(shí)現(xiàn)(程序中我用函數(shù)指針代替)，因?yàn)樵谟螒蛑心硥K地圖對于地面單位和空中單位還有水下單位可以移動的情況都不同因此直接操作地圖元素并不是明智的選擇，再者估價(jià)函數(shù)JudgeCost(x,y)也應(yīng)該設(shè)置成虛函數(shù)或者函數(shù)指針來實(shí)現(xiàn)，畢竟求估價(jià)值的方法很靈活，這里不能限制死了。

　　還有每次尋路搜索哪些方向呢？用DirMask來描述0-7位代表從上開始順時(shí)針一圈的八個(gè)方向情況，0代表不搜索，1代表搜索，那么四個(gè)方向搜索可以用0x55(1010101b)來代替，八個(gè)方向可以用0xff來設(shè)定，如此一來你可以設(shè)定只進(jìn)行搜索3個(gè)方向的尋路，這樣可以滿足一些簡單的尋路任務(wù)了，比如RPG中NPC敵人的移動就可以這樣來設(shè)定。最后就是范圍問題的設(shè)定了，Open表的最大大小可以設(shè)置為100-200(四個(gè)方向)或200-300(八個(gè)方向)而Close表的大小即處理節(jié)點(diǎn)的最多數(shù)目可以設(shè)置成(MapH*MapW)/16這樣的設(shè)定在士兵走入一個(gè)桶形地形時(shí)并不會花費(fèi)很大的開銷去尋找通路，而是走到桶形地形的尖端。其具體值可以適當(dāng)調(diào)整，當(dāng)然數(shù)值越大搜索就越廣，開銷也就越大(MapH*Map)/16這個(gè)數(shù)值我自己感覺比較接近星際的尋路特點(diǎn)

　　其它優(yōu)化，由于Open隊(duì)列中的數(shù)據(jù)全部是連表插入排序的，當(dāng)數(shù)據(jù)多時(shí)效率并不會見得高。這時(shí)如果還要繼續(xù)優(yōu)化手段也很多，比如建立Hash散列表，或者用二叉樹來代替連表排序，大家可以參考前導(dǎo)公司的寫的A*代碼里面就用了散列表這點(diǎn)很優(yōu)秀，但它任然擺脫不了大量的內(nèi)存分配/釋放。因此此處我覺得不怎么高明。

　　到是估價(jià)值的計(jì)算方法很多，但是寫的好壞也關(guān)系到搜索的規(guī)模：坐標(biāo)差之絕對值乘加權(quán)值求和，平方和開方還有些怪的呢，可以看看前導(dǎo)的代碼估價(jià)函數(shù)是怎么寫的。我看到網(wǎng)上有文章說當(dāng)前節(jié)點(diǎn)到終點(diǎn)的估計(jì)距離不能比實(shí)際距離大，說什么才能叫做A*算法，否則只能叫A算法(人工智能書上說的)，因?yàn)椴灰欢ㄊ亲疃搪窂剑呛堑侨绻皇菨M足估價(jià)值小于真實(shí)值也不一定就可以找到最短路徑故暫且不論，先看JudgeCost的意義--使搜索更靠近終點(diǎn)，勢必減小JudgeCost將會增加搜索的寬度及規(guī)模，增加JudgeCost則使搜索跟快地向終點(diǎn)靠攏。下面是使用不同估價(jià)函數(shù)的對比：

  
JudgeCost=abs(dx)+abs(dy) JudgeCost=abs(dx),abs(dy)加權(quán)求和 

　　上圖兩種估價(jià)函數(shù)的求法，星號是路徑點(diǎn)是搜索過的節(jié)點(diǎn)，當(dāng)JudgeCost大于真實(shí)值時(shí)從一個(gè)節(jié)點(diǎn)出發(fā)算法更愿意搜索一個(gè)靠終點(diǎn)近的點(diǎn)，換言之JudgeCost越大算法就越買力向終點(diǎn)靠攏，從左右兩副圖可以清楚看到(點(diǎn)擊放大)。所以我們使用坐標(biāo)差加權(quán)求和來處理或者直接求和乘與一個(gè)數(shù)字(比如8)在地形復(fù)雜的時(shí)候就更加顯出這種方法的實(shí)用性了，良種式子的規(guī)模差距還要比上圖嚴(yán)重的多。所以通用地用加權(quán)求和dx=abs(x-endx),dy=abs(y-endy);if (dx>dy) result =10*dx+6*dy; else result=10*dy+6*dx;就是這個(gè)意思，所用的乘10和乘6是試驗(yàn)證明比較好用的數(shù)字了，如此一來搜索的規(guī)模就被控制得又減小了，是不可忽視的。

　　還有幾點(diǎn)要注意的，集體尋路要采用跟隨政策，共用一條路徑，中途遇到移動物分三步走：嘗試加入一個(gè)斜方的路徑節(jié)點(diǎn)看是否可以饒過;不能就等待移動物體自己走開;到了時(shí)間不走再另外搜尋路徑，大場景要預(yù)先設(shè)定一些路徑節(jié)點(diǎn)中轉(zhuǎn)站再進(jìn)行遠(yuǎn)距離搜索時(shí)可以大大提高效率，用方向保存路徑比用坐標(biāo)保存節(jié)省至少1/4的空間。。。。碰到敵人部隊(duì)就開槍，自己部隊(duì)則可以不走了，或者發(fā)送兩條指令給擋住路的士兵的指令隊(duì)列1.移開當(dāng)前位置并等待;2.回到當(dāng)前位置，這樣可以產(chǎn)生一個(gè)一個(gè)順序讓路的精彩效果，紅警里面早已有實(shí)現(xiàn):-)

　　講遠(yuǎn)了，那是行軍問題了，前段時(shí)間給一個(gè)高中生輔導(dǎo)NOI復(fù)賽，那小子竟然在講到廣度優(yōu)先時(shí)問了路徑算法，一時(shí)興起就寫了這篇文章以及一段三百多行的程序，順便供大家參考:-)　一家之言，歡迎來信討論: skywindt@yeah.net

Copyright LinWei 2001/12/19