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

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

3、中央,直到抵達目的地。這些格子的中點叫做節點。當你在其他地方看到有關尋找路徑的東西時,你會經常發現人們在討論節點。為什么不直接把它們稱作方格呢?因為你不一定要把你的搜索區域分隔成方塊,矩形、六邊形或者其他任何形狀都可以。況且節點還有可能位于這些形狀內的任何一處呢?在中間、靠著邊,或者什么的。我們就用這種設定,因為畢竟這是最簡單的情況。開始搜索當我們把搜索區域簡化成一些很容易操作的節點后,下一步就要構造一個搜索來尋找最短路徑。在A*算法中,我們從A點開始,依次檢查它的相鄰節點,然后照此繼續并向外擴展直到找到目的地。我們通過以下方法來開始搜索:1.從A點開始,將A點加入一個專門存放待檢驗的方格的“

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

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

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

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

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

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

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

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

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

13、,就不管它了。上面挨著的那個也同樣忽略。還有右邊墻下面那個方格我們也不管。為什么呢?因為你不可能切穿墻角直接到達那個格子。實際上你得先向下走然后再通過那個方格。這個過程中是繞著墻角走。(注意:穿過墻角的這個規則是可選的,取決于你的節點是如何放置的。那么還剩下其他五個相鄰方格。當前方格的下面那兩個還不在開放列表中,那我們把它們加進去并且把當前方格作為它們的父方格。其他三個中有兩個已經在封閉列表中了(兩個已經在圖中用亮藍色標記了,起始方格,上面的方格,所以就不用管了。最后那個,當前方格左邊挨著的,要檢查一下經由當前節點到那里會不會降低它的G值。結果不行,所以我們又處理完畢了,然后去檢驗開放列表中的

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

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

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

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

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

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

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

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

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

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

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

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

26、A*算法會得出開銷最小路程最短的路徑，但沒法得到看起來最平滑的路 徑。看看那個例子的最終路徑（圖七） ，該路徑的第一步是起始點的右下方的方格。 如果第一步是正下方那個方格，那得到的路徑不是就要平滑很多嗎？ 有幾種方法可以處理這個問題。如在計算路徑的時候你可以給那些改變了路徑方向 的方格一個額外開銷，使其G值增大。這樣，你可以沿著所得路徑看看哪些取舍能 使你的路徑看起來更平滑。對于這個話題，可以看看鏈接標記Toward More Realistic Pathfinding（是免費的，但是查看需要注冊）來了解更多。 / 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. 非方格的搜索區域：在上面的例子中，我們用的是簡單的二維方格布局。你可以不 這樣弄，不規則區域也行。想想棋盤游戲Risk和Risk里的那些國家。你可以設計一 個那樣的尋路的關卡。要做這樣的關卡，你得創建一個查找表來存儲每個國家對應 的鄰國，和從一個國家移動到另一個國家的開銷G。另外也得選一種計算估計值H的 方法。其他的處理就和前面的例子差不多了。只是當對新區域進行檢驗時，即添加 新項目到開放列表中的時候，是從表中查找鄰近國家而不是選擇鄰近方格。 類似的，你可以針對固定地形的地圖來創建一個路標系統。路

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

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