去年做了個(gè)小東西，一個(gè)在線(xiàn)WebGame，目前只實(shí)現了多人聊天，移動(dòng)，拖動(dòng)畫(huà)面移動(dòng)，場(chǎng)景系統等，可以當場(chǎng)景聊天室使用。不過(guò)扔了一年了。
如圖

美工由靜電設計
后臺將由老于開(kāi)發(fā)


今年想再撿起來(lái)好好做做，由于是基于坐標點(diǎn)的，所以移動(dòng)路徑非常費資源。找到了一個(gè)A*的路徑算法，挺智能。

轉載一些介紹【轉自 http://data.gameres.com/message.asp?TopicID=25439】
譯者序：很久以前就知道了A*算法，但是從未認真讀過(guò)相關(guān)的文章，也沒(méi)有看過(guò)代碼，只是腦子里有個(gè)模糊的概念。這次決定從頭開(kāi)始，研究一下這個(gè)被人推崇備至的簡(jiǎn)單方法，作為學(xué)習人工智能的開(kāi)始。
這篇文章非常知名，國內應該有不少人翻譯過(guò)它，我沒(méi)有查找，覺(jué)得翻譯本身也是對自身英文水平的鍛煉。經(jīng)過(guò)努力，終于完成了文檔，也明白的A*算法的原理。毫無(wú)疑問(wèn)，作者用形象的描述，簡(jiǎn)潔詼諧的語(yǔ)言由淺入深的講述了這一神奇的算法，相信每個(gè)讀過(guò)的人都會(huì )對此有所認識（如果沒(méi)有，那就是偶的翻譯太差了--b）。
原文鏈接：http://www.gamedev.net/reference/articles/article2003.asp
以下是翻譯的正文。(由于本人使用ultraedit編輯，所以沒(méi)有對原文中的各種鏈接加以處理(除了圖表)，也是為了避免未經(jīng)許可鏈接的嫌疑，有興趣的讀者可以參考原文。

會(huì )者不難，A*(念作A星)算法對初學(xué)者來(lái)說(shuō)的確有些難度。

這篇文章并不試圖對這個(gè)話(huà)題作權威的陳述。取而代之的是，它只是描述算法的原理，使你可以在進(jìn)一步的閱讀中理解其他相關(guān)的資料。

最后，這篇文章沒(méi)有程序細節。你盡可以用任意的計算機程序語(yǔ)言實(shí)現它。如你所愿，我在文章的末尾包含了一個(gè)指向例子程序的鏈接。 壓縮包包括C++和Blitz Basic兩個(gè)語(yǔ)言的版本，如果你只是想看看它的運行效果，里面還包含了可執行文件。

我們正在提高自己。讓我們從頭開(kāi)始。。。

序：搜索區域

假設有人想從A點(diǎn)移動(dòng)到一墻之隔的B點(diǎn)，如下圖，綠色的是起點(diǎn)A，紅色是終點(diǎn)B，藍色方塊是中間的墻。




你首先注意到，搜索區域被我們劃分成了方形網(wǎng)格。像這樣，簡(jiǎn)化搜索區域，是尋路的第一步。這一方法把搜索區域簡(jiǎn)化成了一個(gè)二維數組。數組的每一個(gè)元素是網(wǎng)格的一個(gè)方塊，方塊被標記為可通過(guò)的和不可通過(guò)的。路徑被描述為從A到B我們經(jīng)過(guò)的方塊的集合。一旦路徑被找到，我們的人就從一個(gè)方格的中心走向另一個(gè)，直到到達目的地。

這些中點(diǎn)被稱(chēng)為“節點(diǎn)”。當你閱讀其他的尋路資料時(shí)，你將經(jīng)常會(huì )看到人們討論節點(diǎn)。為什么不把他們描述為方格呢？因為有可能你的路徑被分割成其他不是方格的結構。他們完全可以是矩形，六角形，或者其他任意形狀。節點(diǎn)能夠被放置在形狀的任意位置－可以在中心，或者沿著(zhù)邊界，或其他什么地方。我們使用這種系統，無(wú)論如何，因為它是最簡(jiǎn)單的。

開(kāi)始搜索

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

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


   1，從點(diǎn)A開(kāi)始，并且把它作為待處理點(diǎn)存入一個(gè)“開(kāi)啟列表”。開(kāi)啟列表就像一張購物清單。盡管現在列表里只有一個(gè)元素，但以后就會(huì )多起來(lái)。你的路徑可能會(huì )通過(guò)它包含的方格，也可能不會(huì )?；旧?，這是一個(gè)待檢查方格的列表。
   2，尋找起點(diǎn)周?chē)锌傻竭_或者可通過(guò)的方格，跳過(guò)有墻，水，或其他無(wú)法通過(guò)地形的方格。也把他們加入開(kāi)啟列表。為所有這些方格保存點(diǎn)A作為“父方格”。當我們想描述路徑的時(shí)候，父方格的資料是十分重要的。后面會(huì )解釋它的具體用途。
   3，從開(kāi)啟列表中刪除點(diǎn)A，把它加入到一個(gè)“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。

在這一點(diǎn)，你應該形成如圖的結構。在圖中，暗綠色方格是你起始方格的中心。它被用淺藍色描邊，以表示它被加入到關(guān)閉列表中了。所有的相鄰格現在都在開(kāi)啟列表中，它們被用淺綠色描邊。每個(gè)方格都有一個(gè)灰色指針?lè )粗杆麄兊母阜礁?，也就是開(kāi)始的方格。




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

路徑評分

選擇路徑中經(jīng)過(guò)哪個(gè)方格的關(guān)鍵是下面這個(gè)等式：

F = G + H

這里：
    * G = 從起點(diǎn)A，沿著(zhù)產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費。
    * H = 從網(wǎng)格上那個(gè)方格移動(dòng)到終點(diǎn)B的預估移動(dòng)耗費。這經(jīng)常被稱(chēng)為啟發(fā)式的，可能會(huì )讓你有點(diǎn)迷惑。這樣叫的原因是因為它只是個(gè)猜測。我們沒(méi)辦法事先知道路徑的長(cháng)度，因為路上可能存在各種障礙(墻，水，等等)。雖然本文只提供了一種計算H的方法，但是你可以在網(wǎng)上找到很多其他的方法。

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

正如上面所說(shuō)，G表示沿路徑從起點(diǎn)到當前點(diǎn)的移動(dòng)耗費。在這個(gè)例子里，我們令水平或者垂直移動(dòng)的耗費為10，對角線(xiàn)方向耗費為14。我們取這些值是因為沿對角線(xiàn)的距離是沿水平或垂直移動(dòng)耗費的的根號2（別怕），或者約1.414倍。為了簡(jiǎn)化，我們用10和14近似。比例基本正確，同時(shí)我們避免了求根運算和小數。這不是只因為我們怕麻煩或者不喜歡數學(xué)。使用這樣的整數對計算機來(lái)說(shuō)也更快捷。你不就就會(huì )發(fā)現，如果你不使用這些簡(jiǎn)化方法，尋路會(huì )變得很慢。

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

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

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



現在我們來(lái)看看這些方格。寫(xiě)字母的方格里，G = 10。這是因為它只在水平方向偏離起始格一個(gè)格距。緊鄰起始格的上方，下方和左邊的方格的G值都等于10。對角線(xiàn)方向的G值是14。

H值通過(guò)求解到紅色目標格的曼哈頓距離得到，其中只在水平和垂直方向移動(dòng)，并且忽略中間的墻。用這種方法，起點(diǎn)右側緊鄰的方格離紅色方格有3格距離，H值就是30。這塊方格上方的方格有4格距離(記住，只能在水平和垂直方向移動(dòng))，H值是40。你大致應該知道如何計算其他方格的H值了～。

每個(gè)格子的F值，還是簡(jiǎn)單的由G和H相加得到

繼續搜索

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

   4，把它從開(kāi)啟列表中刪除，然后添加到關(guān)閉列表中。
   5，檢查所有相鄰格子。跳過(guò)那些已經(jīng)在關(guān)閉列表中的或者不可通過(guò)的(有墻，水的地形，或者其他無(wú)法通過(guò)的地形)，把他們添加進(jìn)開(kāi)啟列表，如果他們還不在里面的話(huà)。把選中的方格作為新的方格的父節點(diǎn)。
   6，如果某個(gè)相鄰格已經(jīng)在開(kāi)啟列表里了，檢查現在的這條路徑是否更好。換句話(huà)說(shuō)，檢查如果我們用新的路徑到達它的話(huà)，G值是否會(huì )更低一些。如果不是，那就什么都不做。
      另一方面，如果新的G值更低，那就把相鄰方格的父節點(diǎn)改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個(gè)方格）。最后，重新計算F和G的值。如果這看起來(lái)不夠清晰，你可以看下面的圖示。

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




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

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

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

于是我們檢索開(kāi)啟列表，現在里面只有7格了，我們仍然選擇其中F值最低的。有趣的是，這次，有兩個(gè)格子的數值都是54。我們如何選擇？這并不麻煩。從速度上考慮，選擇最后添加進(jìn)列表的格子會(huì )更快捷。這種導致了尋路過(guò)程中，在靠近目標的時(shí)候，優(yōu)先使用新找到的格子的偏好。但這無(wú)關(guān)緊要。（對相同數值的不同對待，導致不同版本的A*算法找到等長(cháng)的不同路徑。）

那我們就選擇起始格右下方的格子，如圖。




這次，當我們檢查相鄰格的時(shí)候，發(fā)現右側是墻，于是略過(guò)。上面一格也被略過(guò)。我們也略過(guò)了墻下面的格子。為什么呢？因為你不能在不穿越墻角的情況下直接到達那個(gè)格子。你的確需要先往下走然后到達那一格，按部就班的走過(guò)那個(gè)拐角。(注解：穿越拐角的規則是可選的。它取決于你的節點(diǎn)是如何放置的。)

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

我們重復這個(gè)過(guò)程，知道目標格被添加進(jìn)開(kāi)啟列表，就如在下面的圖中所看到的。




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

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





A*方法總結

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

   1，把起始格添加到開(kāi)啟列表。
   2，重復如下的工作：
      a) 尋找開(kāi)啟列表中F值最低的格子。我們稱(chēng)它為當前格。
      b) 把它切換到關(guān)閉列表。
      c) 對相鄰的8格中的每一個(gè)？
          * 如果它不可通過(guò)或者已經(jīng)在關(guān)閉列表中，略過(guò)它。反之如下。
          * 如果它不在開(kāi)啟列表中，把它添加進(jìn)去。把當前格作為這一格的父節點(diǎn)。記錄這一格的F,G,和H值。
          * 如果它已經(jīng)在開(kāi)啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著(zhù)更好的路徑。如果是這樣，就把這一格的父節點(diǎn)改成當前格，并且重新計算這一格的G和F值。如果你保持你的開(kāi)啟列表按F值排序，改變之后你可能需要重新對開(kāi)啟列表排序。

      d) 停止，當你
          * 把目標格添加進(jìn)了開(kāi)啟列表，這時(shí)候路徑被找到，或者
          * 沒(méi)有找到目標格，開(kāi)啟列表已經(jīng)空了。這時(shí)候，路徑不存在。
   3.保存路徑。從目標格開(kāi)始，沿著(zhù)每一格的父節點(diǎn)移動(dòng)直到回到起始格。這就是你的路徑。

題外話(huà)

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

實(shí)現的注解

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

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

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

2，其他單位：如果你恰好看了我的例子代碼，你會(huì )發(fā)現它完全忽略了其他單位。我的尋路者事實(shí)上可以相互穿越。取決于具體的游戲，這也許可以，也許不行。如果你打算考慮其他單位，希望他們能互相繞過(guò)，我建議在尋路算法中忽略其他單位，寫(xiě)一些新的代碼作碰撞檢測。當碰撞發(fā)生，你可以生成一條新路徑或者使用一些標準的移動(dòng)規則(比如總是向右，等等)直到路上沒(méi)有了障礙，然后再生成新路徑。為什么在最初的路徑計算中不考慮其他單位呢？那是因為其他單位會(huì )移動(dòng)，當你到達他們原來(lái)的位置的時(shí)候，他們可能已經(jīng)離開(kāi)了。這有可能會(huì )導致奇怪的結果，一個(gè)單位突然轉向，躲避一個(gè)已經(jīng)不在那里的單位，并且會(huì )撞到計算完路徑后，沖進(jìn)它的路徑中的單位。

然而，在尋路算法中忽略其他對象，意味著(zhù)你必須編寫(xiě)單獨的碰撞檢測代碼。這因游戲而異，所以我把這個(gè)決定權留給你。參考文獻列表中，Bryan Stout的文章值得研究，里面有一些可能的解決方案(像魯棒追蹤，等等)。

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

    * 使用更小的地圖或者更少的尋路者。
    * 不要同時(shí)給多個(gè)對象尋路。取而代之的是把他們加入一個(gè)隊列，把尋路過(guò)程分散在幾個(gè)游戲周期中。如果你的游戲以40周期每秒的速度運行，沒(méi)人能察覺(jué)。但是他們會(huì )發(fā)覺(jué)游戲速度突然變慢，當大量尋路者計算自己路徑的時(shí)候。
    * 盡量使用更大的地圖網(wǎng)格。這降低了尋路中搜索的總網(wǎng)格數。如果你有志氣，你可以設計兩個(gè)或者更多尋路系統以便使用在不同場(chǎng)合，取決于路徑的長(cháng)度。這也正是專(zhuān)業(yè)人士的做法，用大的區域計算長(cháng)的路徑，然后在接近目標的時(shí)候切換到使用小格子/區域的精細尋路。如果你對這個(gè)觀(guān)點(diǎn)感興趣，查閱我的文章Two-Tiered A* Pathfinding。
    * 使用路徑點(diǎn)系統計算長(cháng)路徑，或者預先計算好路徑并加入到游戲中。
    * 預處理你的地圖，表明地圖中哪些區域是不可到達的。我把這些區域稱(chēng)作“孤島”。事實(shí)上，他們可以是島嶼或其他被墻壁包圍等無(wú)法到達的任意區域。A*的下限是，當你告訴它要尋找通往那些區域的路徑時(shí)，它會(huì )搜索整個(gè)地圖，直到所有可到達的方格/節點(diǎn)都被通過(guò)開(kāi)啟列表和關(guān)閉列表的計算。這會(huì )浪費大量的CPU時(shí)間?？梢酝ㄟ^(guò)預先確定這些區域（比如通過(guò)flood-fill或類(lèi)似的方法)來(lái)避免這種情況的發(fā)生,用某些種類(lèi)的數組記錄這些信息，在開(kāi)始尋路前檢查它。在我Blitz版本的代碼中，我建立了一個(gè)地圖預處理器來(lái)作這個(gè)工作。它也標明了尋路算法可以忽略的死端，這進(jìn)一步提高了尋路速度。

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

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

一種需額外考慮的情況是被專(zhuān)家稱(chēng)之為“influence mapping”的東西（暫譯為影響映射圖）。就像上面描述的不同地形耗費一樣，你可以創(chuàng )建一格額外的分數系統，并把它應用到尋路的AI中。假設你有一張有大批尋路者的地圖，他們都要通過(guò)某個(gè)山區。每次電腦生成一條通過(guò)那個(gè)關(guān)口的路徑，它就會(huì )變得更擁擠。如果你愿意，你可以創(chuàng )建一個(gè)影響映射圖對有大量屠殺事件的格子施以不利影響。這會(huì )讓計算機更傾向安全些的路徑，并且幫助它避免總是僅僅因為路徑短(但可能更危險)而持續把隊伍和尋路者送到某一特定路徑。

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

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

6，平滑路徑：盡管A*提供了最短，最低代價(jià)的路徑，它無(wú)法自動(dòng)提供看起來(lái)平滑的路徑?？匆幌挛覀兊睦幼罱K形成的路徑（在圖7）。最初的一步是起始格的右下方，如果這一步是直接往下的話(huà)，路徑不是會(huì )更平滑一些嗎？

有幾種方法來(lái)解決這個(gè)問(wèn)題。當計算路徑的時(shí)候可以對改變方向的格子施加不利影響，對G值增加額外的數值。也可以換種方法，你可以在路徑計算完之后沿著(zhù)它跑一遍，找那些用相鄰格替換會(huì )讓路徑看起來(lái)更平滑的地方。想知道完整的結果，查看Toward More Realistic Pathfinding，一篇(免費，但是需要注冊)Marco Pinter發(fā)表在Gamasutra.com的文章

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

類(lèi)似的，你可以為一張確定的地形圖創(chuàng )建路徑點(diǎn)系統，路徑點(diǎn)一般是路上，或者地牢通道的轉折點(diǎn)。作為游戲設計者，你可以預設這些路徑點(diǎn)。兩個(gè)路徑點(diǎn)被認為是相鄰的如果他們之間的直線(xiàn)上沒(méi)有障礙的話(huà)。在冒險棋的例子里，你可以保存這些相鄰信息在某個(gè)表格里，當需要在開(kāi)啟列表中添加元素的時(shí)候使用它。然后你就可以記錄關(guān)聯(lián)的G值（可能使用兩點(diǎn)間的直線(xiàn)距離），H值（可以使用到目標點(diǎn)的直線(xiàn)距離），其他都按原先的做就可以了。

另一個(gè)在非方形區域搜索RPG地圖的例子，查看我的文章Two-Tiered A* Pathfinding。

進(jìn)一步的閱讀

好，現在你對一些進(jìn)一步的觀(guān)點(diǎn)有了初步認識。這時(shí)，我建議你研究我的源代碼。包里面包含兩個(gè)版本，一個(gè)是用C++寫(xiě)的，另一個(gè)用Blitz Basic。順便說(shuō)一句，兩個(gè)版本都注釋詳盡，容易閱讀，這里是鏈接。

    * 例子代碼：A* Pathfinder (2D) Version 1.71

如果你既不用C++也不用Blitz Basic,在C++版本里有兩個(gè)小的可執行文件。Blitz Basic可以在從Blitz Basic網(wǎng)站免費下載的litz Basic 3D(不是Blitz Plus)演示版上運行。Ben O'Neill提供一個(gè)聯(lián)機演示可以在這里找到。

你也該看看以下的網(wǎng)頁(yè)。讀了這篇教程后，他們應該變得容易理解多了。

    * Amit的 A* 頁(yè)面:這是由Amit Patel制作，被廣泛引用的頁(yè)面，如果你沒(méi)有事先讀這篇文章，可能會(huì )有點(diǎn)難以理解。值得一看。尤其要看Amit關(guān)于這個(gè)問(wèn)題的自己的看法。
    * Smart Moves:智能尋路：Bryan Stout發(fā)表在Gamasutra.com的這篇文章需要注冊才能閱讀。注冊是免費的而且比起這篇文章和網(wǎng)站的其他資源，是非常物有所值的。Bryan用Delphi寫(xiě)的程序幫助我學(xué)習A*，也是我的A*代碼的靈感之源。它還描述了A*的幾種變化。
    * 地形分析：這是一格高階，但是有趣的話(huà)題，Dave Pottinge撰寫(xiě)，Ensemble Studios的專(zhuān)家。這家伙參與了帝國時(shí)代和君王時(shí)代的開(kāi)發(fā)。別指望看懂這里所有的東西，但是這是篇有趣的文章也許會(huì )讓你產(chǎn)生自己的想法。它包含一些對mip-mapping，influence mapping以及其他一些高級AI/尋路觀(guān)點(diǎn)。對"flood filling"的討論使我有了我自己的“死端”和“孤島”的代碼的靈感，這些包含在我Blitz版本的代碼中。

其他一些值得一看的網(wǎng)站：

    * aiGuru: Pathfinding
    * Game AI Resource: Pathfinding
    * GameDev.net: Pathfinding

好了，這就是全部。如果你剛好寫(xiě)一個(gè)運用這些觀(guān)點(diǎn)的程序，我想見(jiàn)識見(jiàn)識。你可以這樣聯(lián)系我：
現在，好運！





在51js上找到了hjjboy朋友的js實(shí)現方法，我給增加了注釋?zhuān)员闳蘸笳矸庋b。



在發(fā)一個(gè).net版本的實(shí)現 進(jìn)入