A*算法入門

在看下面這篇文章之前，先介紹幾個(gè)理論知識(shí)，有助于理解A*算法。

啟發(fā)式搜索：?jiǎn)l(fā)式搜索就是在狀態(tài)空間中的搜索對(duì)每一個(gè)搜索的位置進(jìn)行評(píng)估，得到最好的位置，再?gòu)倪@個(gè)位置進(jìn)行搜索直到目標(biāo)。這樣可以省略大量無(wú)畏的搜索路徑，提到了效率。在啟發(fā)式搜索中，對(duì)位置的估價(jià)是十分重要的。采用了不同的估價(jià)可以有不同的效果。

估價(jià)函數(shù)：從當(dāng)前節(jié)點(diǎn)移動(dòng)到目標(biāo)節(jié)點(diǎn)的預(yù)估費(fèi)用；這個(gè)估計(jì)就是啟發(fā)式的。在尋路問(wèn)題和迷宮問(wèn)題中，我們通常用曼哈頓（manhattan）估價(jià)函數(shù)（下文有介紹）預(yù)估費(fèi)用。

A*算法與BFS：可以這樣說(shuō)，BFS是A*算法的一個(gè)特例。對(duì)于一個(gè)BFS算法，從當(dāng)前節(jié)點(diǎn)擴(kuò)展出來(lái)的每一個(gè)節(jié)點(diǎn)（如果沒(méi)有被訪問(wèn)過(guò)的話）都要放進(jìn)隊(duì)列進(jìn)行進(jìn)一步擴(kuò)展。也就是說(shuō)BFS的估計(jì)函數(shù)h永遠(yuǎn)等于0，沒(méi)有一點(diǎn)啟發(fā)式的信息，可以認(rèn)為BFS是“最爛的”A*算法。

選取最小估價(jià)：如果學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的話，應(yīng)該可以知道，對(duì)于每次都要選取最小估價(jià)的節(jié)點(diǎn)，應(yīng)該用到最小優(yōu)先級(jí)隊(duì)列（也叫最小二叉堆）。在C++的STL里有現(xiàn)成的數(shù)據(jù)結(jié)構(gòu)priority_queue，可以直接使用。當(dāng)然不要忘了重載自定義節(jié)點(diǎn)的比較操作符。

A*算法的特點(diǎn)：A*算法在理論上是時(shí)間最優(yōu)的，但是也有缺點(diǎn)：它的空間增長(zhǎng)是指數(shù)級(jí)別的。

IDA*算法：這種算法被稱為迭代加深A*算法，可以有效的解決A*空間增長(zhǎng)帶來(lái)的問(wèn)題，甚至可以不用到優(yōu)先級(jí)隊(duì)列。如果要知道詳細(xì)：google一下。

A*尋路初探（轉(zhuǎn)載）

作者：Patrick Lester

譯者：Panic2005年

譯者序：很久以前就知道了A*算法，但是從未認(rèn)真讀過(guò)相關(guān)的文章，也沒(méi)有看過(guò)代碼，只是腦子里有個(gè)模糊的概念。這次決定從頭開(kāi)始，研究一下這個(gè)被人推崇備至的簡(jiǎn)單方法，作為學(xué)習(xí)人工智能的開(kāi)始。

這篇文章非常知名，國(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)在是年月日的版本，應(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í)行文件。我們正在提高自己。讓我們從頭開(kāi)始。。。

序：搜索區(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)單的。

開(kāi)始搜索

正如我們處理上圖網(wǎng)格的方法，一旦搜索區(qū)域被轉(zhuǎn)化為容易處理的節(jié)點(diǎn)，下一步就是去引導(dǎo)一次找到最短路徑的搜索。在A*尋路算法中，我們通過(guò)從點(diǎn)A開(kāi)始，檢查相鄰方格的方式，向外擴(kuò)展直到找到目標(biāo)。

我們做如下操作開(kāi)始搜索：

   1，從點(diǎn)A開(kāi)始，并且把它作為待處理點(diǎn)存入一個(gè)“開(kāi)啟列表”。開(kāi)啟列表就像一張購(gòu)物清單。盡管現(xiàn)在列表里只有一個(gè)元素，但以后就會(huì)多起來(lái)。你的路徑可能會(huì)通過(guò)它包含的方格，也可能不會(huì)。基本上，這是一個(gè)待檢查方格的列表。

   2，尋找起點(diǎn)周圍所有可到達(dá)或者可通過(guò)的方格，跳過(guò)有墻，水，或其他無(wú)法通過(guò)地形的方格。也把他們加入開(kāi)啟列表。為所有這些方格保存點(diǎn)A作為“父方格”。當(dāng)我們想描述路徑的時(shí)候，父方格的資料是十分重要的。后面會(huì)解釋它的具體用途。

   3，從開(kāi)啟列表中刪除點(diǎn)A，把它加入到一個(gè)“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。在這一點(diǎn)，你應(yīng)該形成如圖的結(jié)構(gòu)。在圖中，暗綠色方格是你起始方格的中心。它被用淺藍(lán)色描邊，以表示它被加入到關(guān)閉列表中了。所有的相鄰格現(xiàn)在都在開(kāi)啟列表中，它們被用淺綠色描邊。每個(gè)方格都有一個(gè)灰色指針?lè)粗杆麄兊母阜礁瘢簿褪情_(kāi)始的方格。

[圖-2]

接著，我們選擇開(kāi)啟列表中的臨近方格，大致重復(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ù)遍歷開(kāi)啟列表并且選擇具有最低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)為，對(duì)角線方向耗費(fèi)為。我們?nèi)∵@些值是因?yàn)檠貙?duì)角線的距離是沿水平或垂直移動(dòng)耗費(fèi)的的根號(hào)（別怕），或者約.414倍。為了簡(jiǎn)化，我們用和近似。比例基本正確，同時(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ì)角線)，分別增加和。例子中這個(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被打印在左上角，G在左下角，H則在右下角。

[圖-3]

現(xiàn)在我們來(lái)看看這些方格。寫字母的方格里，G = 10。這是因?yàn)樗辉谒椒较蚱x起始格一個(gè)格距。緊鄰起始格的上方，下方和左邊的方格的G值都等于。對(duì)角線方向的G值是。

H值通過(guò)求解到紅色目標(biāo)格的曼哈頓距離得到，其中只在水平和垂直方向移動(dòng)，并且忽略中間的墻。用這種方法，起點(diǎn)右側(cè)緊鄰的方格離紅色方格有格距離，H值就是。這塊方格上方的方格有格距離(記住，只能在水平和垂直方向移動(dòng))，H值是。你大致應(yīng)該知道如何計(jì)算其他方格的H值了～。每個(gè)格子的F值，還是簡(jiǎn)單的由G和H相加得到

繼續(xù)搜索

為了繼續(xù)搜索，我們簡(jiǎn)單的從開(kāi)啟列表中選擇F值最低的方格。然后，對(duì)選中的方格做如下處理：

   4，把它從開(kāi)啟列表中刪除，然后添加到關(guān)閉列表中。

   5，檢查所有相鄰格子。跳過(guò)那些已經(jīng)在關(guān)閉列表中的或者不可通過(guò)的(有墻，水的地形，或者其他無(wú)法通過(guò)的地形)，把他們添加進(jìn)開(kāi)啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點(diǎn)。

   6，如果某個(gè)相鄰格已經(jīng)在開(kāi)啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說(shuō)，檢查如果我們用新的路徑到達(dá)它的話，G值是否會(huì)更低一些。如果不是，那就什么都不做。

      另一方面，如果新的G值更低，那就把相鄰方格的父節(jié)點(diǎn)改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個(gè)方格）。最后，重新計(jì)算F和G的值。如果這看起來(lái)不夠清晰，你可以看下面的圖示。

好了，讓我們看看它是怎么運(yùn)作的。我們最初的格方格中，在起點(diǎn)被切換到關(guān)閉列表中后，還剩格留在開(kāi)啟列表中。這里面，F值最低的那個(gè)是起始格右側(cè)緊鄰的格子，它的F值是。因此我們選擇這一格作為下一個(gè)要處理的方格。在緊隨的圖中，它被用藍(lán)色突出顯示。

[圖-4]

首先，我們把它從開(kāi)啟列表中取出，放入關(guān)閉列表(這就是他被藍(lán)色突出顯示的原因)。然后我們檢查相鄰的格子。哦，右側(cè)的格子是墻，所以我們略過(guò)。左側(cè)的格子是起始格。它在關(guān)閉列表里，所以我們也跳過(guò)它。

其他格已經(jīng)在開(kāi)啟列表里了，于是我們檢查G值來(lái)判定，如果通過(guò)這一格到達(dá)那里，路徑是否更好。我們來(lái)看選中格子下面的方格。它的G值是。如果我們從當(dāng)前格移動(dòng)到那里，G值就會(huì)等于(到達(dá)當(dāng)前格的G值是，移動(dòng)到上面的格子將使得G值增加)。因?yàn)?span>G值大于，所以這不是更好的路徑。如果你看圖，就能理解。與其通過(guò)先水平移動(dòng)一格，再垂直移動(dòng)一格，還不如直接沿對(duì)角線方向移動(dòng)一格來(lái)得簡(jiǎn)單。

當(dāng)我們對(duì)已經(jīng)存在于開(kāi)啟列表中的個(gè)臨近格重復(fù)這一過(guò)程的時(shí)候，我們發(fā)現(xiàn)沒(méi)有一條路徑可以通過(guò)使用當(dāng)前格子得到改善，所以我們不做任何改變。既然我們已經(jīng)檢查過(guò)了所有鄰近格，那么就可以移動(dòng)到下一格了。

于是我們檢索開(kāi)啟列表，現(xiàn)在里面只有7格了，我們?nèi)匀贿x擇其中F值最低的。有趣的是，這次，有兩個(gè)格子的數(shù)值都是。我們?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)，就剩下了其他格。當(dāng)前格下面的另外兩個(gè)格子目前不在開(kāi)啟列表中，于是我們添加他們，并且把當(dāng)前格指定為他們的父節(jié)點(diǎn)。其余格，兩個(gè)已經(jīng)在關(guān)閉列表中（起始格，和當(dāng)前格上方的格子，在表格中藍(lán)色高亮顯示),于是我們略過(guò)它們。最后一格，在當(dāng)前格的左側(cè)，將被檢查通過(guò)這條路徑，G值是否更低。不必?fù)?dān)心，我們已經(jīng)準(zhǔn)備好檢查開(kāi)啟列表中的下一格了。

我們重復(fù)這個(gè)過(guò)程，直到目標(biāo)格被添加進(jìn)關(guān)閉列表(注解)，就如在下面的圖中所看到的。

[圖-6]

注意，起始格下方格子的父節(jié)點(diǎn)已經(jīng)和前面不同的。之前它的G值是，并且指向右上方的格子。現(xiàn)在它的G值是，指向它上方的格子。這在尋路過(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)格開(kāi)始，按箭頭的方向朝父節(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]

A*方法總結(jié)

好，現(xiàn)在你已經(jīng)看完了整個(gè)說(shuō)明，讓我們把每一步的操作寫在一起：

   1，把起始格添加到開(kāi)啟列表。

   2，重復(fù)如下的工作：

      a) 尋找開(kāi)啟列表中F值最低的格子。我們稱它為當(dāng)前格。

      b) 把它切換到關(guān)閉列表。

      c) 對(duì)相鄰的格中的每一個(gè)？

          * 如果它不可通過(guò)或者已經(jīng)在關(guān)閉列表中，略過(guò)它。反之如下。

          * 如果它不在開(kāi)啟列表中，把它添加進(jìn)去。把當(dāng)前格作為這一格的父節(jié)點(diǎn)。記錄這一格的F,G,和H值。

          * 如果它已經(jīng)在開(kāi)啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節(jié)點(diǎn)改成當(dāng)前格，并且重新計(jì)算這一格的G和F值。如果你保持你的開(kāi)啟列表按F值排序，改變之后你可能需要重新對(duì)開(kāi)啟列表排序。

      d) 停止，當(dāng)你

          * 把目標(biāo)格添加進(jìn)了關(guān)閉列表(注解)，這時(shí)候路徑被找到，或者

          * 沒(méi)有找到目標(biāo)格，開(kāi)啟列表已經(jīng)空了。這時(shí)候，路徑不存在。

   3.保存路徑。從目標(biāo)格開(kāi)始，沿著每一格的父節(jié)點(diǎn)移動(dòng)直到回到起始格。這就是你的路徑。

(注解:在這篇文章的較早版本中，建議的做法是當(dāng)目標(biāo)格（或節(jié)點(diǎn)）被加入到開(kāi)啟列表，而不是關(guān)閉列表的時(shí)候停止尋路。這么做會(huì)更迅速，而且?guī)缀蹩偸悄苷业阶疃痰穆窂剑皇墙^對(duì)的。當(dāng)從倒數(shù)第二個(gè)節(jié)點(diǎn)到最后一個(gè)（目標(biāo)節(jié)點(diǎn)）之間的移動(dòng)耗費(fèi)懸殊很大時(shí)－例如剛好有一條河穿越兩個(gè)節(jié)點(diǎn)中間，這時(shí)候舊的做法和新的做法就會(huì)有顯著不同。)

題外話

離題一下，見(jiàn)諒，值得一提的是，當(dāng)你在網(wǎng)上或者相關(guān)論壇看到關(guān)于A*的不同的探討，你有時(shí)會(huì)看到一些被當(dāng)作A*算法的代碼而實(shí)際上他們不是。要使用A*，你必須包含上面討論的所有元素－－特定的開(kāi)啟和關(guān)閉列表，用F,G和H作路徑評(píng)價(jià)。有很多其他的尋路算法，但他們并不是A*，A*被認(rèn)為是他們當(dāng)中最好的。Bryan Stout在這篇文章后面的參考文檔中論述了一部分，包括他們的一些優(yōu)點(diǎn)和缺點(diǎn)。有時(shí)候特定的場(chǎng)合其他算法會(huì)更好，但你必須很明確你在作什么。好了，夠多的了。回到文章。

實(shí)現(xiàn)的注解

現(xiàn)在你已經(jīng)明白了基本原理，寫你的程序的時(shí)候還得考慮一些額外的東西。下面這些材料中的一些引用了我用C++和Blitz Basic寫的程序，但對(duì)其他語(yǔ)言寫的代碼同樣有效。

1.其他單位(避免碰撞)：如果你恰好看了我的例子代碼，你會(huì)發(fā)現(xiàn)它完全忽略了其他單位。我的尋路者事實(shí)上可以相互穿越。取決于具體的游戲，這也許可以，也許不行。如果你打算考慮其他單位，希望他們能互相繞過(guò)，我建議你只考慮靜止或那些在計(jì)算路徑時(shí)臨近當(dāng)前單位的單位，把它們當(dāng)前的位置標(biāo)志為可通過(guò)的。對(duì)于臨近的運(yùn)動(dòng)著的單位，你可以通過(guò)懲罰它們各自路徑上的節(jié)點(diǎn)，來(lái)鼓勵(lì)這些尋路者找到不同的路徑(更多的描述見(jiàn)#2).

如果你選擇了把其他正在移動(dòng)并且遠(yuǎn)離當(dāng)前尋路單位的那些單位考慮在內(nèi)，你將需要實(shí)現(xiàn)一種方法及時(shí)預(yù)測(cè)在何時(shí)何地碰撞可能會(huì)發(fā)生，以便恰當(dāng)?shù)谋苊狻７駝t你極有可能得到一條怪異的路徑，單位突然轉(zhuǎn)彎試圖避免和一個(gè)已經(jīng)不存在的單位發(fā)生碰撞。

當(dāng)然，你也需要寫一些碰撞檢測(cè)的代碼，因?yàn)闊o(wú)論計(jì)算的時(shí)候路徑有多完美，它也會(huì)因時(shí)間而改變。當(dāng)碰撞發(fā)生時(shí)，一個(gè)單位必須尋找一條新路徑，或者，如果另一個(gè)單位正在移動(dòng)并且不是正面碰撞，在繼續(xù)沿當(dāng)前路徑移動(dòng)之前，等待那個(gè)單位離開(kāi)。

這些提示大概可以讓你開(kāi)始了。如果你想了解更多，這里有些你可能會(huì)覺(jué)得有用的鏈接：

    *自治角色的指導(dǎo)行為：Craig Reynold在指導(dǎo)能力上的工作和尋路有些不同，但是它可以和尋路整合從而形成更完整的移動(dòng)和碰撞檢測(cè)系統(tǒng)。

    *電腦游戲中的長(zhǎng)短距指導(dǎo)：指導(dǎo)和尋路方面著作的一個(gè)有趣的考察。這是一個(gè)pdf文件。

    *協(xié)同單位移動(dòng)：一個(gè)兩部分系列文章的第一篇，內(nèi)容是關(guān)于編隊(duì)和基于分組的移動(dòng)，作者是帝國(guó)時(shí)代(Age of Empires)的設(shè)計(jì)者Dave Pottinger.

    *實(shí)現(xiàn)協(xié)同移動(dòng)：Dave Pottinger文章系列的第二篇。

2. 不同的地形損耗：在這個(gè)教程和我附帶的程序中，地形只能是二者之－可通過(guò)的和不可通過(guò)的。但是你可能會(huì)需要一些可通過(guò)的地形，但是移動(dòng)耗費(fèi)更高－沼澤，小山，地牢的樓梯，等等。這些都是可通過(guò)但是比平坦的開(kāi)闊地移動(dòng)耗費(fèi)更高的地形。類似的，道路應(yīng)該比自然地形移動(dòng)耗費(fèi)更低。

這個(gè)問(wèn)題很容易解決，只要在計(jì)算任何地形的G值的時(shí)候增加地形損耗就可以了。簡(jiǎn)單的給它增加一些額外的損耗就可以了。由于A*算法已經(jīng)按照尋找最低耗費(fèi)的路徑來(lái)設(shè)計(jì)，所以很容易處理這種情況。在我提供的這個(gè)簡(jiǎn)單的例子里，地形只有可通過(guò)和不可通過(guò)兩種，A*會(huì)找到最短，最直接的路徑。但是在地形耗費(fèi)不同的場(chǎng)合，耗費(fèi)最低的路徑也許會(huì)包含很長(zhǎng)的移動(dòng)距離－就像沿著路繞過(guò)沼澤而不是直接穿過(guò)它。

一種需額外考慮的情況是被專家稱之為“influence mapping”的東西（暫譯為影響映射圖）。就像上面描述的不同地形耗費(fèi)一樣，你可以創(chuàng)建一格額外的分?jǐn)?shù)系統(tǒng)，并把它應(yīng)用到尋路的AI中。假設(shè)你有一張有大批尋路者的地圖，他們都要通過(guò)某個(gè)山區(qū)。每次電腦生成一條通過(guò)那個(gè)關(guān)口的路徑，它就會(huì)變得更擁擠。如果你愿意，你可以創(chuàng)建一個(gè)影響映射圖對(duì)有大量屠殺事件的格子施以不利影響。這會(huì)讓計(jì)算機(jī)更傾向安全些的路徑，并且?guī)椭苊饪偸莾H僅因?yàn)槁窂蕉?span>(但可能更危險(xiǎn))而持續(xù)把隊(duì)伍和尋路者送到某一特定路徑。

另一個(gè)可能得應(yīng)用是懲罰周圍移動(dòng)單位路徑上得節(jié)點(diǎn)。A*的一個(gè)底限是，當(dāng)一群?jiǎn)挝煌瑫r(shí)試圖尋路到接近的地點(diǎn)，這通常會(huì)導(dǎo)致路徑交疊。以為一個(gè)或者多個(gè)單位都試圖走相同或者近似的路徑到達(dá)目的地。對(duì)其他單位已經(jīng)“認(rèn)領(lǐng)”了的節(jié)點(diǎn)增加一些懲罰會(huì)有助于你在一定程度上分離路徑，降低碰撞的可能性。然而，如果有必要，不要把那些節(jié)點(diǎn)看成不可通過(guò)的，因?yàn)槟闳匀幌Ｍ鄠€(gè)單位能夠一字縱隊(duì)通過(guò)擁擠的出口。同時(shí)，你只能懲罰那些臨近單位的路徑，而不是所有路徑，否則你就會(huì)得到奇怪的躲避行為例如單位躲避路徑上其他已經(jīng)不在那里的單位。還有，你應(yīng)該只懲罰路徑當(dāng)前節(jié)點(diǎn)和隨后的節(jié)點(diǎn)，而不應(yīng)處理已經(jīng)走過(guò)并甩在身后的節(jié)點(diǎn)。

3. 處理未知區(qū)域：你是否玩過(guò)這樣的PC游戲，電腦總是知道哪條路是正確的，即使它還沒(méi)有偵察過(guò)地圖？對(duì)于游戲，尋路太好會(huì)顯得不真實(shí)。幸運(yùn)的是，這是一格可以輕易解決的問(wèn)題。

答案就是為每個(gè)不同的玩家和電腦（每個(gè)玩家，而不是每個(gè)單位－－那樣的話會(huì)耗費(fèi)大量的內(nèi)存）創(chuàng)建一個(gè)獨(dú)立的“knownWalkability”數(shù)組，每個(gè)數(shù)組包含玩家已經(jīng)探索過(guò)的區(qū)域，以及被當(dāng)作可通過(guò)區(qū)域的其他區(qū)域，直到被證實(shí)。用這種方法，單位會(huì)在路的死端徘徊并且導(dǎo)致錯(cuò)誤的選擇直到他們?cè)谥車业铰贰Ｒ坏┑貓D被探索了，尋路就像往常那樣進(jìn)行。

4. 平滑路徑：盡管A*提供了最短，最低代價(jià)的路徑，它無(wú)法自動(dòng)提供看起來(lái)平滑的路徑。看一下我們的例子最終形成的路徑（在圖）。最初的一步是起始格的右下方，如果這一步是直接往下的話，路徑不是會(huì)更平滑一些嗎？有幾種方法來(lái)解決這個(gè)問(wèn)題。當(dāng)計(jì)算路徑的時(shí)候可以對(duì)改變方向的格子施加不利影響，對(duì)G值增加額外的數(shù)值。也可以換種方法，你可以在路徑計(jì)算完之后沿著它跑一遍，找那些用相鄰格替換會(huì)讓路徑看起來(lái)更平滑的地方。想知道完整的結(jié)果，查看Toward More Realistic Pathfinding，一篇(免費(fèi)，但是需要注冊(cè))Marco Pinter發(fā)表在Gamasutra.com的文章

5. 非方形搜索區(qū)域：在我們的例子里，我們使用簡(jiǎn)單的D方形圖。你可以不使用這種方式。你可以使用不規(guī)則形狀的區(qū)域。想想冒險(xiǎn)棋的游戲，和游戲中那些國(guó)家。你可以設(shè)計(jì)一個(gè)像那樣的尋路關(guān)卡。為此，你可能需要建立一個(gè)國(guó)家相鄰關(guān)系的表格，和從一個(gè)國(guó)家移動(dòng)到另一個(gè)的G值。你也需要估算H值的方法。其他的事情就和例子中完全一樣了。當(dāng)你需要向開(kāi)啟列表中添加新元素的時(shí)候，不需使用相鄰的格子，取而代之的是從表格中尋找相鄰的國(guó)家。

類似的，你可以為一張確定的地形圖創(chuàng)建路徑點(diǎn)系統(tǒng)，路徑點(diǎn)一般是路上，或者地牢通道的轉(zhuǎn)折點(diǎn)。作為游戲設(shè)計(jì)者，你可以預(yù)設(shè)這些路徑點(diǎn)。兩個(gè)路徑點(diǎn)被認(rèn)為是相鄰的如果他們之間的直線上沒(méi)有障礙的話。在冒險(xiǎn)棋的例子里，你可以保存這些相鄰信息在某個(gè)表格里，當(dāng)需要在開(kāi)啟列表中添加元素的時(shí)候使用它。然后你就可以記錄關(guān)聯(lián)的G值（可能使用兩點(diǎn)間的直線距離），H值（可以使用到目標(biāo)點(diǎn)的直線距離），其他都按原先的做就可以了。Amit Patel 寫了其他方法的摘要。另一個(gè)在非方形區(qū)域搜索RPG地圖的例子，查看我的文章Two-Tiered A* Pathfinding。(譯者注：譯文： A*分層尋路)

6. 一些速度方面的提示：當(dāng)你開(kāi)發(fā)你自己的A*程序，或者改寫我的，你會(huì)發(fā)現(xiàn)尋路占據(jù)了大量的CPU時(shí)間，尤其是在大地圖上有大量對(duì)象在尋路的時(shí)候。如果你閱讀過(guò)網(wǎng)上的其他材料，你會(huì)明白，即使是開(kāi)發(fā)了星際爭(zhēng)霸或帝國(guó)時(shí)代的專家，這也無(wú)可奈何。如果你覺(jué)得尋路太過(guò)緩慢，這里有一些建議也許有效：

    * 使用更小的地圖或者更少的尋路者。

    * 不要同時(shí)給多個(gè)對(duì)象尋路。取而代之的是把他們加入一個(gè)隊(duì)列，把尋路過(guò)程分散在幾個(gè)游戲周期中。如果你的游戲以周期每秒的速度運(yùn)行，沒(méi)人能察覺(jué)。但是當(dāng)大量尋路者計(jì)算自己路徑的時(shí)候,他們會(huì)發(fā)覺(jué)游戲速度突然變慢。

    * 盡量使用更大的地圖網(wǎng)格。這降低了尋路中搜索的總網(wǎng)格數(shù)。如果你有志氣，你可以設(shè)計(jì)兩個(gè)或者更多尋路系統(tǒng)以便使用在不同場(chǎng)合，取決于路徑的長(zhǎng)度。這也正是專業(yè)人士的做法，用大的區(qū)域計(jì)算長(zhǎng)的路徑，然后在接近目標(biāo)的時(shí)候切換到使用小格子/區(qū)域的精細(xì)尋路。如果你對(duì)這個(gè)觀點(diǎn)感興趣，查閱我的文章Two-Tiered A* Pathfinding。(譯者注：譯文:A*分層尋路)

    * 使用路徑點(diǎn)系統(tǒng)計(jì)算長(zhǎng)路徑，或者預(yù)先計(jì)算好路徑并加入到游戲中。

    * 預(yù)處理你的地圖，表明地圖中哪些區(qū)域是不可到達(dá)的。我把這些區(qū)域稱作“孤島”。事實(shí)上，他們可以是島嶼或其他被墻壁包圍等無(wú)法到達(dá)的任意區(qū)域。A*的下限是，當(dāng)你告訴它要尋找通往那些區(qū)域的路徑時(shí)，它會(huì)搜索整個(gè)地圖，直到所有可到達(dá)的方格/節(jié)點(diǎn)都被通過(guò)開(kāi)啟列表和關(guān)閉列表的計(jì)算。這會(huì)浪費(fèi)大量的CPU時(shí)間。可以通過(guò)預(yù)先確定這些區(qū)域（比如通過(guò)flood-fill或類似的方法)來(lái)避免這種情況的發(fā)生,用某些種類的數(shù)組記錄這些信息，在開(kāi)始尋路前檢查它。

    * 在一個(gè)擁擠的類似迷宮的場(chǎng)合，把不能連通的節(jié)點(diǎn)看作死端。這些區(qū)域可以在地圖編輯器中預(yù)先手動(dòng)指定，或者如果你有雄心壯志，開(kāi)發(fā)一個(gè)自動(dòng)識(shí)別這些區(qū)域的算法。給定死端的所有節(jié)點(diǎn)可以被賦予一個(gè)唯一的標(biāo)志數(shù)字。然后你就可以在尋路過(guò)程中安全的忽略所有死端，只有當(dāng)起點(diǎn)或者終點(diǎn)恰好在死端的某個(gè)節(jié)點(diǎn)的時(shí)候才需要考慮它們。

7. 維護(hù)開(kāi)啟列表：這是A*尋路算法最重要的組成部分。每次你訪問(wèn)開(kāi)啟列表，你都需要尋找F值最低的方格。有幾種不同的方法實(shí)現(xiàn)這一點(diǎn)。你可以把路徑元素隨意保存，當(dāng)需要尋找F值最低的元素的時(shí)候，遍歷開(kāi)啟列表。這很簡(jiǎn)單，但是太慢了，尤其是對(duì)長(zhǎng)路徑來(lái)說(shuō)。這可以通過(guò)維護(hù)一格排好序的列表來(lái)改善，每次尋找F值最低的方格只需要選取列表的首元素。當(dāng)我自己實(shí)現(xiàn)的時(shí)候，這種方法是我的首選。

在小地圖。這種方法工作的很好，但它并不是最快的解決方案。更苛求速度的A*程序員使用叫做二叉堆的方法，這也是我在代碼中使用的方法。憑我的經(jīng)驗(yàn)，這種方法在大多數(shù)場(chǎng)合會(huì)快～倍，并且在長(zhǎng)路經(jīng)上速度呈幾何級(jí)數(shù)提升(10倍以上速度)。如果你想了解更多關(guān)于二叉堆的內(nèi)容，查閱我的文章，Using Binary Heaps in A* Pathfinding。(譯者注：譯文：在A*尋路中使用二叉堆)

另一個(gè)可能的瓶頸是你在多次尋路之間清除和保存你的數(shù)據(jù)結(jié)構(gòu)的方法。我個(gè)人更傾向把所有東西都存儲(chǔ)在數(shù)組里面。雖然節(jié)點(diǎn)可以以面向?qū)ο蟮娘L(fēng)格被動(dòng)態(tài)的產(chǎn)生，記錄和保存，我發(fā)現(xiàn)創(chuàng)建和刪除對(duì)象所增加的大量時(shí)間，以及多余的管理層次減慢的整個(gè)過(guò)程的速度。但是，如果你使用數(shù)組，你需要在調(diào)用之間清理數(shù)據(jù)。這中情形你想做的最后一件事就是在尋路調(diào)用之后花點(diǎn)時(shí)間把一切歸零，尤其是你的地圖很大的時(shí)候。

我通過(guò)使用一個(gè)叫做whichList(x,y)的二維數(shù)組避免這種開(kāi)銷，數(shù)組的每個(gè)元素表明了節(jié)點(diǎn)在開(kāi)啟列表還是在關(guān)閉列表中。嘗試尋路之后，我沒(méi)有清零這個(gè)數(shù)組。取而代之的是，我在新的尋路中重置onClosedList和onOpenList的數(shù)值，每次尋路兩個(gè)都+5或者類似其他數(shù)值。這種方法，算法可以安全的跳過(guò)前面尋路留下的臟數(shù)據(jù)。我還在數(shù)組中儲(chǔ)存了諸如F,G和H的值。這樣一來(lái)，我只需簡(jiǎn)單的重寫任何已經(jīng)存在的值而無(wú)需被清除數(shù)組的操作干擾。將數(shù)據(jù)存儲(chǔ)在多維數(shù)組中需要更多內(nèi)存，所以這里需要權(quán)衡利弊。最后，你應(yīng)該使用你最得心應(yīng)手的方法。

8. Dijkstra的算法：盡管A*被認(rèn)為是通常最好的尋路算法(看前面的“題外話”),還是有一種另外的算法有它的可取之處-Dijkstra算法。Dijkstra算法和A*本質(zhì)是相同的，只有一點(diǎn)不同，就是Dijkstra算法沒(méi)有啟發(fā)式(H值總是)。由于沒(méi)有啟發(fā)式，它在各個(gè)方向上平均搜索。正如你所預(yù)料，由于Dijkstra算法在找到目標(biāo)前通常會(huì)探索更大的區(qū)域，所以一般會(huì)比A*更慢一些。

那么為什么要使用這種算法呢？因?yàn)橛袝r(shí)候我們并不知道目標(biāo)的位置。比如說(shuō)你有一個(gè)資源采集單位，需要獲取某種類型的資源若干。它可能知道幾個(gè)資源區(qū)域，但是它想去最近的那個(gè)。這種情況，Dijkstra算法就比A*更適合，因?yàn)槲覀儾恢滥膫€(gè)更近。用A*，我們唯一的選擇是依次對(duì)每個(gè)目標(biāo)許路并計(jì)算距離，然后選擇最近的路徑。我們尋找的目標(biāo)可能會(huì)有不計(jì)其數(shù)的位置，我們只想找其中最近的，而我們并不知道它在哪里，或者不知道哪個(gè)是最近的。

看完上面的介紹，再來(lái)看一個(gè)比較經(jīng)典的題目:knight moves。貌似也叫漢密爾頓路徑，具體的我也不記得了。對(duì)這個(gè)問(wèn)題我用A*算法來(lái)求解，正所謂光說(shuō)不練是沒(méi)有用的

http://acm.pku.edu.cn/JudgeOnline/problem?id=2243
problem statement

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input Specification

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output Specification

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input

e2 e4

a1 b2

b2 c3

a1 h8

a1 h7

h8 a1

b1 c3

f6 f6

Sample Output

To get from e2 to e4 takes 2 knight moves.

To get from a1 to b2 takes 4 knight moves.

To get from b2 to c3 takes 2 knight moves.

To get from a1 to h8 takes 6 knight moves.

To get from a1 to h7 takes 5 knight moves.

To get from h8 to a1 takes 6 knight moves.

To get from b1 to c3 takes 1 knight moves.

To get from f6 to f6 takes 0 knight moves.
題目的意思大概是說(shuō)：在國(guó)際象棋的棋盤上，一匹馬共有8個(gè)可能的跳躍方向，求從起點(diǎn)到目標(biāo)點(diǎn)之間的最少跳躍次數(shù)。
A* code:

posted on 2009-04-19 23:53 極限定律 閱讀(128258) 評(píng)論(44)  編輯 收藏 引用 所屬分類: ACM/ICPC