A路徑尋找算法入門

1、A*路徑尋找算法入門來源于: GameD 作 者: Patrick Lester原文URL: 翻 譯: 孫璨雖然A*（讀作A星）算法對初學者來說是比較深奧難懂，但是一旦你找到門路了，它又會變得非常簡單。網上有很多解釋A*算法的文章，但是大多數是寫給那些有一定基礎的人看的，而您看到的這一篇呢，是真正寫給菜鳥的。 本篇文章并不想給這個算法題目作一些權威性論斷，而是闡述它的基本原理，并為你理解更多相關資料與討論打下基礎。文章末尾給出了一些比較好的鏈接，放在“進階閱讀”一節(jié)之后。 最后，本文不是編程規(guī)范，你將可能使這里講述的東西編寫成任何計算機語言。在本文的末尾

2、我還給出了一個例子程序包的下載鏈接，也許正合你意。在這個包中有C+和Blitz Basic兩個版本的程序代碼，如果你只是想看看A*算法是如何運作的，該包中也有可直接執(zhí)行的文件供你研究。 我們還是要超越自己的（把算法弄懂），所以，讓我們從頭開始吧！初步：搜索區(qū)域 我們假設某個人要從A點到達B點，而一堵墻把這兩個點隔開了，如下圖所示，綠色部分代表起點A，紅色部分代表終點B，藍色方塊部分代表之間的墻。圖一你首先會注意到我們把這一塊搜索區(qū)域分成了一個一個的方格，如此這般，使搜索區(qū)域簡單化，正是尋找路徑的第一步。這種方法將我們的搜索區(qū)域簡化成了一個普通的二維數組。數組中的每一個元素表

3、示對應的一個方格，該方格的狀態(tài)被標記為可通過的和不可通過的。通過找出從A點到B點所經過的方格，就能得到AB之間的路徑。當路徑找出來以后，這個人就可以從一個格子中央移動到另一個格子中央，直到抵達目的地。這些格子的中點叫做節(jié)點。當你在其他地方看到有關尋找路徑的東西時，你會經常發(fā)現人們在討論節(jié)點。為什么不直接把它們稱作方格呢？因為你不一定要把你的搜索區(qū)域分隔成方塊，矩形、六邊形或者其他任何形狀都可以。況且節(jié)點還有可能位于這些形狀內的任何一處呢？在中間、靠著邊，或者什么的。我們就用這種設定，因為畢竟這是最簡單的情況。 開始搜索 當我們把搜索區(qū)域簡化成一些很容易操作的節(jié)點后，下一步就

4、要構造一個搜索來尋找最短路徑。在A*算法中，我們從A點開始，依次檢查它的相鄰節(jié)點，然后照此繼續(xù)并向外擴展直到找到目的地。我們通過以下方法來開始搜索：1.       從A點開始，將A點加入一個專門存放待檢驗的方格的“開放列表”中。這個開放列表有點像一張購物清單。當前這個列表中只有一個元素，但一會兒將會有更多。列表中包含的方格可能會是你要途經的方格，也可能不是?？傊@是一個包含待檢驗方格的列表。2.       檢查起點A相鄰的所有可達的或者可通過的方格，不用管墻啊，水啊，或

5、者其他什么無效地形，把它們也都加到開放列表中。對于每一個相鄰方格，將點A保存為它們的“父方格”。當我們要回溯路徑的時候，父方格是一個很重要的元素。稍后我們將詳細解釋它。3.       從開放列表中去掉方格A，并把A加入到一個“封閉列表”中。封閉列表存放的是你現在不用再去考慮的方格。此時你將得到如下圖所示的樣子。在這張圖中，中間深綠色的方格是你的起始方格，所有相鄰方格目前都在開放列表中，并且以亮綠色描邊。每個相鄰方格有一個灰色的指針指向它們的父方格，即起始方格。圖二接下來，我們在開放列表中選一個相鄰方格并再重復幾次如前所述的過程。但是

6、我們該選哪一個方格呢？具有最小F值的那個。 路徑排序 決定哪些方格會形成路徑的關鍵是下面這個等式：F = G + H這里·    G從起點A沿著已生成的路徑到一個給定方格的移動開銷。·    H從給定方格到目的方格的估計移動開銷。這種方式常叫做試探，有點困惑人吧。其實之所以叫做試探法是因為這只是一個猜測。在找到路徑之前我們實際上并不知道實際的距離，因為任何東西都有可能出現在半路上（墻啊，水啊什么的）。本文中給出了一種計算H值的方法，網上還有很多其他文章介紹的不同方法。 我們要的路徑是通過反復遍歷開放列表并

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

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

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

10、垂直移動），H就是40。你可以大概看看其他方格的H值是怎么計算出來的。 每一個方格的F值，當然就不過是G和H值之和了。 繼續(xù)搜索 為了繼續(xù)搜索，我們簡單的從開放列表中選擇具有最小F值的方格，然后對選中的方格進行如下操作：4.       將其從開放列表中移除，并加到封閉列表中。5.       檢驗所有的相鄰方格，忽略那些不可通過的或者已經在封閉列表里的方格。如果這個相鄰方格不在開放列表中，就把它添加進去。并將當前選定方格設為新添方格的父方格。6

11、.       如果某個相鄰方格已經在開放列表中了（意味著已經探測過，而且已經設置過父方格譯者），就看看有沒有到達那個方格的更好的路徑。也就是說，如果從當前選中方格到那個方格，會不會使那個方格的G值更小。如果不能，就不進行任何操作。相反的，如果新路徑的G值更小，就將該相鄰方格的父方格重設為當前選中方格。（在上圖中是改變其指針的方向為指向選中方格。最后，重新計算那個相鄰方格的F和G值。如果你看糊涂了，下面會有圖解說明。好啦，咱們來看看具體點的例子。在初始時的9個方塊中，當開始方格被加到封閉列表后，開放列表里還剩8個方格。在這八個方格當中

12、，位于起點方格右邊的那個方格具有最小的F值40。所以我們選擇這個方格作為下一個中心方格。下圖中它以高亮的藍色表示。圖四首先，我們將選中的方格從開放列表中移除，并加入到封閉列表中（所以用亮藍色標記）。然后再檢驗它的相鄰節(jié)點。那么在它緊鄰的右邊的方格都是墻，所以不管它們。左邊挨著的是起始方格，而起始方格已經在封閉列表中了，所以我們也不管它。其他四個方格已經在開放列表中，那么我們就要檢驗一下如果路徑經由當前選中方格到那些方格的話會不會更好，當然，是用G值作為參考。來看看選中方格右上角的那一個方格，它當前的G值是14，如果我們經由當前節(jié)點再到達那個方格的話，G值會是20（到當前方格的G值是10，然后向

13、上移動一格就再加上10）。為20的G值比14大，因此這樣的路徑不會更好。你看看圖就會容易理解些。顯然從起始點沿斜角方向移動到那個方格比先水平移動一格再垂直移動一格更直接。當我們按如上過程依次檢驗開放列表中的所有四個方格后，會發(fā)現經由當前方格的話不會形成更好的路徑，那我們就保持目前的狀況不變?，F在我們已經處理了所有相鄰方格，準備到下一個方格吧。我們再遍歷一下開放列表，目前只有7個方格了。我們挑個F值最小的吧。有趣的是，目前這種情況下，有兩個F值為54的方格。那我們怎么選擇呢？其實選哪個都沒關系，要考慮到速度的話，選你最近加到開放列表中的那一個會更快些。當離目的地越來越近的時候越偏向于選最后發(fā)現的

14、方格。實際上這個真的沒關系（對待這個的不同造成了兩個版本的A*算法得到等長的不同路徑）。那我們選下面的那個好了，就是起始方格右邊的，下圖所示的那個。圖五這一次，在我們檢驗相鄰方格的時候發(fā)現右邊緊挨的那個是墻，就不管它了。上面挨著的那個也同樣忽略。還有右邊墻下面那個方格我們也不管。為什么呢？因為你不可能切穿墻角直接到達那個格子。實際上你得先向下走然后再通過那個方格。這個過程中是繞著墻角走。（注意：穿過墻角的這個規(guī)則是可選的，取決于你的節(jié)點是如何放置的。）那么還剩下其他五個相鄰方格。當前方格的下面那兩個還不在開放列表中，那我們把它們加進去并且把當前方格作為它們的父方格。其他三個中有兩個已經在封閉列

15、表中了（兩個已經在圖中用亮藍色標記了，起始方格，上面的方格），所以就不用管了。最后那個，當前方格左邊挨著的，要檢查一下經由當前節(jié)點到那里會不會降低它的G值。結果不行，所以我們又處理完畢了，然后去檢驗開放列表中的下一個格子。重復這個過程直到我們把目的方格加入到開放列表中了，那時候看起來會像下圖這個樣子。圖六注意到沒？起始方格下兩格的位置，那里的格子已經和前一張圖不一樣了。之前它的G值是28并且指向右上方的那個方格?，F在它的G值變成了20并且指向了正上方的方格。這個改變是在搜索過程中，它的G值被核查時發(fā)現在某個新路徑下可以變得更小時發(fā)生的。然后它的父方格也被重設并且重新計算了G值和F值。在本例中這

16、個改變看起來好像不是很重要，但是在很多種情況下這種改變會使到達目標的最佳路徑變得非常不同。那么我們怎樣來自動得出實際路徑的呢?很簡單，只要從紅色目標方格開始沿著每一個方格的指針方向移動，依次到達它們的父方格，最終肯定會到達起始方格。那就是你的路徑！如下圖所示。從A方格到B方格的移動就差不多是沿著這個路徑從每個方格中心（節(jié)點）移動到另一個方格中心，直到抵達終點。簡單吧！圖七A*算法總結 1.           將開始節(jié)點放入開放列表(開始節(jié)點的F和G值都視為0);2. 

17、60;         重復一下步驟:            i.        在開放列表中查找具有最小F值的節(jié)點,并把查找到的節(jié)點作為當前節(jié)點;           ii.     &#

18、160;  把當前節(jié)點從開放列表刪除, 加入到封閉列表;         iii.        對當前節(jié)點相鄰的每一個節(jié)點依次執(zhí)行以下步驟:1.     如果該相鄰節(jié)點不可通行或者該相鄰節(jié)點已經在封閉列表中,則什么操作也不執(zhí)行,繼續(xù)檢驗下一個節(jié)點;2.     如果該相鄰節(jié)點不在開放列表中,則將該節(jié)點添加到開放列表中, 并將該相鄰節(jié)點的父節(jié)點設為當前節(jié)點,

19、同時保存該相鄰節(jié)點的G和F值;3.     如果該相鄰節(jié)點在開放列表中, 則判斷若經由當前節(jié)點到達該相鄰節(jié)點的G值是否小于原來保存的G值,若小于,則將該相鄰節(jié)點的父節(jié)點設為當前節(jié)點,并重新設置該相鄰節(jié)點的G和F值.        iv.        循環(huán)結束條件:當終點節(jié)點被加入到開放列表作為待檢驗節(jié)點時, 表示路徑被找到,此時應終止循環(huán);或者當開放列表為空,表明已無可以添加的新節(jié)點,而已檢驗的節(jié)點中沒有終點節(jié)點則

20、意味著路徑無法被找到,此時也結束循環(huán);3.           從終點節(jié)點開始沿父節(jié)點遍歷, 并保存整個遍歷到的節(jié)點坐標,遍歷所得的節(jié)點就是最后得到的路徑; 一點感慨 原諒我的離題。但畢竟值得指出的是，當你在網上和論壇里看到很多討論A*路徑尋找算法的東西時，偶爾會遇到一些人所指的A*算法并不是真正的A*的情況。實際上要應用真正的A*需要包含我們上面討論的那些元素：專門的開放列表和封閉列表，用F、G和H值來排序的路徑統(tǒng)計。有很多其他的尋找路徑算法，但是其他的都不是A*，而A*一

21、般認為是這些算法當中最好的。本文末尾的參考文檔里有Bryan Stout對這些算法的討論。在特定情況下某些算法可能會更好，但是你至少要理解你要準備做什么。好了，差不多了，還是回到主題吧。 實現時的注意事項 現在你已經理解了基本的算法，下面將討論一些你在寫自己的程序時要考慮的東西。下面一些材料和我用C+和Blitz Basic寫的程序有關，但是那些要點是適用于任何其他語言的。1.     開放列表的維護：實際上是A*算法中最耗時的因素。每次你處理開放列表時你都要從中找出具有最小F值的方格。有幾種方法可以做到。你可以保存所需的路徑元素，簡

22、單的遍歷列表來找出最小F值的方格。這種方法是很簡單，但是在路徑很長的時候會很慢。也可以改進一下，變成維護一個有序列表，這樣在需要最小F值方格的時候僅須獲取該有序列表的第一個元素。我在寫我那個程序的時候，開始就是用的這個辦法。這種方法很適合于地圖不大的情況。但這還不是最快的解決辦法。真正追求速度的認真的程序員往往會使用二叉堆。這也是我在我的代碼中用的方法。據我的經驗，這種方法會比大多數解決方案快至少23倍，在路徑很長的時候更快（快10倍以上）。如果你有興趣了解更多二叉堆的內容，去看看我的這篇文章，Using Binary Heaps in A* Pathfinding。2.  

23、;   其他單位。如果你仔細看了我的例子代碼，你會注意到它完全忽略了地圖上的其他單位。我的尋路者實際上是直接穿過彼此的。這樣行得通行不通是取決于游戲的。如果你要考慮地圖上的其他單位并且它們還能夠移動，我建議你在路徑尋找算法中忽略它們而另外寫一些代碼去檢測它們是否發(fā)生了碰撞。當碰撞發(fā)生時，你可以馬上生成一個新的路徑或者應用一些標準移動規(guī)則（比如總是靠右走等等）直到路徑上不再有障礙物或，然后再生成一個新的路徑。為什么在你最初計算路徑的時候就把這些單位考慮進去呢？那其實是因為其他單位也會移動，它們的位置在不停的改變。這樣會導致產生一些不可思議的結果，比如某個單位會突然轉向來避免一

24、個實際上已經不在那兒的另一個單位，或者撞上一個后來移動到它的預定路徑上的單位。在尋路算法中忽略其他單位意味著你將不得不寫一些單獨的代碼來避免沖突。這完全是由游戲特性決定的。所以我把解決方案留給你自己去琢磨。本文末尾參考文章一節(jié)Bryan Stout的一些地方提供了幾個解決方案（比如魯棒式跟蹤等等），不妨去看看。3.     一些提速技巧：你在開發(fā)你自己的A*程序或者改變我寫的那個時，總會發(fā)現這個尋路算法很耗CPU，特別是地圖上有大量的尋路者和地圖相當大的時候。如果你在網上讀過一些資料你會知道這個對于像星際爭霸或者帝國時代這樣專業(yè)的游戲也不例外。當你發(fā)現你

25、的尋路算法使你寫的東西變慢了的話，可以參考下面這些提速的辦法：· 用小一點的地圖或者尋路者少一點。·  不要在同一時間為很多個尋路者計算路徑。不如把它們放進一個隊列里并分散在幾個游戲循環(huán)中。如果你的游戲運行時大約是，比如說，40個循環(huán)/秒的話，沒人會注意到。但是要是有一堆尋路者在同一時間計算路徑而導致游戲在短時間內變慢的話，就非常引人注意了。·  將地圖的區(qū)塊劃分得大一些。這樣會減少搜索路徑時的區(qū)塊總數。如果你夠強，可以設計兩種以上的尋路系統(tǒng)來適應于路徑長度不同的情況。這正是那些專業(yè)人士所做的，路徑長的時候用大區(qū)塊，當接近目標路徑變短的時候又用

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

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

28、。把某個區(qū)塊加上額外的開銷，A*算法仍然有效。在我描述的那個簡單例子里，地形只分可通過和不可通過兩種，A*算法會找到最直接最短的路徑。但當在一個地形多樣化的環(huán)境里時，最小開銷路徑可能會是比較長的一段路程。例如從公路上繞過去顯然比直接通過沼澤地開銷要小。還有一個有趣的辦法是專業(yè)人士們叫做“感應映射”的東西。如同上面描述的多樣化地形開銷一樣，你可以創(chuàng)建一個額外的點數制度并將之應用于AI方面的路徑中。假設在一張地圖上有一堆家伙在守衛(wèi)一個山區(qū)要道，每次電腦派遣某人通過那條要道時都會被困住。那你就可以創(chuàng)建一個感應地圖使得發(fā)生很多戰(zhàn)斗沖突的那些區(qū)塊開銷增大，以此來告知電腦去選一個更安全的路徑，并避免僅憑著是最短路徑（但是更危險）就持續(xù)派遣人員通過某條路徑的愚蠢情形。5.     處理未探索區(qū)域：你有玩過電腦總是知道怎么走，甚至地圖都還沒探索過的PC游戲嗎？由此看來這個路徑尋找算法真是好得不現實。還好這個問題可以很容易解決。方法就是為不同的玩家和電腦（不是每個單位，不然會