林 偉 2001.12
這里的A*優(yōu)化只是針對(duì)網(wǎng)上一些關(guān)于A*算法介紹的文章來(lái)寫的，至于我接觸過的A*代碼可能都算不上專業(yè)級(jí)別因此我從這些代碼開始優(yōu)化也只是覺得這些代碼的優(yōu)點(diǎn)在于說明算法，而在效率與實(shí)用性方面就有些欠缺。
A*是啟發(fā)試搜索加動(dòng)態(tài)規(guī)劃。具體實(shí)現(xiàn)依靠?jī)蓚€(gè)隊(duì)列Open隊(duì)列和Close隊(duì)列。從一點(diǎn)開始探走幾個(gè)相鄰的格子如果可以移動(dòng)且當(dāng)前移動(dòng)為起點(diǎn)到哪個(gè)格子的歷史最佳方法則把那個(gè)格子按照估價(jià)值從小到大插入Open隊(duì)列里面，幾個(gè)方向試探結(jié)素后取出估價(jià)值最小的節(jié)點(diǎn)放入Close再?gòu)倪@里開始試探幾個(gè)相鄰的方向同樣放入Open隊(duì)列里面，放入Open的條件是1.這步在地圖上面是可以移動(dòng)的，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è)方向上都不能移動(dòng)，則把該點(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ì)列空了無(wú)法取出節(jié)點(diǎn)時(shí)搜索結(jié)束沒有找到終點(diǎn)，此時(shí)還是按照上面的方法找一個(gè)最接近終點(diǎn)的點(diǎn)代替終點(diǎn)。
這樣搜索就不會(huì)漫無(wú)邊際地進(jìn)行下去了。上面的程序大家稍微觀察就會(huì)發(fā)現(xiàn)幾處影響速度的致命地方，啟發(fā)試搜索是不變的，而看程序每次加入取出兩個(gè)隊(duì)列時(shí)都要進(jìn)行繁瑣的內(nèi)存分配，這是項(xiàng)耗費(fèi)時(shí)間的工作，其次需要檢查是否在隊(duì)列中，這點(diǎn)也是很慢的，最后就是保存動(dòng)態(tài)規(guī)劃數(shù)據(jù)(歷史最短距離)的數(shù)組進(jìn)行還原，并且每次尋路都要還原若大的數(shù)組，這是無(wú)法接受的。
我所說的優(yōu)化是從數(shù)據(jù)結(jié)構(gòu)入手解決上面的問題讓Open/Close兩隊(duì)列處理時(shí)不再涉及內(nèi)存分配問題，首先建立一個(gè)與地圖上面每個(gè)節(jié)點(diǎn)一一對(duì)應(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也是這樣描述的如此來(lái)看每次搜尋的時(shí)候就不必內(nèi)存分配了，插入節(jié)點(diǎn)(x,y)時(shí)只要改動(dòng)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不會(huì)有重復(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è)變量描述改動(dòng)狀態(tài)(Modified)，如果改動(dòng)過最佳記錄則狀態(tài)第0位為1，如果在Open隊(duì)列中則地1位為1，如果在Close中則第2位為1那么只要通過位運(yùn)算就可以知道節(jié)點(diǎn)和隊(duì)列的關(guān)系了，另外用一個(gè)數(shù)組來(lái)記錄修改過最佳距離的節(jié)點(diǎn)位置，并且依據(jù)前面的狀態(tài)變量來(lái)判斷如果以前已經(jīng)記錄過就不再記錄了，當(dāng)路徑搜索完以后就根據(jù)這個(gè)數(shù)組來(lái)還原數(shù)據(jù)了。
請(qǐng)看右邊的搜索試列圖，可以簡(jiǎn)單看出OPEN隊(duì)列在插入/刪除時(shí)并不需要內(nèi)存分配而只要改變其指針和Node[h][w]中節(jié)點(diǎn)的Next指針就行了。這是激動(dòng)人心的提高，
|
|
?
?
?
?
?
?
有了前面兩段的優(yōu)化，路徑算法已經(jīng)省去了許多不必要的工序了，再看下實(shí)用性方面，首先判斷地圖是否可以移動(dòng)不要在算法中直接判斷而最好設(shè)置一個(gè)虛函數(shù)MoveAble(x,y)來(lái)實(shí)現(xiàn)(程序中我用函數(shù)指針代替)，因?yàn)樵谟螒蛑心硥K地圖對(duì)于地面單位和空中單位還有水下單位可以移動(dòng)的情況都不同因此直接操作地圖元素并不是明智的選擇，再者估價(jià)函數(shù)JudgeCost(x,y)也應(yīng)該設(shè)置成虛函數(shù)或者函數(shù)指針來(lái)實(shí)現(xiàn)，畢竟求估價(jià)值的方法很靈活，這里不能限制死了。
還有每次尋路搜索哪些方向呢？用DirMask來(lái)描述0-7位代表從上開始順時(shí)針一圈的八個(gè)方向情況，0代表不搜索，1代表搜索，那么四個(gè)方向搜索可以用0x55(1010101b)來(lái)代替，八個(gè)方向可以用0xff來(lái)設(shè)定，如此一來(lái)你可以設(shè)定只進(jìn)行搜索3個(gè)方向的尋路，這樣可以滿足一些簡(jiǎn)單的尋路任務(wù)了，比如RPG中NPC敵人的移動(dòng)就可以這樣來(lái)設(shè)定。最后就是范圍問題的設(shè)定了，Open表的最大大小可以設(shè)置為100-200(四個(gè)方向)或200-300(八個(gè)方向)而Close表的大小即處理節(jié)點(diǎn)的最多數(shù)目可以設(shè)置成(MapH*MapW)/16這樣的設(shè)定在士兵走入一個(gè)桶形地形時(shí)并不會(huì)花費(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í)效率并不會(huì)見得高。這時(shí)如果還要繼續(xù)優(yōu)化手段也很多，比如建立Hash散列表，或者用二叉樹來(lái)代替連表排序，大家可以參考前導(dǎo)公司的寫的A*代碼里面就用了散列表這點(diǎn)很優(yōu)秀，但它任然擺脫不了大量的內(nèi)存分配/釋放。因此此處我覺得不怎么高明。
到是估價(jià)值的計(jì)算方法很多，但是寫的好壞也關(guān)系到搜索的規(guī)模：坐標(biāo)差之絕對(duì)值乘加權(quán)值求和，平方和開方還有些怪的呢，可以看看前導(dǎo)的代碼估價(jià)函數(shù)是怎么寫的。我看到網(wǎng)上有文章說當(dāng)前節(jié)點(diǎn)到終點(diǎn)的估計(jì)距離不能比實(shí)際距離大，說什么才能叫做A*算法，否則只能叫A算法(人工智能書上說的)，因?yàn)椴灰欢ㄊ亲疃搪窂?，呵呵但是如果只是滿足估價(jià)值小于真實(shí)值也不一定就可以找到最短路徑故暫且不論，先看JudgeCost的意義--使搜索更靠近終點(diǎn)，勢(shì)必減小JudgeCost將會(huì)增加搜索的寬度及規(guī)模，增加JudgeCost則使搜索跟快地向終點(diǎn)靠攏。下面是使用不同估價(jià)函數(shù)的對(duì)比：
|
|
|
JudgeCost=abs(dx)+abs(dy)
|
JudgeCost=abs(dx),abs(dy)加權(quán)求和
|
上圖兩種估價(jià)函數(shù)的求法，星號(hào)是路徑點(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)求和來(lái)處理或者直接求和乘與一個(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ù)字了，如此一來(lái)搜索的規(guī)模就被控制得又減小了，是不可忽視的。
還有幾點(diǎn)要注意的，集體尋路要采用跟隨政策，共用一條路徑，中途遇到移動(dòng)物分三步走：嘗試加入一個(gè)斜方的路徑節(jié)點(diǎn)看是否可以饒過;不能就等待移動(dòng)物體自己走開;到了時(shí)間不走再另外搜尋路徑，大場(chǎng)景要預(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í)興起就寫了這篇文章以及一段三百多行的程序，順便供大家參考:-) 一家之言，歡迎來(lái)信討論: skywindt@yeah.net
Copyright LinWei 2001/12/19