A星算法中文詳解

1、雖然A*(讀作A星算法對初學(xué)者來說是比較深奧難懂,但是一旦你找到門路了,它又會變得非常簡單。網(wǎng)上有很多解釋A*算法的文章,但是大多數(shù)是寫給那些有一定基礎(chǔ)的人看的,而您看到的這一篇呢,是真正寫給菜鳥的。本篇文章并不想給這個(gè)算法題目作一些權(quán)威性論斷,而是闡述它的基本原理,并為你理解更多相關(guān)資料與討論打下基礎(chǔ)。文章末尾給出了一些比較好的鏈接,放在“進(jìn)階閱讀”一節(jié)之后。最后,本文不是編程規(guī)范,你將可能使這里講述的東西編寫成任何計(jì)算機(jī)語言。在本文的末尾我還給出了一個(gè)例子程序包的下載鏈接,也許正合你意。在這個(gè)包中有C+和Blitz Basic兩個(gè)版本的程序代碼,如果你只是想看看A*算法是如何運(yùn)作的,該包中

2、也有可直接執(zhí)行的文件供你研究。我們還是要超越自己的(把算法弄懂,所以,讓我們從頭開始吧!初步:搜索區(qū)域我們假設(shè)某個(gè)人要從A點(diǎn)到達(dá)B點(diǎn),而一堵墻把這兩個(gè)點(diǎn)隔開了,如下圖所示,綠色部分代表起點(diǎn)A,紅色部分代表終點(diǎn)B,藍(lán)色方塊部分代表之間的墻。 圖一你首先會注意到我們把這一塊搜索區(qū)域分成了一個(gè)一個(gè)的方格,如此這般,使搜索區(qū)域簡單化,正是尋找路徑的第一步。這種方法將我們的搜索區(qū)域簡化成了一個(gè)普通的二維數(shù)組。數(shù)組中的每一個(gè)元素表示對應(yīng)的一個(gè)方格,該方格的狀態(tài)被標(biāo)記為可通過的和不可通過的。通過找出從A點(diǎn)到B點(diǎn)所經(jīng)過的方格,就能得到AB之間的路徑。當(dāng)路徑找出來以后,這個(gè)人就可以從一個(gè)格子中央移動到另一個(gè)格子

3、中央,直到抵達(dá)目的地。這些格子的中點(diǎn)叫做節(jié)點(diǎn)。當(dāng)你在其他地方看到有關(guān)尋找路徑的東西時(shí),你會經(jīng)常發(fā)現(xiàn)人們在討論節(jié)點(diǎn)。為什么不直接把它們稱作方格呢?因?yàn)槟悴灰欢ㄒ涯愕乃阉鲄^(qū)域分隔成方塊,矩形、六邊形或者其他任何形狀都可以。況且節(jié)點(diǎn)還有可能位于這些形狀內(nèi)的任何一處呢?在中間、靠著邊,或者什么的。我們就用這種設(shè)定,因?yàn)楫吘惯@是最簡單的情況。開始搜索當(dāng)我們把搜索區(qū)域簡化成一些很容易操作的節(jié)點(diǎn)后,下一步就要構(gòu)造一個(gè)搜索來尋找最短路徑。在A*算法中,我們從A點(diǎn)開始,依次檢查它的相鄰節(jié)點(diǎn),然后照此繼續(xù)并向外擴(kuò)展直到找到目的地。我們通過以下方法來開始搜索:1.從A點(diǎn)開始,將A點(diǎn)加入一個(gè)專門存放待檢驗(yàn)的方格的“

4、開放列表”中。這個(gè)開放列表有點(diǎn)像一張購物清單。當(dāng)前這個(gè)列表中只有一個(gè)元素,但一會兒將會有更多。列表中包含的方格可能會是你要途經(jīng)的方格,也可能不是?？傊?這是一個(gè)包含待檢驗(yàn)方格的列表。2.檢查起點(diǎn)A相鄰的所有可達(dá)的或者可通過的方格,不用管墻啊,水啊,或者其他什么無效地形,把它們也都加到開放列表中。對于每一個(gè)相鄰方格,將點(diǎn)A保存為它們的“父方格”。當(dāng)我們要回溯路徑的時(shí)候,父方格是一個(gè)很重要的元素。稍后我們將詳細(xì)解釋它。3.從開放列表中去掉方格A,并把A加入到一個(gè)“封閉列表”中。封閉列表存放的是你現(xiàn)在不用再去考慮的方格。此時(shí)你將得到如下圖所示的樣子。在這張圖中,中間深綠色的方格是你的起始方格,所有相

5、鄰方格目前都在開放列表中,并且以亮綠色描邊。每個(gè)相鄰方格有一個(gè)灰色的指針指向它們的父方格,即起始方格。 圖二接下來,我們在開放列表中選一個(gè)相鄰方格并再重復(fù)幾次如前所述的過程。但是我們該選哪一個(gè)方格呢?具有最小F值的那個(gè)。路徑排序決定哪些方格會形成路徑的關(guān)鍵是下面這個(gè)等式:F =G +H 這里G =從起點(diǎn)A 沿著已生成的路徑到一個(gè)給定方格的移動開銷。H =從給定方格到目的方格的估計(jì)移動開銷。這種方式常叫做試探,有點(diǎn)困惑人吧。其實(shí)之所以叫做試探法是因?yàn)檫@只是一個(gè)猜測。在找到路徑之前我們實(shí)際上并不知道實(shí)際的距離,因?yàn)槿魏螙|西都有可能出現(xiàn)在半路上(墻啊,水啊什么的。本文中給出了一種計(jì)算H 值的方法,網(wǎng)

6、上還有很多其他文章介紹的不同方法。 我們要的路徑是通過反復(fù)遍歷開放列表并選擇具有最小F 值的方格來生成的。本文稍后將詳細(xì)討論這個(gè)過程。我們先進(jìn)一步看看如何計(jì)算那個(gè)等式。如前所述,G 是從起點(diǎn)A 沿著已生成的路徑到一個(gè)給定方格的移動開銷,在本例中,我們指定每一個(gè)水平或者垂直移動的開銷為10,對角線移動的開銷為14。因?yàn)閷蔷€的實(shí)際距離是2的平方根(別嚇到啦,或者說水平及垂直移動開銷的1.414倍。為了簡單起見我們用了10和14這兩個(gè)值。比例大概對就好,我們還因此避免了平方根和小數(shù)的計(jì)算。這倒不是因?yàn)槲覀儽炕蛘哒f不喜歡數(shù)學(xué),而是因?yàn)閷﹄娔X來說,計(jì)算這樣的數(shù)字也要快很多。不然的話你會發(fā)現(xiàn)尋找路徑會非

7、常慢。我們要沿特定路徑計(jì)算給定方格的G 值,辦法就是找出該方格的父方格的G 值,并根據(jù)與父方格的相對位置(斜角或非斜角方向來給這個(gè)G 值加上14或者10。在本例中這個(gè)方法將隨著離起點(diǎn)方格越來越遠(yuǎn)計(jì)算的方格越來越多而用得越來越多。有很多方算通過水平和垂直方向的平移到達(dá)目的地所經(jīng)過的方格數(shù)乘以10來得到H 值。之所以叫Manhattan 方法是因?yàn)檫@就像計(jì)算從一個(gè)地方移動到另一個(gè)地方所經(jīng)過的城市街區(qū)數(shù)一樣,而通常你是不能斜著穿過街區(qū)的。重要的是,在計(jì)算H 值時(shí)并不考慮任何障礙物。因?yàn)檫@是對剩余距離的估計(jì)值而不是實(shí)際值(通常是要保證估計(jì)值不大于實(shí)際值譯者注。這就是為什么這個(gè)方式被叫做試探法的原因了。

8、想要了解更多些嗎?法可以用來估計(jì)H 值。我們用的這個(gè)叫做曼哈頓(Manhattan 方法,即計(jì)和H 相加就得到了F 。第一步搜索所得到的結(jié)果如下圖所示。每個(gè)方格里都標(biāo)出了F 、鏈接標(biāo)記這里還有更多式子和關(guān)于試探法的額外說明。G G 和H 值。如起點(diǎn)方格右側(cè)的方格標(biāo)出的,左上角顯示的是F 值,左下角是G 值,右下角是H 值。 圖三我們來看看這些方格吧。在有字母的方格中,G=10,這是因?yàn)樗谒椒较蛏想x起點(diǎn)只有一個(gè)方格遠(yuǎn)。起點(diǎn)緊挨著的上下左右都具有相同的G值10。對角線方向的方塊G值都是14。H值通過估算到紅色目標(biāo)方格的曼哈頓距離而得出。用這種方法得出的起點(diǎn)右側(cè)方格到紅色方格有3個(gè)方格遠(yuǎn),則該方

9、格H值就是30。上面那個(gè)方格有4個(gè)方格遠(yuǎn)(注意只能水平和垂直移動,H就是40。你可以大概看看其他方格的H值是怎么計(jì)算出來的。每一個(gè)方格的F值,當(dāng)然就不過是G和H值之和了。繼續(xù)搜索為了繼續(xù)搜索,我們簡單的從開放列表中選擇具有最小F值的方格,然后對選中的方格進(jìn)行如下操作:4.將其從開放列表中移除,并加到封閉列表中。5.檢驗(yàn)所有的相鄰方格,忽略那些不可通過的或者已經(jīng)在封閉列表里的方格。如果這個(gè)相鄰方格不在開放列表中,就把它添加進(jìn)去。并將當(dāng)前選定方格設(shè)為新添方格的父方格。6.如果某個(gè)相鄰方格已經(jīng)在開放列表中了(意味著已經(jīng)探測過,而且已經(jīng)設(shè)置過父方格譯者,就看看有沒有到達(dá)那個(gè)方格的更好的路徑。也就是說,

10、如果從當(dāng)前選中方格到那個(gè)方格,會不會使那個(gè)方格的G值更小。如果不能,就不進(jìn)行任何操作。相反的,如果新路徑的G值更小,就將該相鄰方格的父方格重設(shè)為當(dāng)前選中方格。(在上圖中是改變其指針的方向?yàn)橹赶蜻x中方格。最后,重新計(jì)算那個(gè)相鄰方格的F和G值。如果你看糊涂了,下面會有圖解說明。好啦,咱們來看看具體點(diǎn)的例子。在初始時(shí)的9個(gè)方塊中,當(dāng)開始方格被加到封閉列表后,開放列表里還剩8個(gè)方格。在這八個(gè)方格當(dāng)中,位于起點(diǎn)方格右邊的那個(gè)方格具有最小的F值40。所以我們選擇這個(gè)方格作為下一個(gè)中心方格。下圖中它以高亮的藍(lán)色表示。 圖四首先,我們將選中的方格從開放列表中移除,并加入到封閉列表中(所以用亮藍(lán)色標(biāo)記。然后再檢

11、驗(yàn)它的相鄰節(jié)點(diǎn)。那么在它緊鄰的右邊的方格都是墻,所以不管它們。左邊挨著的是起始方格,而起始方格已經(jīng)在封閉列表中了,所以我們也不管它。其他四個(gè)方格已經(jīng)在開放列表中,那么我們就要檢驗(yàn)一下如果路徑經(jīng)由當(dāng)前選中方格到那些方格的話會不會更好,當(dāng)然,是用G值作為參考。來看看選中方格右上角的那一個(gè)方格,它當(dāng)前的G值是14,如果我們經(jīng)由當(dāng)前節(jié)點(diǎn)再到達(dá)那個(gè)方格的話, G值會是20(到當(dāng)前方格的G值是10,然后向上移動一格就再加上10。為20的G值比14大,因此這樣的路徑不會更好。你看看圖就會容易理解些。顯然從起始點(diǎn)沿斜角方向移動到那個(gè)方格比先水平移動一格再垂直移動一格更直接。當(dāng)我們按如上過程依次檢驗(yàn)開放列表中的

12、所有四個(gè)方格后,會發(fā)現(xiàn)經(jīng)由當(dāng)前方格的話不會形成更好的路徑,那我們就保持目前的狀況不變。現(xiàn)在我們已經(jīng)處理了所有相鄰方格,準(zhǔn)備到下一個(gè)方格吧。我們再遍歷一下開放列表,目前只有7個(gè)方格了。我們挑個(gè)F值最小的吧。有趣的是,目前這種情況下,有兩個(gè)F值為54的方格。那我們怎么選擇呢?其實(shí)選哪個(gè)都沒關(guān)系,要考慮到速度的話,選你最近加到開放列表中的那一個(gè)會更快些。當(dāng)離目的地越來越近的時(shí)候越偏向于選最后發(fā)現(xiàn)的方格。實(shí)際上這個(gè)真的沒關(guān)系(對待這個(gè)的不同造成了兩個(gè)版本的A*算法得到等長的不同路徑。那我們選下面的那個(gè)好了,就是起始方格右邊的,下圖所示的那個(gè)。 圖五這一次,在我們檢驗(yàn)相鄰方格的時(shí)候發(fā)現(xiàn)右邊緊挨的那個(gè)是墻

13、,就不管它了。上面挨著的那個(gè)也同樣忽略。還有右邊墻下面那個(gè)方格我們也不管。為什么呢?因?yàn)槟悴豢赡芮写侵苯拥竭_(dá)那個(gè)格子。實(shí)際上你得先向下走然后再通過那個(gè)方格。這個(gè)過程中是繞著墻角走。(注意:穿過墻角的這個(gè)規(guī)則是可選的,取決于你的節(jié)點(diǎn)是如何放置的。那么還剩下其他五個(gè)相鄰方格。當(dāng)前方格的下面那兩個(gè)還不在開放列表中,那我們把它們加進(jìn)去并且把當(dāng)前方格作為它們的父方格。其他三個(gè)中有兩個(gè)已經(jīng)在封閉列表中了(兩個(gè)已經(jīng)在圖中用亮藍(lán)色標(biāo)記了,起始方格,上面的方格,所以就不用管了。最后那個(gè),當(dāng)前方格左邊挨著的,要檢查一下經(jīng)由當(dāng)前節(jié)點(diǎn)到那里會不會降低它的G值。結(jié)果不行,所以我們又處理完畢了,然后去檢驗(yàn)開放列表中的

14、下一個(gè)格子。重復(fù)這個(gè)過程直到我們把目的方格加入到開放列表中了,那時(shí)候看起來會像下圖這個(gè)樣子。 圖六注意到?jīng)]?起始方格下兩格的位置,那里的格子已經(jīng)和前一張圖不一樣了。之前它的G值是28并且指向右上方的那個(gè)方格?，F(xiàn)在它的G值變成了20并且指向了正上方的方格。這個(gè)改變是在搜索過程中,它的G值被核查時(shí)發(fā)現(xiàn)在某個(gè)新路徑下可以變得更小時(shí)發(fā)生的。然后它的父方格也被重設(shè)并且重新計(jì)算了G值和F值。在本例中這個(gè)改變看起來好像不是很重要,但是在很多種情況下這種改變會使到達(dá)目標(biāo)的最佳路徑變得非常不同。那么我們怎樣來自動得出實(shí)際路徑的呢?很簡單,只要從紅色目標(biāo)方格開始沿著每一個(gè)方格的指針方向移動,依次到達(dá)它們的父方格,

15、最終肯定會到達(dá)起始方格。那就是你的路徑!如下圖所示。從A方格到B方格的移動就差不多是沿著這個(gè)路徑從每個(gè)方格中心(節(jié)點(diǎn)移動到另一個(gè)方格中心,直到抵達(dá)終點(diǎn)。簡單吧! 圖七A*算法總結(jié)1.將開始節(jié)點(diǎn)放入開放列表(開始節(jié)點(diǎn)的F和G值都視為0;2.重復(fù)一下步驟:i.在開放列表中查找具有最小F值的節(jié)點(diǎn),并把查找到的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn);ii.把當(dāng)前節(jié)點(diǎn)從開放列表刪除, 加入到封閉列表;iii.對當(dāng)前節(jié)點(diǎn)相鄰的每一個(gè)節(jié)點(diǎn)依次執(zhí)行以下步驟:1.如果該相鄰節(jié)點(diǎn)不可通行或者該相鄰節(jié)點(diǎn)已經(jīng)在封閉列表中,則什么操作也不執(zhí)行,繼續(xù)檢驗(yàn)下一個(gè)節(jié)點(diǎn);2.如果該相鄰節(jié)點(diǎn)不在開放列表中,則將該節(jié)點(diǎn)添加到開放列表中, 并將該相鄰節(jié)點(diǎn)

16、的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn),同時(shí)保存該相鄰節(jié)點(diǎn)的G和F值;3.如果該相鄰節(jié)點(diǎn)在開放列表中, 則判斷若經(jīng)由當(dāng)前節(jié)點(diǎn)到達(dá)該相鄰節(jié)點(diǎn)的G值是否小于原來保存的G值,若小于,則將該相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn),并重新設(shè)置該相鄰節(jié)點(diǎn)的G和F值.iv.循環(huán)結(jié)束條件:當(dāng)終點(diǎn)節(jié)點(diǎn)被加入到開放列表作為待檢驗(yàn)節(jié)點(diǎn)時(shí), 表示路徑被找到,此時(shí)應(yīng)終止循環(huán); 或者當(dāng)開放列表為空,表明已無可以添加的新節(jié)點(diǎn),而已檢驗(yàn)的節(jié)點(diǎn)中沒有終點(diǎn)節(jié)點(diǎn)則意味著路徑無法被找到,此時(shí)也結(jié)束循環(huán); 3.從終點(diǎn)節(jié)點(diǎn)開始沿父節(jié)點(diǎn)遍歷, 并保存整個(gè)遍歷到的節(jié)點(diǎn)坐標(biāo),遍歷所得的節(jié)點(diǎn)就是最后得到的路徑;一點(diǎn)感慨原諒我的離題。但畢竟值得指出的是,當(dāng)你在網(wǎng)上和論壇里看

17、到很多討論A*路徑尋找算法的東西時(shí),偶爾會遇到一些人所指的A*算法并不是真正的A*的情況。實(shí)際上要應(yīng)用真正的A*要包含我們上面討論的那些元素:專門的開放列表和封閉列表,用F 、G 和H 值來排序的路徑統(tǒng)計(jì)。有很多其他的尋找路徑算法,但是其他的都不是A*,而A*一般認(rèn)為是這些算法當(dāng)中最好的。本文末尾的參考文檔里有Bryan Stout 對這些算法的討論。在特定情況下某些算法可能會更好,但是你至少要理解你要準(zhǔn)備做什么。好了,差不多了,還是回到主題吧。 實(shí)現(xiàn)時(shí)的注意事項(xiàng) 現(xiàn)在你已經(jīng)理解了基本的算法,下面將討論一些你在寫自己的程序時(shí)要考慮的東西。下面一些材料和我用C+和Blitz Basic 寫的程序

18、有關(guān),但是那些要點(diǎn)是適用于任何其他語言的。 1.開放列表的維護(hù):實(shí)際上是A*算法中最耗時(shí)的因素。每次你處理開放列表時(shí)你都要從中找出具有最小F 值的方格。有幾種方法可以做到。你可以保存所需的路徑元素,簡單的遍歷列表來找出最小F 值的方格。這種方法是很簡單,但是在路徑很長的時(shí)候會很慢。也可以改進(jìn)一下,變成維護(hù)一個(gè)有序列表,這樣在需要最小F 值方格的時(shí)候僅須獲取該有序列表的第一個(gè)元素。我在寫我那個(gè)程序的時(shí)候,開始就是用的這個(gè)辦法。這種方法很適合于地圖不大的情況。但這還不是最快的解決辦法。真正追求速度的認(rèn)真的程序員往往會使用二叉堆。這也是我在我的代碼中用的方法。據(jù)我的經(jīng)驗(yàn),這種方法會比大多數(shù)解決方案快

19、至少2-3倍,在路徑很長的時(shí)候更快(快10倍以上。如果你有興趣了解更多二叉堆的內(nèi)容,去看看我的這篇文章,需鏈接標(biāo)記Using Binary Heaps in A* Pathfinding 。2.其他單位。如果你仔細(xì)看了我的例子代碼,你會注意到它完全忽略了地圖上的其他單位。我的尋路者實(shí)際上是直接穿過彼此的。這樣行得通行不通是取決于游戲的。如果你要考慮地圖上的其他單位并且它們還能夠移動,我建議你在路徑尋找算法中忽略它們而另外寫一些代碼去檢測它們是否發(fā)生了碰撞。當(dāng)碰撞發(fā)生時(shí),你可以馬上生成一個(gè)新的路徑或者應(yīng)用一些標(biāo)準(zhǔn)移動規(guī)則(比如總是靠右走等等直到路徑上不再有障礙物或,然后再生成一個(gè)新的路徑。為什么

20、在你最初計(jì)算路徑的時(shí)候就把這些單位考慮進(jìn)去呢?那其實(shí)是因?yàn)槠渌麊挝灰矔苿?它們的位置在不停的改變。這樣會導(dǎo)致產(chǎn)生一些不可思議的結(jié)果,比如某個(gè)單位會突然轉(zhuǎn)向來避免一個(gè)實(shí)際上已經(jīng)不在那兒的另一個(gè)單位,或者撞上一個(gè)后來移動到它的預(yù)定路徑上的單位。在尋路算法中忽略其他單位意味著你將不得不寫一些單獨(dú)的代碼來避免沖突。這完全是由游戲特性決定的。所以我把解決方案留給你自己去琢磨。本文末尾參考文章一節(jié)Bryan Stout的一些地方提供了幾個(gè)解決方案(比如魯棒式跟蹤等等,不妨去看看。3.一些提速技巧:你在開發(fā)你自己的A*程序或者改變我寫的那個(gè)時(shí),總會發(fā)現(xiàn)這個(gè)尋路算法很耗CPU,特別是地圖上有大量的尋路者和地

21、圖相當(dāng)大的時(shí)候。如果你在網(wǎng)上讀過一些資料你會知道這個(gè)對于像星際爭霸或者帝國時(shí)代這樣專業(yè)的游戲也不例外。當(dāng)你發(fā)現(xiàn)你的尋路算法使你寫的東西變慢了的話,可以參考下面這些提速的辦法:用小一點(diǎn)的地圖或者尋路者少一點(diǎn)。不要在同一時(shí)間為很多個(gè)尋路者計(jì)算路徑。不如把它們放進(jìn)一個(gè)隊(duì)列里并分散在幾個(gè)游戲循環(huán)中。如果你的游戲運(yùn)行時(shí)大約是,比如說,40個(gè)循環(huán)/秒的話,沒人會注意到。但是要是有一堆尋路者在同一時(shí)間計(jì)算路徑而導(dǎo)致游戲在短時(shí)間內(nèi)變慢的話,就非常引人注意了。將地圖的區(qū)塊劃分得大一些。這樣會減少搜索路徑時(shí)的區(qū)塊總數(shù)。如果你夠強(qiáng),可以設(shè)計(jì)兩種以上的尋路系統(tǒng)來適應(yīng)于路徑長度不同的情況。這正是那些專業(yè)人士所做的,路徑

22、長的時(shí)候用大區(qū)塊,當(dāng)接近目標(biāo)路徑變短的時(shí)候又用小區(qū)塊來進(jìn)行精確些的搜索。要是你對這個(gè)概念感興趣,不妨讀讀我的文章鏈接標(biāo)記Two-Tiered A* Pathfinding考慮采用路標(biāo)系統(tǒng)來處理長路徑的情況,或者預(yù)先處理一些對游戲來說很少變化的路徑。對地圖進(jìn)行預(yù)處理并計(jì)算出哪些區(qū)域是從其他地方根本到達(dá)不了的。我把這些區(qū)域叫做“島”。實(shí)際中這些區(qū)域可能是島也可能是墻圍起來的地方。A*算法的一個(gè)缺陷是當(dāng)你在找到這樣一個(gè)不可達(dá)區(qū)域的路徑時(shí),幾乎會把整個(gè)地圖都搜個(gè)遍,直到地圖上每一個(gè)區(qū)塊都被搜索過了才會停。這樣會浪費(fèi)很多CPU時(shí)間。解決這個(gè)問題的辦法是預(yù)先得出哪些區(qū)域是根本不可達(dá)的(通過洪泛法或者其他方

23、式,用一個(gè)數(shù)組記錄下這些數(shù)據(jù)并在尋找路徑前先檢查一下。在我那個(gè)Blitz版本的代碼中,我創(chuàng)建了一個(gè)地圖預(yù)處理器來完成這樣的處理。這個(gè)預(yù)處理器還能提前找到可在尋路算法中忽略的死角,因而大大提高了算法速度。4.地形多樣化的開銷:在這個(gè)入門教程和我附帶的程序中,地形地貌只包括兩種情況:可通過的和不可通過的。但是假如還有一些地形那是可以通過的只是移動的開銷更大一點(diǎn)呢？比如沼澤、山丘、地牢里的梯子等等呢？這些都是可以通行的地形的例 子，只不過比開闊的平地具有更高的開銷。類似的，公路地形會比路郊的移動開銷 小。 這個(gè)問題很容易解決。只要在計(jì)算給定區(qū)塊的G值時(shí)把地形的開銷加上去就行。把 某個(gè)區(qū)塊加上額外的開

24、銷，A*算法仍然有效。在我描述的那個(gè)簡單例子里，地形只 分可通過和不可通過兩種，A*算法會找到最直接最短的路徑。但當(dāng)在一個(gè)地形多樣 化的環(huán)境里時(shí)，最小開銷路徑可能會是比較長的一段路程。例如從公路上繞過去顯 然比直接通過沼澤地開銷要小。 還有一個(gè)有趣的辦法是專業(yè)人士們叫做“感應(yīng)映射”的東西。如同上面描述的多樣化 地形開銷一樣，你可以創(chuàng)建一個(gè)額外的點(diǎn)數(shù)制度并將之應(yīng)用于AI方面的路徑中。假 設(shè)在一張地圖上有一堆家伙在守衛(wèi)一個(gè)山區(qū)要道，每次電腦派遣某人通過那條要道 時(shí)都會被困住。那你就可以創(chuàng)建一個(gè)感應(yīng)地圖使得發(fā)生很多戰(zhàn)斗沖突的那些區(qū)塊開 銷增大，以此來告知電腦去選一個(gè)更安全的路徑，并避免僅憑著是最短路

25、徑（但是 更危險(xiǎn)）就持續(xù)派遣人員通過某條路徑的愚蠢情形。 g I # P: |/ N 5. 處理未探索區(qū)域：你有玩過電腦總是知道怎么走，甚至地圖都還沒探索過的PC游戲 嗎？由此看來這個(gè)路徑尋找算法真是好得不現(xiàn)實(shí)。還好這個(gè)問題可以很容易解決。 方法就是為不同的玩家和電腦（不是每個(gè)單位，不然會耗掉好多內(nèi)存）創(chuàng)建一個(gè)獨(dú) 立的“已知可通行”數(shù)組。每個(gè)數(shù)組包含了玩家已探索區(qū)域和未知區(qū)域的信息，并把 未知區(qū)域全部視為可通行區(qū)域來對待，除非后來發(fā)現(xiàn)是其他的地形。使用這種方法 的話，移動單位就會繞到死角或犯類似錯(cuò)誤，直到它們發(fā)現(xiàn)了周圍的路。一旦地圖 都被探索過了，路徑尋找算法就會正常運(yùn)行了。 6. 平滑路徑：

26、A*算法會得出開銷最小路程最短的路徑，但沒法得到看起來最平滑的路 徑?？纯茨莻€(gè)例子的最終路徑（圖七） ，該路徑的第一步是起始點(diǎn)的右下方的方格。 如果第一步是正下方那個(gè)方格，那得到的路徑不是就要平滑很多嗎？ 有幾種方法可以處理這個(gè)問題。如在計(jì)算路徑的時(shí)候你可以給那些改變了路徑方向 的方格一個(gè)額外開銷，使其G值增大。這樣，你可以沿著所得路徑看看哪些取舍能 使你的路徑看起來更平滑。對于這個(gè)話題，可以看看鏈接標(biāo)記Toward More Realistic Pathfinding（是免費(fèi)的，但是查看需要注冊）來了解更多。 / 5 5 % a5 e# r T 0 V& w1 J N4 p9 M- B c

27、Q4 U 2 c , e3 l D I! C ! o f9 g1 N6 k$ i- v K 7. 非方格的搜索區(qū)域：在上面的例子中，我們用的是簡單的二維方格布局。你可以不 這樣弄，不規(guī)則區(qū)域也行。想想棋盤游戲Risk和Risk里的那些國家。你可以設(shè)計(jì)一 個(gè)那樣的尋路的關(guān)卡。要做這樣的關(guān)卡，你得創(chuàng)建一個(gè)查找表來存儲每個(gè)國家對應(yīng) 的鄰國，和從一個(gè)國家移動到另一個(gè)國家的開銷G。另外也得選一種計(jì)算估計(jì)值H的 方法。其他的處理就和前面的例子差不多了。只是當(dāng)對新區(qū)域進(jìn)行檢驗(yàn)時(shí)，即添加 新項(xiàng)目到開放列表中的時(shí)候，是從表中查找鄰近國家而不是選擇鄰近方格。 類似的，你可以針對固定地形的地圖來創(chuàng)建一個(gè)路標(biāo)系統(tǒng)。路

28、標(biāo)通常是橫穿路徑的 點(diǎn)，可能是在公路上也可能是在地牢的主隧道里。對于游戲設(shè)計(jì)者來說，需要提前 設(shè)置好這些路標(biāo)。 如果兩個(gè)路標(biāo)所成的直線路徑之間沒有障礙物的話就稱之為“相鄰 + m C, G% U8 |1 |3 c y, - 的”。在Risk游戲的例子中，你會將相鄰信息保存在一個(gè)查找表中，并會在新增開放 列表元素時(shí)用到這個(gè)查找表。然后你會用到相關(guān)的G值（可能通過兩個(gè)節(jié)點(diǎn)間的直 線距離得到）和H值（可能通過該節(jié)點(diǎn)到終點(diǎn)的直線距離得到）其他的運(yùn)算就和普 通的差不多。 另外一個(gè)使用非方格搜索區(qū)域的斜視角RPG游戲的例子參見我的文章 鏈接標(biāo)記 Two-Tiered A* Pathfinding。 P y

29、3 d9 p* 7 F5 + K5 q b9 P0 v5 C E i G4 G. K+ P 進(jìn)階閱讀 6 w7 |( I9 l0 u% Q, _+ A( M3 I - N2 u8 O3 Q1 w b 好了！現(xiàn)在你基本上掌握了基礎(chǔ)知識，并對高級的概念也有了些印象。在此我建議 把我的代碼拿來研究研究。壓縮包里有兩個(gè)版本，分別是C+的和Blitz Basic的。它 們的注釋都很詳細(xì)，我想應(yīng)該很容易理解。下面是鏈接： ( y# A V0 N1 ( ; T& j9 _ |0 # ?1 v$ l 鏈接標(biāo)記Sample Code: A* Pathfinder (2D Version 1.71 k; * k# R0 V: l 如果你沒法用C+或者Blitz Basic， 在C+版里有兩個(gè)程序文件可以直接運(yùn)行。 而Blitz Basic版本要在鏈接標(biāo)記Blitz Basic的網(wǎng)站上下載免費(fèi)演示版的Blitz Basic 3D才能運(yùn) 行。鏈接標(biāo)記這里還有Ben ONeill寫的在線示例。 你也應(yīng)通讀一下下面的網(wǎng)