A*算法入門

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

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

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

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

選取最小估價(jià)：如果學(xué)過數(shù)據(jù)結(jié)構(gòu)的話，應(yīng)該可以知道，對于每次都要選取最小估價(jià)的節(jié)點(diǎn)，應(yīng)該用到最小優(yōu)先級隊(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)：它的空間增長是指數(shù)級別的。

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

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

作者：Patrick Lester

譯者：Panic2005年

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

這篇文章非常知名，國內(nèi)應(yīng)該有不少人翻譯過它，我沒有查找，覺得翻譯本身也是對自身英文水平的鍛煉。經(jīng)過努力，終于完成了文檔，也明白的A*算法的原理。毫無疑問，作者用形象的描述，簡潔詼諧的語言由淺入深的講述了這一神奇的算法，相信每個(gè)讀過的人都會對此有所認(rèn)識（如果沒有，那就是偶的翻譯太差了--b）。

現(xiàn)在是年月日的版本，應(yīng)原作者要求，對文中的某些算法細(xì)節(jié)做了修改。

原文鏈接：http://www.gamedev.net/reference/articles/article2003.asp

原作者文章鏈接：http://www.policyalmanac.org/games/aStarTutorial.htm

以下是翻譯的正文

會者不難，A*(念作A星)算法對初學(xué)者來說的確有些難度。這篇文章并不試圖對這個(gè)話題作權(quán)威的陳述。取而代之的是，它只是描述算法的原理，使你可以在進(jìn)一步的閱讀中理解其他相關(guān)的資料。最后，這篇文章沒有程序細(xì)節(jié)。你盡可以用任意的計(jì)算機(jī)程序語言實(shí)現(xiàn)它。如你所愿，我在文章的末尾包含了一個(gè)指向例子程序的鏈接。壓縮包包括C++和Blitz Basic兩個(gè)語言的版本，如果你只是想看看它的運(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)格。像這樣，簡化搜索區(qū)域，是尋路的第一步。這一方法把搜索區(qū)域簡化成了一個(gè)二維數(shù)組。數(shù)組的每一個(gè)元素是網(wǎng)格的一個(gè)方塊，方塊被標(biāo)記為可通過的和不可通過的。路徑被描述為從A到B我們經(jīng)過的方塊的集合。一旦路徑被找到，我們的人就從一個(gè)方格的中心走向另一個(gè)，直到到達(dá)目的地。

這些中點(diǎn)被稱為“節(jié)點(diǎn)”。當(dāng)你閱讀其他的尋路資料時(shí)，你將經(jīng)常會看到人們討論節(jié)點(diǎn)。為什么不把他們描述為方格呢？因?yàn)橛锌赡苣愕穆窂奖环指畛善渌皇欠礁竦慕Y(jié)構(gòu)。他們完全可以是矩形，六角形，或者其他任意形狀。節(jié)點(diǎn)能夠被放置在形狀的任意位置－可以在中心，或者沿著邊界，或其他什么地方。我們使用這種系統(tǒng)，無論如何，因?yàn)樗亲詈唵蔚摹?/span>

開始搜索

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

我們做如下操作開始搜索：

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

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

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

[圖-2]

接著，我們選擇開啟列表中的臨近方格，大致重復(fù)前面的過程，如下。但是，哪個(gè)方格是我們要選擇的呢？是那個(gè)F值最低的。

路徑評分

選擇路徑中經(jīng)過哪個(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ā)式的，可能會讓你有點(diǎn)迷惑。這樣叫的原因是因?yàn)樗皇莻€(gè)猜測。我們沒辦法事先知道路徑的長度，因?yàn)槁飞峡赡艽嬖诟鞣N障礙(墻，水，等等)。雖然本文只提供了一種計(jì)算H的方法，但是你可以在網(wǎng)上找到很多其他的方法。

我們的路徑是通過反復(fù)遍歷開啟列表并且選擇具有最低F值的方格來生成的。文章將對這個(gè)過程做更詳細(xì)的描述。首先，我們更深入的看看如何計(jì)算這個(gè)方程。

正如上面所說，G表示沿路徑從起點(diǎn)到當(dāng)前點(diǎn)的移動(dòng)耗費(fèi)。在這個(gè)例子里，我們令水平或者垂直移動(dòng)的耗費(fèi)為，對角線方向耗費(fèi)為。我們?nèi)∵@些值是因?yàn)檠貙蔷€的距離是沿水平或垂直移動(dòng)耗費(fèi)的的根號（別怕），或者約.414倍。為了簡化，我們用和近似。比例基本正確，同時(shí)我們避免了求根運(yùn)算和小數(shù)。這不是只因?yàn)槲覀兣侣闊┗蛘卟幌矚g數(shù)學(xué)。使用這樣的整數(shù)對計(jì)算機(jī)來說也更快捷。你不就就會發(fā)現(xiàn)，如果你不使用這些簡化方法，尋路會變得很慢。

既然我們在計(jì)算沿特定路徑通往某個(gè)方格的G值，求值的方法就是取它父節(jié)點(diǎn)的G值，然后依照它相對父節(jié)點(diǎn)是對角線方向或者直角方向(非對角線)，分別增加和。例子中這個(gè)方法的需求會變得更多，因?yàn)槲覀儚钠瘘c(diǎn)方格以外獲取了不止一個(gè)方格。

H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計(jì)算從當(dāng)前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對角線方向，然后把結(jié)果乘以10。這被稱為曼哈頓方法是因?yàn)樗雌饋硐裼?jì)算城市中從一個(gè)地方到另外一個(gè)地方的街區(qū)數(shù)，在那里你不能沿對角線方向穿過街區(qū)。很重要的一點(diǎn)，我們忽略了一切障礙物。這是對剩余距離的一個(gè)估算，而非實(shí)際值，這也是這一方法被稱為啟發(fā)式的原因。想知道更多？你可以在這里找到方程和額外的注解。

F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到。F,G和H的評分被寫在每個(gè)方格里。正如在緊挨起始格右側(cè)的方格所表示的，F被打印在左上角，G在左下角，H則在右下角。

[圖-3]

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

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

繼續(xù)搜索

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

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

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

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

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

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

[圖-4]

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

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

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

于是我們檢索開啟列表，現(xiàn)在里面只有7格了，我們?nèi)匀贿x擇其中F值最低的。有趣的是，這次，有兩個(gè)格子的數(shù)值都是。我們?nèi)绾芜x擇？這并不麻煩。從速度上考慮，選擇最后添加進(jìn)列表的格子會更快捷。這種導(dǎo)致了尋路過程中，在靠近目標(biāo)的時(shí)候，優(yōu)先使用新找到的格子的偏好。但這無關(guān)緊要。（對相同數(shù)值的不同對待，導(dǎo)致不同版本的A*算法找到等長的不同路徑）那我們就選擇起始格右下方的格子，如圖：

[圖-5]

這次，當(dāng)我們檢查相鄰格的時(shí)候，發(fā)現(xiàn)右側(cè)是墻，于是略過。上面一格也被略過。我們也略過了墻下面的格子。為什么呢？因?yàn)槟悴荒茉诓淮┰綁堑那闆r下直接到達(dá)那個(gè)格子。你的確需要先往下走然后到達(dá)那一格，按部就班的走過那個(gè)拐角。(注解：穿越拐角的規(guī)則是可選的。它取決于你的節(jié)點(diǎn)是如何放置的。)

這樣一來，就剩下了其他格。當(dāng)前格下面的另外兩個(gè)格子目前不在開啟列表中，于是我們添加他們，并且把當(dāng)前格指定為他們的父節(jié)點(diǎn)。其余格，兩個(gè)已經(jīng)在關(guān)閉列表中（起始格，和當(dāng)前格上方的格子，在表格中藍(lán)色高亮顯示),于是我們略過它們。最后一格，在當(dāng)前格的左側(cè)，將被檢查通過這條路徑，G值是否更低。不必?fù)?dān)心，我們已經(jīng)準(zhǔn)備好檢查開啟列表中的下一格了。

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

[圖-6]

注意，起始格下方格子的父節(jié)點(diǎn)已經(jīng)和前面不同的。之前它的G值是，并且指向右上方的格子。現(xiàn)在它的G值是，指向它上方的格子。這在尋路過程中的某處發(fā)生，當(dāng)應(yīng)用新路徑時(shí)，G值經(jīng)過檢查變得低了－于是父節(jié)點(diǎn)被重新指定，G和F值被重新計(jì)算。盡管這一變化在這個(gè)例子中并不重要，在很多場合，這種變化會導(dǎo)致尋路結(jié)果的巨大變化。

那么，我們怎么確定這條路徑呢？很簡單，從紅色的目標(biāo)格開始，按箭頭的方向朝父節(jié)點(diǎn)移動(dòng)。這最終會引導(dǎo)你回到起始格，這就是你的路徑！看起來應(yīng)該像圖中那樣。從起始格A移動(dòng)到目標(biāo)格B只是簡單的從每個(gè)格子（節(jié)點(diǎn)）的中點(diǎn)沿路徑移動(dòng)到下一個(gè)，直到你到達(dá)目標(biāo)點(diǎn)。就這么簡單。

[圖-7]

A*方法總結(jié)

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

   1，把起始格添加到開啟列表。

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

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

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

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

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

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

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

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

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

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

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

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

題外話

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

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

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

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

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

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

這些提示大概可以讓你開始了。如果你想了解更多，這里有些你可能會覺得有用的鏈接：

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

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

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

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

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

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

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

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

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

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

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

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

類似的，你可以為一張確定的地形圖創(chuàng)建路徑點(diǎn)系統(tǒng)，路徑點(diǎn)一般是路上，或者地牢通道的轉(zhuǎn)折點(diǎn)。作為游戲設(shè)計(jì)者，你可以預(yù)設(shè)這些路徑點(diǎn)。兩個(gè)路徑點(diǎn)被認(rèn)為是相鄰的如果他們之間的直線上沒有障礙的話。在冒險(xiǎn)棋的例子里，你可以保存這些相鄰信息在某個(gè)表格里，當(dāng)需要在開啟列表中添加元素的時(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)你開發(fā)你自己的A*程序，或者改寫我的，你會發(fā)現(xiàn)尋路占據(jù)了大量的CPU時(shí)間，尤其是在大地圖上有大量對象在尋路的時(shí)候。如果你閱讀過網(wǎng)上的其他材料，你會明白，即使是開發(fā)了星際爭霸或帝國時(shí)代的專家，這也無可奈何。如果你覺得尋路太過緩慢，這里有一些建議也許有效：

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

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

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

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

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

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

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

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

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

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

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

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

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

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.
題目的意思大概是說：在國際象棋的棋盤上，一匹馬共有8個(gè)可能的跳躍方向，求從起點(diǎn)到目標(biāo)點(diǎn)之間的最少跳躍次數(shù)。
A* code:

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