|
A*尋路初探 GameDev.net
作者：Patrick Lester
譯者：Panic 2005年3月18日
出處：Panic的小屋
譯者序：很久以前就知道了A*算法，但是從未認(rèn)真讀過(guò)相關(guān)的文章，也沒(méi)有看過(guò)代碼，只是腦子里有個(gè)模糊的概念。這次決定從頭開始，研究一下這個(gè)被人推崇備至的簡(jiǎn)單方法，作為學(xué)習(xí)人工智能的開始。
這篇文章非常知名，國(guó)內(nèi)應(yīng)該有不少人翻譯過(guò)它，我沒(méi)有查找，覺(jué)得翻譯本身也是對(duì)自身英文水平的鍛煉。經(jīng)過(guò)努力，終于完成了文檔，也明白的A*算法的原理。毫無(wú)疑問(wèn)，作者用形象的描述，簡(jiǎn)潔詼諧的語(yǔ)言由淺入深的講述了這一神奇的算法，相信每個(gè)讀過(guò)的人都會(huì)對(duì)此有所認(rèn)識(shí)（如果沒(méi)有，那就是偶的翻譯太差了--b）。
現(xiàn)在是2005年7月19日的版本，應(yīng)原作者要求，對(duì)文中的某些算法細(xì)節(jié)做了修改。
原文鏈接：http://www.gamedev.net/reference/articles/article2003.asp
原作者文章鏈接：http://www.policyalmanac.org/games/aStarTutorial.htm
以下是翻譯的正文。
會(huì)者不難，A*(念作A星)算法對(duì)初學(xué)者來(lái)說(shuō)的確有些難度。
這篇文章并不試圖對(duì)這個(gè)話題作權(quán)威的陳述。取而代之的是，它只是描述算法的原理，使你可以在進(jìn)一步的閱讀中理解其他相關(guān)的資料。
最后，這篇文章沒(méi)有程序細(xì)節(jié)。你盡可以用任意的計(jì)算機(jī)程序語(yǔ)言實(shí)現(xiàn)它。如你所愿，我在文章的末尾包含了一個(gè)指向例子程序的鏈接。 壓縮包包括C++和Blitz Basic兩個(gè)語(yǔ)言的版本，如果你只是想看看它的運(yùn)行效果，里面還包含了可執(zhí)行文件。
我們正在提高自己。讓我們從頭開始。。。
序：搜索區(qū)域
假設(shè)有人想從A點(diǎn)移動(dòng)到一墻之隔的B點(diǎn)，如下圖，綠色的是起點(diǎn)A，紅色是終點(diǎn)B，藍(lán)色方塊是中間的墻。
[圖1]
你首先注意到，搜索區(qū)域被我們劃分成了方形網(wǎng)格。像這樣，簡(jiǎn)化搜索區(qū)域，是尋路的第一步。這一方法把搜索區(qū)域簡(jiǎn)化成了一個(gè)二維數(shù)組。數(shù)組的每一個(gè)元素是網(wǎng)格的一個(gè)方塊，方塊被標(biāo)記為可通過(guò)的和不可通過(guò)的。路徑被描述為從A到B我們經(jīng)過(guò)的方塊的集合。一旦路徑被找到，我們的人就從一個(gè)方格的中心走向另一個(gè)，直到到達(dá)目的地。
這些中點(diǎn)被稱為“節(jié)點(diǎn)”。當(dāng)你閱讀其他的尋路資料時(shí)，你將經(jīng)常會(huì)看到人們討論節(jié)點(diǎn)。為什么不把他們描述為方格呢？因?yàn)橛锌赡苣愕穆窂奖环指畛善渌皇欠礁竦慕Y(jié)構(gòu)。他們完全可以是矩形，六角形，或者其他任意形狀。節(jié)點(diǎn)能夠被放置在形狀的任意位置－可以在中心，或者沿著邊界，或其他什么地方。我們使用這種系統(tǒng)，無(wú)論如何，因?yàn)樗亲詈?jiǎn)單的。
開始搜索
正如我們處理上圖網(wǎng)格的方法，一旦搜索區(qū)域被轉(zhuǎn)化為容易處理的節(jié)點(diǎn)，下一步就是去引導(dǎo)一次找到最短路徑的搜索。在A*尋路算法中，我們通過(guò)從點(diǎn)A開始，檢查相鄰方格的方式，向外擴(kuò)展直到找到目標(biāo)。
我們做如下操作開始搜索：
1，從點(diǎn)A開始，并且把它作為待處理點(diǎn)存入一個(gè)“開啟列表”。開啟列表就像一張購(gòu)物清單。盡管現(xiàn)在列表里只有一個(gè)元素，但以后就會(huì)多起來(lái)。你的路徑可能會(huì)通過(guò)它包含的方格，也可能不會(huì)。基本上，這是一個(gè)待檢查方格的列表。
2，尋找起點(diǎn)周圍所有可到達(dá)或者可通過(guò)的方格，跳過(guò)有墻，水，或其他無(wú)法通過(guò)地形的方格。也把他們加入開啟列表。為所有這些方格保存點(diǎn)A作為“父方格”。當(dāng)我們想描述路徑的時(shí)候，父方格的資料是十分重要的。后面會(huì)解釋它的具體用途。
3，從開啟列表中刪除點(diǎn)A，把它加入到一個(gè)“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。
在這一點(diǎn)，你應(yīng)該形成如圖的結(jié)構(gòu)。在圖中，暗綠色方格是你起始方格的中心。它被用淺藍(lán)色描邊，以表示它被加入到關(guān)閉列表中了。所有的相鄰格現(xiàn)在都在開啟列表中，它們被用淺綠色描邊。每個(gè)方格都有一個(gè)灰色指針?lè)粗杆麄兊母阜礁瘢簿褪情_始的方格。
[圖2]
接著，我們選擇開啟列表中的臨近方格，大致重復(fù)前面的過(guò)程，如下。但是，哪個(gè)方格是我們要選擇的呢？是那個(gè)F值最低的。
路徑評(píng)分
選擇路徑中經(jīng)過(guò)哪個(gè)方格的關(guān)鍵是下面這個(gè)等式：
F = G + H
這里：
* G = 從起點(diǎn)A，沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi)。
* H = 從網(wǎng)格上那個(gè)方格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)耗費(fèi)。這經(jīng)常被稱為啟發(fā)式的，可能會(huì)讓你有點(diǎn)迷惑。這樣叫的原因是因?yàn)樗皇莻�(gè)猜測(cè)。我們沒(méi)辦法事先知道路徑的長(zhǎng)度，因?yàn)槁飞峡赡艽嬖诟鞣N障礙(墻，水，等等)。雖然本文只提供了一種計(jì)算H的方法，但是你可以在網(wǎng)上找到很多其他的方法。
我們的路徑是通過(guò)反復(fù)遍歷開啟列表并且選擇具有最低F值的方格來(lái)生成的。文章將對(duì)這個(gè)過(guò)程做更詳細(xì)的描述。首先，我們更深入的看看如何計(jì)算這個(gè)方程。
正如上面所說(shuō)，G表示沿路徑從起點(diǎn)到當(dāng)前點(diǎn)的移動(dòng)耗費(fèi)。在這個(gè)例子里，我們令水平或者垂直移動(dòng)的耗費(fèi)為10，對(duì)角線方向耗費(fèi)為14。我們?nèi)∵@些值是因?yàn)檠貙?duì)角線的距離是沿水平或垂直移動(dòng)耗費(fèi)的的根號(hào)2（別怕），或者約1.414倍。為了簡(jiǎn)化，我們用10和14近似。比例基本正確，同時(shí)我們避免了求根運(yùn)算和小數(shù)。這不是只因?yàn)槲覀兣侣闊┗蛘卟幌矚g數(shù)學(xué)。使用這樣的整數(shù)對(duì)計(jì)算機(jī)來(lái)說(shuō)也更快捷。你不就就會(huì)發(fā)現(xiàn)，如果你不使用這些簡(jiǎn)化方法，尋路會(huì)變得很慢。
既然我們?cè)谟?jì)算沿特定路徑通往某個(gè)方格的G值，求值的方法就是取它父節(jié)點(diǎn)的G值，然后依照它相對(duì)父節(jié)點(diǎn)是對(duì)角線方向或者直角方向(非對(duì)角線)，分別增加14和10。例子中這個(gè)方法的需求會(huì)變得更多，因?yàn)槲覀儚钠瘘c(diǎn)方格以外獲取了不止一個(gè)方格。
H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對(duì)角線方向。然后把結(jié)果乘以10。這被成為曼哈頓方法是因?yàn)樗雌饋?lái)像計(jì)算城市中從一個(gè)地方到另外一個(gè)地方的街區(qū)數(shù)，在那里你不能沿對(duì)角線方向穿過(guò)街區(qū)。很重要的一點(diǎn)，我們忽略了一切障礙物。這是對(duì)剩余距離的一個(gè)估算，而非實(shí)際值，這也是這一方法被稱為啟發(fā)式的原因。想知道更多？你可以在這里找到方程和額外的注解。
F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。F,G和H的評(píng)分被寫在每個(gè)方格里。正如在緊挨起始格右側(cè)的方格所表示的，F(xiàn)被打印在左上角，G在左下角，H則在右下角。
[圖3]
現(xiàn)在我們來(lái)看看這些方格。寫字母的方格里，G = 10。這是因?yàn)樗辉谒椒较蚱x起始格一個(gè)格距。緊鄰起始格的上方，下方和左邊的方格的G值都等于10。對(duì)角線方向的G值是14。
H值通過(guò)求解到紅色目標(biāo)格的曼哈頓距離得到，其中只在水平和垂直方向移動(dòng)，并且忽略中間的墻。用這種方法，起點(diǎn)右側(cè)緊鄰的方格離紅色方格有3格距離，H值就是30。這塊方格上方的方格有4格距離(記住，只能在水平和垂直方向移動(dòng))，H值是40。你大致應(yīng)該知道如何計(jì)算其他方格的H值了～。
每個(gè)格子的F值，還是簡(jiǎn)單的由G和H相加得到
繼續(xù)搜索
為了繼續(xù)搜索，我們簡(jiǎn)單的從開啟列表中選擇F值最低的方格。然后，對(duì)選中的方格做如下處理：
4，把它從開啟列表中刪除，然后添加到關(guān)閉列表中。
5，檢查所有相鄰格子。跳過(guò)那些已經(jīng)在關(guān)閉列表中的或者不可通過(guò)的(有墻，水的地形，或者其他無(wú)法通過(guò)的地形)，把他們添加進(jìn)開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點(diǎn)。
6，如果某個(gè)相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說(shuō)，檢查如果我們用新的路徑到達(dá)它的話，G值是否會(huì)更低一些。如果不是，那就什么都不做。
另一方面，如果新的G值更低，那就把相鄰方格的父節(jié)點(diǎn)改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個(gè)方格）。最后，重新計(jì)算F和G的值。如果這看起來(lái)不夠清晰，你可以看下面的圖示。
好了，讓我們看看它是怎么運(yùn)作的。我們最初的9格方格中，在起點(diǎn)被切換到關(guān)閉列表中后，還剩8格留在開啟列表中。這里面，F(xiàn)值最低的那個(gè)是起始格右側(cè)緊鄰的格子，它的F值是40。因此我們選擇這一格作為下一個(gè)要處理的方格。在緊隨的圖中，它被用藍(lán)色突出顯示。
[圖4]
首先，我們把它從開啟列表中取出，放入關(guān)閉列表(這就是他被藍(lán)色突出顯示的原因)。然后我們檢查相鄰的格子。哦，右側(cè)的格子是墻，所以我們略過(guò)。左側(cè)的格子是起始格。它在關(guān)閉列表里，所以我們也跳過(guò)它。
其他4格已經(jīng)在開啟列表里了，于是我們檢查G值來(lái)判定，如果通過(guò)這一格到達(dá)那里，路徑是否更好。我們來(lái)看選中格子下面的方格。它的G值是14。如果我們從當(dāng)前格移動(dòng)到那里，G值就會(huì)等于20(到達(dá)當(dāng)前格的G值是10，移動(dòng)到上面的格子將使得G值增加10)。因?yàn)镚值20大于14，所以這不是更好的路徑。如果你看圖，就能理解。與其通過(guò)先水平移動(dòng)一格，再垂直移動(dòng)一格，還不如直接沿對(duì)角線方向移動(dòng)一格來(lái)得簡(jiǎn)單。
當(dāng)我們對(duì)已經(jīng)存在于開啟列表中的4個(gè)臨近格重復(fù)這一過(guò)程的時(shí)候，我們發(fā)現(xiàn)沒(méi)有一條路徑可以通過(guò)使用當(dāng)前格子得到改善，所以我們不做任何改變。既然我們已經(jīng)檢查過(guò)了所有鄰近格，那么就可以移動(dòng)到下一格了。
于是我們檢索開啟列表，現(xiàn)在里面只有7格了，我們?nèi)匀贿x擇其中F值最低的。有趣的是，這次，有兩個(gè)格子的數(shù)值都是54。我們?nèi)绾芜x擇？這并不麻煩。從速度上考慮，選擇最后添加進(jìn)列表的格子會(huì)更快捷。這種導(dǎo)致了尋路過(guò)程中，在靠近目標(biāo)的時(shí)候，優(yōu)先使用新找到的格子的偏好。但這無(wú)關(guān)緊要。（對(duì)相同數(shù)值的不同對(duì)待，導(dǎo)致不同版本的A*算法找到等長(zhǎng)的不同路徑。）
那我們就選擇起始格右下方的格子，如圖。
[圖5]
這次，當(dāng)我們檢查相鄰格的時(shí)候，發(fā)現(xiàn)右側(cè)是墻，于是略過(guò)。上面一格也被略過(guò)。我們也略過(guò)了墻下面的格子。為什么呢？因?yàn)槟悴荒茉诓淮┰綁堑那闆r下直接到達(dá)那個(gè)格子。你的確需要先往下走然后到達(dá)那一格，按部就班的走過(guò)那個(gè)拐角。(注解：穿越拐角的規(guī)則是可選的。它取決于你的節(jié)點(diǎn)是如何放置的。)
這樣一來(lái)，就剩下了其他5格。當(dāng)前格下面的另外兩個(gè)格子目前不在開啟列表中，于是我們添加他們，并且把當(dāng)前格指定為他們的父節(jié)點(diǎn)。其余3格，兩個(gè)已經(jīng)在關(guān)閉列表中（起始格，和當(dāng)前格上方的格子，在表格中藍(lán)色高亮顯示),于是我們略過(guò)它們。最后一格，在當(dāng)前格的左側(cè)，將被檢查通過(guò)這條路徑，G值是否更低。不必?fù)?dān)心，我們已經(jīng)準(zhǔn)備好檢查開啟列表中的下一格了。
我們重復(fù)這個(gè)過(guò)程，直到目標(biāo)格被添加進(jìn)關(guān)閉列表(注解)，就如在下面的圖中所看到的。
[圖6]
注意，起始格下方格子的父節(jié)點(diǎn)已經(jīng)和前面不同的。之前它的G值是28，并且指向右上方的格子�，F(xiàn)在它的G值是20，指向它上方的格子。這在尋路過(guò)程中的某處發(fā)生，當(dāng)應(yīng)用新路徑時(shí)，G值經(jīng)過(guò)檢查變得低了－于是父節(jié)點(diǎn)被重新指定，G和F值被重新計(jì)算。盡管這一變化在這個(gè)例子中并不重要，在很多場(chǎng)合，這種變化會(huì)導(dǎo)致尋路結(jié)果的巨大變化。
那么，我們?cè)趺创_定這條路徑呢？很簡(jiǎn)單，從紅色的目標(biāo)格開始，按箭頭的方向朝父節(jié)點(diǎn)移動(dòng)。這最終會(huì)引導(dǎo)你回到起始格，這就是你的路徑！看起來(lái)應(yīng)該像圖中那樣。從起始格A移動(dòng)到目標(biāo)格B只是簡(jiǎn)單的從每個(gè)格子（節(jié)點(diǎn)）的中點(diǎn)沿路徑移動(dòng)到下一個(gè)，直到你到達(dá)目標(biāo)點(diǎn)。就這么簡(jiǎn)單。
[圖7]
出處：藍(lán)色理想
責(zé)任編輯：藍(lán)色月光
上一頁(yè) Chapter 2. 詳細(xì)代碼及說(shuō)明 下一頁(yè) Chapter 4. A*方法總結(jié)
◎進(jìn)入論壇Flash專欄版塊參加討論
|
第 1 頁(yè) 
第 3 頁(yè) Chapter 3. A*尋路初探
