深入淺出A-Star算法

1、A*尋路初探整理來自：/document/viewdoc/2idT422這篇文章并不試圖對這個話題作權(quán)威的陳述。取而代之的是，它只是描述算法的原理，使你可以在進一步的閱讀 中理解其他相關(guān)的資料。最后，這篇文章沒有程序細(xì)節(jié)。你盡可以用任意的計算機程序語言實現(xiàn)它。如你所愿，我在文章的末尾包含了一 個指向例子程序的鏈接。壓縮包包括C+和Blitz Basic兩個語言的版本，如果你只是想看看它的運行效果，里面還 包含了可執(zhí)行文件。我們正在提高自己。讓我們從頭開始.序：搜索區(qū)域假設(shè)有人想從A點移動到一墻之隔的B點，如下圖，綠色的是起點A，紅色是終點B，藍(lán)色方塊是中間的墻。你首先注意到，搜索區(qū)域被我們劃分

2、成了方形網(wǎng)格。像這樣，簡化搜索區(qū)域，是尋路的第一步。這一方法把搜索區(qū) 域簡化成了一個二維數(shù)組。數(shù)組的每一個元素是網(wǎng)格的一個方塊，方塊被標(biāo)記為可通過的和不可通過的。路徑被描述 為從A到B我們經(jīng)過的方塊的集合。一旦路徑被找到，我們的人就從一個方格的中心走向另一個，直到到達(dá)目的地。這些中點被稱為“節(jié)點”。當(dāng)你閱讀其他的尋路資料時，你將經(jīng)常會看到人們討論節(jié)點。為什么不把他們描述為 方格呢？因為有可能你的路徑被分割成其他不是方格的結(jié)構(gòu)。他們完全可以是矩形，六角形，或者其他任意形狀。節(jié) 點能夠被放置在形狀的任意位置一可以在中心，或者沿著邊界，或其他什么地方。我們使用這種系統(tǒng)，無論如何，因 為它是最簡單的。

3、開始搜索正如我們處理上圖網(wǎng)格的方法，一旦搜索區(qū)域被轉(zhuǎn)化為容易處理的節(jié)點，下一步就是去引導(dǎo)一次找到最短路徑的搜 索。在A*尋路算法中，我們通過從點A開始，檢查相鄰方格的方式，向外擴展直到找到目標(biāo)。1、從點A開始，并且把它作為待處理點存入一個“開啟列表”。開啟列表就像一張購物清單。盡管現(xiàn)在列表里只 有一個元素，但以后就會多起來。你的路徑可能會通過它包含的方格，也可能不會?；旧希@是一個待檢查方格的 列表。2、尋找起點周圍所有可到達(dá)或者可通過的方格，跳過有墻，水，或其他無法通過地形的方格。也把他們加入開啟 列表。為所有這些方格保存點A作為“父方格”。當(dāng)我們想描述路徑的時候，父方格的資料是十分重要的

4、。后面會解 釋它的具體用途。3、從開啟列表中刪除點A，把它加入到一個“關(guān)閉列表”，列表中保存所有不需要再次檢查的方格。在這一點，你應(yīng)該形成如圖的結(jié)構(gòu)。在圖中，暗綠色方格是你起始方格的中心。它被用淺藍(lán)色描邊，以表示它被加 入到關(guān)閉列表中了。所有的相鄰格現(xiàn)在都在開啟列表中，它們被用淺綠色描邊。每個方格都有一個灰色指針反指他們 的父方格，也就是開始的方格。接著，我們選擇開啟列表中的臨近方格，大致重復(fù)前面的過程，如下。但是，哪個方格是我們要選擇的呢？是那4f 值最低的。路徑評分選擇路徑中經(jīng)過哪個方格的關(guān)鍵是下面這個等式：F = G + HG =從起點A，沿著產(chǎn)生的路徑，移動到網(wǎng)格上指定方格的移動耗費。

5、H =從網(wǎng)格上那個方格移動到終點B的預(yù)估移動耗費。這經(jīng)常被稱為啟發(fā)式的，可能會讓你有點迷惑。這樣叫的原 因是因為它只是個猜測。我們沒辦法事先知道路徑的長度，因為路上可能存在各種障疏墻，水，等等）。雖然本文只 提供了一種計算H的方法，但是你可以在網(wǎng)上找到很多其他的方法。我們的路徑是通過反復(fù)遍歷開啟列表并且選擇具有最低F值的方格來生成的。文章將對這個過程做更詳細(xì)的描 述。首先，我們更深入的看看如何計算這個方程。正如上面所說，G表示沿路徑從起點到當(dāng)前點的移動耗費。在這個例子里，我們令水平或者垂直移動的耗費為10， 對角線方向耗費為14。我們?nèi)∵@些值是因為沿對角線的距離是沿水平或垂直移動耗費的的根號2

6、（別怕），或者約1.414 倍。為了簡化，我們用10和14近似。比例基本正確，同時我們避免了求根運算和小數(shù)。這不是只因為我們怕麻煩或 者不喜歡數(shù)學(xué)。使用這樣的整數(shù)對計算機來說也更快捷。你不就就會發(fā)現(xiàn)，如果你不使用這些簡化方法，尋路會變得 很慢。既然我們在計算沿特定路徑通往某個方格的G值，求值的方法就是取它父節(jié)點的G值，然后依照它相對父節(jié)點是 對角線方向或者直角方向（非對角線），分別增加14和10。例子中這個方法的需求會變得更多，因為我們從起點方格 以外獲取了不止一個方格。H值可以用不同的方法估算。我們這里使用的方法被稱為曼哈頓方法，它計算從當(dāng)前格到目的格之間水平和垂直 的方格的數(shù)量總和，忽略對

7、角線方向。然后把結(jié)果乘以10。這被成為曼哈頓方法是因為它看起來像計算城市中從一 個地方到另外一個地方的街區(qū)數(shù)，在那里你不能沿對角線方向穿過街區(qū)。很重要的一點，我們忽略了一切障礙物。這 是對剩余距離的一個估算，而非實際值，這也是這一方法被稱為啟發(fā)式的原因。想知道更多？你可以在這里找到方程 和額外的注解。F的值是G和H的和。第一步搜索的結(jié)果可以在下面的圖表中看到F,G和H的評分被寫在每個方格里。正如在 緊挨起始格右側(cè)的方格所表示的，F(xiàn)被打印在左上角，G在左下角，H則在右下角?，F(xiàn)在我們來看看這些方格。寫字母的方格里，G = 10。這是因為它只在水平方向偏離起始格一個格距。緊鄰起始 格的上方，下方和左

8、邊的方格的G值都等于10。對角線方向的G值是14。H值通過求解到紅色目標(biāo)格的曼哈頓距離得到，其中只在水平和垂直方向移動，并且忽略中間的墻。用這種方法， 起點右側(cè)緊鄰的方格離紅色方格有3格距離，H值就是30。這塊方格上方的方格有4格距離（記住，只能在水平和垂 直方向移動，這個僅僅是曼哈頓距離計算規(guī)則，不是游戲移動規(guī)則），H值是40。你大致應(yīng)該知道如何計算其他方格的 H值了。每個格子的F值，還是簡單的由G和H相加得到繼續(xù)搜索為了繼續(xù)搜索，我們簡單的從開啟列表中選擇F值最低的方格。然后，對選中的方格做如下處理：把它從開啟列表中刪除，然后添加到關(guān)閉列表中。檢查所有相鄰格子。跳過那些已經(jīng)在關(guān)閉列表中的或

9、者不可通過的（有墻，水的地形，或者其他無法通過的 地形），把他們添加進開啟列表（如果他們還不在里面的話）。把選中的方格作為新的方格的父節(jié)點。如果某個相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。換句話說，檢查如果我們用新的路徑 到達(dá)它的話，G值是否會更低一些。如果不是，那就什么都不做。另一方面，如果新的G值更低，那就把相鄰方格的父節(jié)點改為目前選中的方格（在上面的圖表中，把箭頭的方 向改為指向這個方格）。最后，重新計算F和G的值。如果這看起來不夠清晰，你可以看下面的圖示。好了，讓我們看看它是怎么運作的。我們最初的9格方格中，在起點被切換到關(guān)閉列表中后，還剩8格留在開啟 列表中。這里面，F(xiàn)

10、值最低的那個是起始格右側(cè)緊鄰的格子，它的F值是40。因此我們選擇這一格作為下一個要處 理的方格。在緊隨的圖中，它被用藍(lán)色突出顯示。首先，我們把它從開啟列表中取出，放入關(guān)閉列表（這就是他被藍(lán)色突出顯示的原因）。然后我們檢查相鄰的格子。 哦，右側(cè)的格子是墻，所以我們略過。左側(cè)的格子是起始格。它在關(guān)閉列表里，所以我們也跳過它。其他4格已經(jīng)在開啟列表里了，于是我們檢查G值來判定，如果通過這一格到達(dá)那里，路徑是否更好。我們先 來看選中格子下面的方格。它的G值是14。如果我們從當(dāng)前格移動到那里，G值就會等于20（到達(dá)當(dāng)前格的G值是 10，移動到下面的格子將使得G值增加10）。因為G值20大于14,所以這不

11、是更好的路徑。如果你看圖，就能理解。 與其通過先水平移動一格，再垂直移動一格，還不如直接沿對角線方向移動一格來得簡單。當(dāng)我們對已經(jīng)存在于開啟列表中的4個臨近格重復(fù)這一過程的時候，我們發(fā)現(xiàn)沒有一條路徑可以通過使用當(dāng)前格 子（即起點右側(cè)格子）得到改善，所以我們不做任何改變。既然我們已經(jīng)檢查過了所有鄰近格，那么就可以移動到下一 格了。于是我們檢索開啟列表，現(xiàn)在里面只有7格了，我們?nèi)匀贿x擇其中F值最低的。有趣的是，這次，有兩個格子的 數(shù)值都是54。我們?nèi)绾芜x擇？這并不麻煩。從速度上考慮，選擇最后添加進列表的格子會更快捷。這種導(dǎo)致了尋路 過程中，在靠近目標(biāo)的時候，優(yōu)先使用新找到的格子的偏好。但這無關(guān)緊要

12、。（對相同數(shù)值的不同對待，導(dǎo)致不同版 本的A*算法找到等長的不同路徑。）那我們就選擇起始格右下方的格子，如圖。這次，當(dāng)我們檢查相鄰格的時候，發(fā)現(xiàn)右側(cè)是墻，于是略過。上面一格也被略過。我們也略過了墻下面的格子。 為什么呢？因為你不能在不穿越墻角的情況下直接到達(dá)那個格子。你的確需要先往下走然后到達(dá)那一格，按部就班的 走過那個拐角。（注解：穿越拐角的規(guī)則是可選的。它取決于你的節(jié)點是如何放置的。）這樣一來，就剩下了其他5格。其中當(dāng)前格下面的2個格子目前不在開啟列表中，于是我們添加他們，并且把當(dāng) 前格指定為他們的父節(jié)點。另外3格，兩個已經(jīng)在關(guān)閉列表中（起始格，和當(dāng)前格上方的格子，在表格中藍(lán)色高亮顯 示）

13、,于是我們略過它們；最后一格，在當(dāng)前格的左側(cè)，將被檢查通過這條路徑，G值是否更低。不必?fù)?dān)心，我們已經(jīng) 準(zhǔn)備好檢查開啟列表中的下一格了。我們重復(fù)這個過程，知道目標(biāo)格被添加進開啟列表，就如在下面的圖中所看到的。1 DBZBBD9HZH?DBD.TZDED7HZHED9HZH70A 01 1 HEDEDT 1 ED5H1 HHDBDOznEQEDCli osnHDO1 D3DBZ% 7Z1 EBi1 bbnnBZz7Z1 9H2H?n7H/1 4EDEDA1 DED5H1 HHD7HEHZDEBz5B1 DBBEBZD1 OBZBBD9HZH?DBOAZDED7HAZH5DY：3HHD7H：HH3D

14、Y) 5HZD1 DZ7ZmuIDS/bh ?n9HA3HEDBEJ SBEDBBHaHDSB5Bsn注意，起始格下方格子的父節(jié)點已經(jīng)和前面不同的。之前它的G值是28,并且指向右上方的格子?，F(xiàn)在它的G 值是20，指向它上方的格子。這在尋路過程中的某處發(fā)生，當(dāng)應(yīng)用新路徑時，G值經(jīng)過檢查變得低了一于是父節(jié)點 被重新指定，G和F值被重新計算。盡管這一變化在這個例子中并不重要，在很多場合，這種變化會導(dǎo)致尋路結(jié)果的 巨大變化。那么，我們怎么確定這條路徑呢？很簡單，從紅色的目標(biāo)格開始，按箭頭的方向朝父節(jié)點移動。這最終會引導(dǎo)你 回到起始格，這就是你的路徑！看起來應(yīng)該像圖中那樣。從起始格人移動到目標(biāo)格B只是簡

15、單的從每個格子（節(jié)點）A*方法總結(jié)好，現(xiàn)在你已經(jīng)看完了整個說明，讓我們把每一步的操作寫在一起:1、把起始格添加到開啟列表。2、重復(fù)如下的工作：a）尋找開啟列表中F值最低的格子。我們稱它為當(dāng)前格。b）把它切換到關(guān)閉列表。c）對相鄰的8格中的每一個？如果它不可通過或者已經(jīng)在關(guān)閉列表中，略過它。反之如下。如果它不在開啟列表中，把它添加進去。把當(dāng)前格作為這一格的父節(jié)點。記錄這一格的F,G和H值。如果它已經(jīng)在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣， 就把這一格的父節(jié)點改成當(dāng)前格，并且重新計算這一格的G和F值。如果你保持你的開啟列表按F值排序，改 變之后你可能

16、需要重新對開啟列表排序。d）停止，當(dāng)你把目標(biāo)格添加進了開啟列表，這時候路徑被找到，或者沒有找到目標(biāo)格，開啟列表已經(jīng)空了。這 時候，路徑不存在。3、保存路徑。從目標(biāo)格開始，沿著每一格的父節(jié)點移動直到回到起始格。這就是你的路徑。題外話離題一下，見諒，值得一提的是，當(dāng)你在網(wǎng)上或者相關(guān)論壇看到關(guān)于A*的不同的探討，你有時會看到一些 被當(dāng)作A*算法的代碼而實際上他們不是。要使用A*，你必須包含上面討論的所有元素一一特定的開啟和關(guān)閉列 表，用F,G和H作路徑評價。有很多其他的尋路算法，但他們并不是A*，A*被認(rèn)為是他們當(dāng)中最好的Bryan Stout 在這篇文章后面的參考文檔中論述了一部分，包括他們的一些

17、優(yōu)點和缺點。有時候特定的場合其他算法會更好， 但你必須很明確你在作什么。好了，夠多的了?；氐轿恼隆崿F(xiàn)的注解現(xiàn)在你已經(jīng)明白了基本原理，寫你的程序的時候還得考慮一些額外的東西。下面這些材料中的一些引用了我 用C+和Blitz Basic寫的程序，但對其他語言寫的代碼同樣有效。1、維護開啟列表：這是A*尋路算法最重要的組成部分。每次你訪問開啟列表，你都需要尋堀值最低的方 格。有幾種不同的方法實現(xiàn)這一點。你可以把路徑元素隨意保存，當(dāng)需要尋找F值最低的元素的時候，遍歷開啟 列表。這很簡單，但是太慢了，尤其是對長路徑來說。這可以通過維護一格排好序的列表來改善，每次尋找F 值最低的方格只需要選取列表的首元

18、素。當(dāng)我自己實現(xiàn)的時候，這種方法是我的首選。在小地圖。這種方法工作的很好，但它并不是最快的解決方案。更苛求速度的A*程序員使用叫做“binary heap” 的方法，這也是我在代碼中使用的方法。憑我的經(jīng)驗，這種方法在大多數(shù)場合會快23倍，并且在長路經(jīng)上速 度呈幾何級數(shù)提升（10倍以上速度）。如果你想了解更多關(guān)于binary heap的內(nèi)容，查閱我的文章:Using Binary Heaps in A* Pathfinding o2、其他單位：如果你恰好看了我的例子代碼，你會發(fā)現(xiàn)它完全忽略了其他單位。我的尋路者事實上可以相 互穿越。取決于具體的游戲，這也許可以，也許不行。如果你打算考慮其他單位，

19、希望他們能互相繞過，我建議 在尋路算法中忽略其他單位，寫一些新的代碼作碰撞檢測。當(dāng)碰撞發(fā)生，你可以生成一條新路徑或者使用一些標(biāo) 準(zhǔn)的移動規(guī)則（比如總是向右，等等）直到路上沒有了障礙，然后再生成新路徑。為什么在最初的路徑計算中不考 慮其他單位呢？那是因為其他單位會移動，當(dāng)你到達(dá)他們原來的位置的時候，他們可能已經(jīng)離開了。這有可能會 導(dǎo)致奇怪的結(jié)果，一個單位突然轉(zhuǎn)向，躲避一個已經(jīng)不在那里的單位，并且會撞到計算完路徑后，沖進它的路徑 中的單位。然而，在尋路算法中忽略其他對象，意味著你必須編寫單獨的碰撞檢測代碼。這因游戲而異，所以我把這 個決定權(quán)留給你。參考文獻(xiàn)列表中，Bryan Stout的文章值得研

20、究，里面有一些可能的解決方案（像魯棒追蹤，等 等）。3、一些速度方面的提示：當(dāng)你開發(fā)你自己的A*程序，或者改寫我的，你會發(fā)現(xiàn)尋路占據(jù)了大量的CPU時 間，尤其是在大地圖上有大量對象在尋路的時候。如果你閱讀過網(wǎng)上的其他材料，你會明白，即使是開發(fā)了星際 爭霸或帝國時代的專家，這也無可奈何。如果你覺得尋路太過緩慢，這里有一些建議也許有效：（1）使用更小的地圖或者更少的尋路者。（2）不要同時給多個對象尋路。取而代之的是把他們加入一個隊列，把尋路過程分散在幾個游戲周期中。如 果你的游戲以40周期每秒的速度運行，沒人能察覺。但是他們會發(fā)覺游戲速度突然變慢，當(dāng)大量尋路者計算自 己路徑的時候。（3）盡量使用更

21、大的地圖網(wǎng)格。這降低了尋路中搜索的總網(wǎng)格數(shù)。如果你有志氣，你可以設(shè)計兩個或者更多 尋路系統(tǒng)以便使用在不同場合，取決于路徑的長度。這也正是專業(yè)人士的做法，用大的區(qū)域計算長的路徑，然后 在接近目標(biāo)的時候切換到使用小格子/區(qū)域的精細(xì)尋路。如果你對這個觀點感興趣，查閱我的文章:Two-Tiered A*Pathfinding o（4）使用路徑點系統(tǒng)計算長路徑，或者預(yù)先計算好路徑并加入到游戲中。（5 ）預(yù)處理你的地圖，表明地圖中哪些區(qū)域是不可到達(dá)的。我把這些區(qū)域稱作“孤島”。事實上，他們可以 是島嶼或其他被墻壁包圍等無法到達(dá)的任意區(qū)域。A*的下限是，當(dāng)你告訴它要尋找通往那些區(qū)域的路徑時，它 會搜索整個地

22、圖，直到所有可到達(dá)的方格/節(jié)點都被通過開啟列表和關(guān)閉列表的計算。這會浪費大量的CPU時間?？梢酝ㄟ^預(yù)先確定這些區(qū)域（比如通過flood-fill或類似的方法）來避免這種情況的發(fā)生，用某些種類的數(shù)組記錄這 些信息，在開始尋路前檢查它。在我Blitz版本的代碼中，我建立了一個地圖預(yù)處理器來作這個工作。它也標(biāo)明了尋路算法可以忽略的死端，這進一步提高了尋路速度。4、不同的地形損耗：在這個教程和我附帶的程序中，地形只有兩種一可通過的和不可通過的。但是你可能會需要一些可通過的地形，但是移動耗費更高一沼澤，小山，地牢的樓梯，等等。這些都是可通過但是比平坦的 開闊地移動耗費更高的地形。類似的，道路應(yīng)該比自然地

23、形移動耗費更低。這個問題很容易解決，只要在計算任何地形的G值的時候增加地形損耗就可以了。簡單的給它增加一些額 外的損耗就可以了。由于A*算法已經(jīng)按照尋找最低耗費的路徑來設(shè)計，所以很容易處理這種情況。在我提供的 這個簡單的例子里，地形只有可通過和不可通過兩種，A*會找到最短，最直接的路徑。但是在地形耗費不同的 場合，耗費最低的路徑也許會包含很長的移動距離一就像沿著路繞過沼澤而不是直接穿過它。一種需額外考慮的情況是被專家稱之為“influence mapping”的東西（暫譯為影響映射圖）。就像上面描述 的不同地形耗費一樣，你可以創(chuàng)建一格額外的分?jǐn)?shù)系統(tǒng)，并把它應(yīng)用到尋路的AI中。假設(shè)你有一張有大批

24、尋路 者的地圖，他們都要通過某個山區(qū)。每次電腦生成一條通過那個關(guān)口的路徑，它就會變得更擁擠。如果你愿意， 你可以創(chuàng)建一個影響映射圖對有大量屠殺事件的格子施以不利影響。這會讓計算機更傾向安全些的路徑，并且?guī)椭苊饪偸莾H僅因為路徑短（但可能更危險）而持續(xù)把隊伍和尋路者送到某一特定路徑。5、處理未知區(qū)域：你是否玩過這樣的PC游戲，電腦總是知道哪條路是正確的，即使它還沒有偵察過地圖？對于游戲，尋路太好會顯得不真實。幸運的是，這是一格可以輕易解決的問題。答案就是為每個不同的玩家和電腦（每個玩家，而不是每個單位一一那樣的話會耗費大量的內(nèi)存）創(chuàng)建一 個獨立的“knownWalkability”數(shù)組，每個數(shù)

25、組包含玩家已經(jīng)探索過的區(qū)域，以及被當(dāng)作可通過區(qū)域的其他區(qū)域， 直到被證實。用這種方法，單位會在路的死端徘徊并且導(dǎo)致錯誤的選擇直到他們在周圍找到路。一旦地圖被探索 了，尋路就像往常那樣進行。6、平滑路徑：盡管A*提供了最短，最低代價的路徑，它無法自動提供看起來平滑的路徑。看一下我們的例 子最終形成的路徑（在圖7）o最初的一步是起始格的右下方，如果這一步是直接往下的話，路徑不是會更平滑一些嗎?有幾種方法來解決這個問題。當(dāng)計算路徑的時候可以對改變方向的格子施加不利影響，對 G值增加額外的 數(shù)值。也可以換種方法，你可以在路徑計算完之后沿著它跑一遍，找那些用相鄰格替換會讓路徑看起來更平滑的 地方。想知道

26、完整的結(jié)果，查看 Marco Pinter發(fā)表在 G 的 一篇文章：Toward More Realistic Pathfinding （免費，但是需要注冊）。 HYPERLINK /features/20010314/pinter_01.htm /features/20010314/pinter 01.htm 阿7、非方形搜索區(qū)域：在我們的例子里，我們使用簡單的2D方形圖。你可以不使用這種方式。你可以使用 不規(guī)則形狀的區(qū)域。想想冒險棋的游戲，和游戲中那些國家。你可以設(shè)計一個像那樣的尋路關(guān)卡。為此，你可能 需要建立一個國家相鄰關(guān)系的表格，和從一個國家移動到另一個的G值。你也需要估算H值的方法。

27、其他的事 情就和例子中完全一樣了。當(dāng)你需要向開啟列表中添加新元素的時候，不需使用相鄰的格子，取而代之的是從表 格中尋找相鄰的國家。類似的，你可以為一張確定的地形圖創(chuàng)建路徑點系統(tǒng)，路徑點一般是路上，或者地牢通道的轉(zhuǎn)折點。作為 游戲設(shè)計者，你可以預(yù)設(shè)這些路徑點。兩個路徑點被認(rèn)為是相鄰的如果他們之間的直線上沒有障礙的話。在冒險 棋的例子里，你可以保存這些相鄰信息在某個表格里，當(dāng)需要在開啟列表中添加元素的時候使用它。然后你就可 以記錄關(guān)聯(lián)的G值（可能使用兩點間的直線距離），H值（可以使用到目標(biāo)點的直線距離），其他都按原先的做就可以了。另一個在非方形區(qū)域搜索RPG地圖的例子，查看我的文章：Two-Tie

28、red A* Pathfinding。 HYPERLINK /games/twoTiered.htm /games/twoTiered.htm進一步的閱讀好，現(xiàn)在你對一些進一步的觀點有了初步認(rèn)識。這時，我建議你研究我的源代碼。包里面包含兩個版本，- 個是用C+寫的，另一個用Blitz Basic0順便說一句，兩個版本都注釋詳盡，容易閱讀，這里是鏈接。例子代碼：A* Pathfinder (2D) Version 1.71 HYPERLINK /cgi-bin/showcase/showcase_showentry.pl?id=turtle177604062002002208&comments=

29、n /cgi-bin/showcase/showcase showentry.pl?id=turtle177604062002002208&comments=n o如果你既不用C+也不用Blitz Basic,在C+版本里有兩個小的可執(zhí)行文件。Blitz Basic可以在從Blitz Basic 網(wǎng)站免費下載的litz Basic 3D(不是Blitz Plus)演示版上運行。Ben ONeill提供一個聯(lián)機演示可以在這里找到。 HYPERLINK http:/www.0wns.me.uk/pathfinding/ http:/www.0wns.me.uk/pathfinding/你也該看看以下的網(wǎng)頁。讀了這篇教程后，他們應(yīng)該變得容易理解多了。Amit的A*頁面：這是由Amit Patel制作，被廣泛引用的頁面，如果你沒有事先讀這篇文章，可能會有點 難以理解。值得一看。尤其要看Amit關(guān)于這個問題的自己的看法。 HYPERLINK http:/www-cs-students.stanford.cdu/amitp/gameprog.html%23Paths http:/www-cs-students.stanford.cdu/amitp/gameprog.html#PathsSmart Moves:智能尋路：Bryan Stou