http://blog.vckbase.com/panic/archive/2005/03/20/3778.html
A*尋路初探
翻譯：Panic?
2005年3月18日
原文出處：A* Pathfinding for Beginners
譯者序
很久以前就知道了A*算法，但是從未認真讀過相關的文章吼驶，也沒有看過代碼捍掺，只是腦子里有個模糊的概念辨绊。這次決定從頭開始，研究一下這個被人推崇備至的簡單方法怔昨，作為學習人工智能的開始。
這篇文章非常知名，國內(nèi)應該有不少人翻譯過它东羹，我沒有查找，覺得翻譯本身也是對自身英文水平的鍛煉忠烛。經(jīng)過努力属提，終于完成了文檔，也明白的A*算法的原理。毫無疑問冤议，作者用形象的描述斟薇，簡潔詼諧的語言由淺入深的講述了這一神奇的算法，相信每個讀過的人都會對此有所認識（如果沒有恕酸，那就是偶的翻譯太差了--b）堪滨。
以下是翻譯的正文。(由于本人使用ultraedit編輯尸疆，所以沒有對原文中的各種鏈接加以處理(除了圖表)椿猎，也是為了避免未經(jīng)許可鏈接的嫌疑，有興趣的讀者可以參考原文寿弱。
會者不難犯眠，A*(念作A星)算法對初學者來說的確有些難度。
這篇文章并不試圖對這個話題作權威的陳述症革。取而代之的是筐咧，它只是描述算法的原理，使你可以在進一步的閱讀中理解其他相關的資料噪矛。
最后量蕊，這篇文章沒有程序細節(jié)。你盡可以用任意的計算機程序語言實現(xiàn)它艇挨。如你所愿残炮，我在文章的末尾包含了一個指向例子程序的鏈接。 壓縮包包括C++和Blitz Basic兩個語言的版本缩滨，如果你只是想看看它的運行效果势就，里面還包含了可執(zhí)行文件。
我們正在提高自己脉漏。讓我們從頭開始......
序：搜索區(qū)域
假設有人想從A點移動到一墻之隔的B點苞冯，如下圖，綠色的是起點A侧巨，紅色是終點B舅锄，藍色方塊是中間的墻。
[圖1]
你首先注意到司忱，搜索區(qū)域被我們劃分成了方形網(wǎng)格皇忿。像這樣，簡化搜索區(qū)域坦仍，是尋路的第一步禁添。這一方法把搜索區(qū)域簡化成了一個二維數(shù)組。數(shù)組的每一個元素是網(wǎng)格的一個方塊桨踪，方塊被標記為可通過的和不可通過的。路徑被描述為從A到B我們經(jīng)過的方塊的集合芹啥。一旦路徑被找到锻离，我們的人就從一個方格的中心走向另一個铺峭，直到到達目的地。
這些中點被稱為“節(jié)點”汽纠。當你閱讀其他的尋路資料時卫键，你將經(jīng)常會看到人們討論節(jié)點。為什么不把他們描述為方格呢虱朵？因為有可能你的路徑被分割成其他不是方格的結構莉炉。他們完全可以是矩形，六角形碴犬，或者其他任意形狀絮宁。節(jié)點能夠被放置在形狀的任意位置－可以在中心，或者沿著邊界服协，或其他什么地方绍昂。我們使用這種系統(tǒng)，無論如何偿荷，因為它是最簡單的窘游。
開始搜索
正如我們處理上圖網(wǎng)格的方法，一旦搜索區(qū)域被轉(zhuǎn)化為容易處理的節(jié)點跳纳，下一步就是去引導一次找到最短路徑的搜索忍饰。在A*尋路算法中，我們通過從點A開始寺庄，檢查相鄰方格的方式艾蓝，向外擴展直到找到目標。
我們做如下操作開始搜索：
從點A開始铣揉，并且把它作為待處理點存入一個“開啟列表”饶深。開啟列表就像一張購物清單。盡管現(xiàn)在列表里只有一個元素逛拱，但以后就會多起來敌厘。你的路徑可能會通過它包含的方格，也可能不會朽合【懔剑基本上，這是一個待檢查方格的列表曹步。
尋找起點周圍所有可到達或者可通過的方格宪彩，跳過有墻，水讲婚，或其他無法通過地形的方格尿孔。也把他們加入開啟列表。為所有這些方格保存點A作為“父方格”。當我們想描述路徑的時候活合，父方格的資料是十分重要的雏婶。后面會解釋它的具體用途。
從開啟列表中刪除點A白指，把它加入到一個“關閉列表”留晚，列表中保存所有不需要再次檢查的方格。
在這一點告嘲，你應該形成如圖的結構错维。在圖中，暗綠色方格是你起始方格的中心橄唬。它被用淺藍色描邊赋焕，以表示它被加入到關閉列表中了。所有的相鄰格現(xiàn)在都在開啟列表中轧坎，它們被用淺綠色描邊宏邮。每個方格都有一個灰色指針反指他們的父方格，也就是開始的方格缸血。
[圖2]
接著蜜氨，我們選擇開啟列表中的臨近方格，大致重復前面的過程捎泻，如下飒炎。但是，哪個方格是我們要選擇的呢笆豁？是那個F值最低的郎汪。
路徑評分
選擇路徑中經(jīng)過哪個方格的關鍵是下面這個等式：
F = G + H
這里：
G = 從起點A，沿著產(chǎn)生的路徑闯狱，移動到網(wǎng)格上指定方格的移動耗費煞赢。
H = 從網(wǎng)格上那個方格移動到終點B的預估移動耗費。這經(jīng)常被稱為啟發(fā)式的哄孤，可能會讓你有點迷惑照筑。這樣叫的原因是因為它只是個猜測。我們沒辦法事先知道路徑的長度瘦陈，因為路上可能存在各種障礙(墻凝危，水，等等)晨逝。雖然本文只提供了一種計算H的方法蛾默，但是你可以在網(wǎng)上找到很多其他的方法芹关。
我們的路徑是通過反復遍歷開啟列表并且選擇具有最低F值的方格來生成的户秤。文章將對這個過程做更詳細的描述绳慎。首先题涨，我們更深入的看看如何計算這個方程功偿。
正如上面所說眷细，G表示沿路徑從起點到當前點的移動耗費朋魔。在這個例子里函荣，我們令水平或者垂直移動的耗費為10，對角線方向耗費為14浸踩。我們?nèi)∵@些值是因為沿對角線的距離是沿水平或垂直移動耗費的的根號2（別怕），或者約1.414倍统求。為了簡化检碗，我們用10和14近似。比例基本正確码邻，同時我們避免了求根運算和小數(shù)折剃。這不是只因為我們怕麻煩或者不喜歡數(shù)學。使用這樣的整數(shù)對計算機來說也更快捷像屋。你不就就會發(fā)現(xiàn)怕犁，如果你不使用這些簡化方法，尋路會變得很慢己莺。
既然我們在計算沿特定路徑通往某個方格的G值奏甫，求值的方法就是取它父節(jié)點的G值，然后依照它相對父節(jié)點是對角線方向或者直角方向(非對角線)凌受，分別增加14和10阵子。例子中這個方法的需求會變得更多，因為我們從起點方格以外獲取了不止一個方格胜蛉。
H值可以用不同的方法估算挠进。我們這里使用的方法被稱為曼哈頓方法，它計算從當前格到目的格之間水平和垂直的方格的數(shù)量總和誊册，忽略對角線方向领突。然后把結果乘以10。這被成為曼哈頓方法是因為它看起來像計算城市中從一個地方到另外一個地方的街區(qū)數(shù)案怯，在那里你不能沿對角線方向穿過街區(qū)君旦。很重要的一點，我們忽略了一切障礙物殴泰。這是對剩余距離的一個估算于宙，而非實際值，這也是這一方法被稱為啟發(fā)式的原因悍汛。想知道更多捞魁？你可以在這里找到方程和額外的注解。
F的值是G和H的和离咐。第一步搜索的結果可以在下面的圖表中看到谱俭。F,G和H的評分被寫在每個方格里奉件。正如在緊挨起始格右側的方格所表示的，F(xiàn)被打印在左上角昆著，G在左下角县貌，H則在右下角。
[圖3]
現(xiàn)在我們來看看這些方格凑懂。寫字母的方格里煤痕，G = 10。這是因為它只在水平方向偏離起始格一個格距接谨。緊鄰起始格的上方摆碉，下方和左邊的方格的G值都等于10。對角線方向的G值是14脓豪。
H值通過求解到紅色目標格的曼哈頓距離得到巷帝，其中只在水平和垂直方向移動，并且忽略中間的墻扫夜。用這種方法楞泼，起點右側緊鄰的方格離紅色方格有3格距離，H值就是30笤闯。這塊方格上方的方格有4格距離(記住堕阔，只能在水平和垂直方向移動)，H值是40望侈。你大致應該知道如何計算其他方格的H值了～印蔬。
每個格子的F值，還是簡單的由G和H相加得到
繼續(xù)搜索
為了繼續(xù)搜索脱衙，我們簡單的從開啟列表中選擇F值最低的方格侥猬。然后，對選中的方格做如下處理：
4．把它從開啟列表中刪除捐韩，然后添加到關閉列表中退唠。
5．檢查所有相鄰格子。跳過那些已經(jīng)在關閉列表中的或者不可通過的(有墻荤胁，水的地形瞧预，或者其他 無法通過的地形)，把他們添加進開啟列表仅政，如果他們還不在里面的話垢油。把選中的方格作為新的方格的父節(jié)點。
6．如果某個相鄰格已經(jīng)在開啟列表里了圆丹，檢查現(xiàn)在的這條路徑是否更好滩愁。換句話說，檢查如果我們用新的路徑到達它的話辫封，G值是否會更低一些硝枉。如果不是廉丽，那就什么都不做。
另一方面妻味，如果新的G值更低正压，那就把相鄰方格的父節(jié)點改為目前選中的方格（在上面的圖表中，把箭頭的方向改為指向這個方格）责球。最后焦履，重新計算F和G的值。如果這看起來不夠清晰雏逾，你可以看下面的圖示裁良。
好了，讓我們看看它是怎么運作的校套。我們最初的9格方格中，在起點被切換到關閉列表中后牧抵，還剩8格留在開啟列表中笛匙。這里面，F(xiàn)值最低的那個是起始格右側緊鄰的格子犀变，它的F值是40妹孙。因此我們選擇這一格作為下一個要處理的方格。在緊隨的圖中获枝，它被用藍色突出顯示蠢正。
[圖4]
首先，我們把它從開啟列表中取出省店，放入關閉列表(這就是他被藍色突出顯示的原因)嚣崭。然后我們檢查相鄰的格子。哦懦傍，右側的格子是墻雹舀，所以我們略過。左側的格子是起始格粗俱。它在關閉列表里说榆，所以我們也跳過它。
其他4格已經(jīng)在開啟列表里了寸认，于是我們檢查G值來判定签财，如果通過這一格到達那里，路徑是否更好偏塞。我們來看選中格子下面的方格唱蒸。它的G值是14。如果我們從當前格移動到那里烛愧，G值就會等于20(到達當前格的G值是10油宜，移動到上面的格子將使得G值增加10)掂碱。因為G值20大于14，所以這不是更好的路徑慎冤。如果你看圖疼燥，就能理解。與其通過先水平移動一格蚁堤，再垂直移動一格醉者，還不如直接沿對角線方向移動一格來得簡單。
當我們對已經(jīng)存在于開啟列表中的4個臨近格重復這一過程的時候披诗，我們發(fā)現(xiàn)沒有一條路徑可以通過使用當前格子得到改善撬即，所以我們不做任何改變。既然我們已經(jīng)檢查過了所有鄰近格呈队，那么就可以移動到下一格了剥槐。
于是我們檢索開啟列表，現(xiàn)在里面只有7格了宪摧，我們?nèi)匀贿x擇其中F值最低的粒竖。有趣的是，這次几于，有兩個格子的數(shù)值都是54蕊苗。我們?nèi)绾芜x擇？這并不麻煩沿彭。從速度上考慮朽砰，選擇最后添加進列表的格子會更快捷。這種導致了尋路過程中喉刘，在靠近目標的時候瞧柔，優(yōu)先使用新找到的格子的偏好。但這無關緊要睦裳。（對相同數(shù)值的不同對待非剃，導致不同版本的A*算法找到等長的不同路徑。）
那我們就選擇起始格右下方的格子推沸，如圖备绽。
[圖5]
這次，當我們檢查相鄰格的時候鬓催，發(fā)現(xiàn)右側是墻肺素，于是略過。上面一格也被略過宇驾。我們也略過了墻下面的格子倍靡。為什么呢？因為你不能在不穿越墻角的情況下直接到達那個格子课舍。你的確需要先往下走然后到達那一格塌西，按部就班的走過那個拐角他挎。(注解：穿越拐角的規(guī)則是可選的。它取決于你的節(jié)點是如何放置的捡需。)
這樣一來办桨，就剩下了其他5格。當前格下面的另外兩個格子目前不在開啟列表中站辉，于是我們添加他們呢撞，并且把當前格指定為他們的父節(jié)點。其余3格饰剥，兩個已經(jīng)在關閉列表中（起始格殊霞，和當前格上方的格子，在表格中藍色高亮顯示),于是我們略過它們汰蓉。最后一格绷蹲，在當前格的左側，將被檢查通過這條路徑顾孽，G值是否更低瘸右。不必擔心，我們已經(jīng)準備好檢查開啟列表中的下一格了岩齿。
我們重復這個過程，知道目標格被添加進開啟列表苞俘，就如在下面的圖中所看到的盹沈。
[圖6]
注意，起始格下方格子的父節(jié)點已經(jīng)和前面不同的吃谣。之前它的G值是28乞封，并且指向右上方的格子。現(xiàn)在它的G值是20岗憋，指向它上方的格子肃晚。這在尋路過程中的某處發(fā)生，當應用新路徑時仔戈，G值經(jīng)過檢查變得低了－于是父節(jié)點被重新指定关串，G和F值被重新計算。盡管這一變化在這個例子中并不重要监徘，在很多場合晋修，這種變化會導致尋路結果的巨大變化。
那么凰盔，我們怎么確定這條路徑呢墓卦？很簡單，從紅色的目標格開始户敬，按箭頭的方向朝父節(jié)點移動落剪。這最終會引導你回到起始格睁本，這就是你的路徑！看起來應該像圖中那樣忠怖。從起始格A移動到目標格B只是簡單的從每個格子（節(jié)點）的中點沿路徑移動到下一個呢堰，直到你到達目標點。就這么簡單脑又。
[圖7]
A*方法總結
好暮胧，現(xiàn)在你已經(jīng)看完了整個說明，讓我們把每一步的操作寫在一起：
把起始格添加到開啟列表问麸。
重復如下的工作：
a) 尋找開啟列表中F值最低的格子往衷。我們稱它為當前格。
b) 把它切換到關閉列表严卖。
c) 對相鄰的8格中的每一個席舍？
如果它不可通過或者已經(jīng)在關閉列表中，略過它哮笆。反之如下来颤。
如果它不在開啟列表中，把它添加進去稠肘。把當前格作為這一格的父節(jié)點福铅。記錄這一格的F,G,和H值。
如果它已經(jīng)在開啟列表中项阴，用G值為參考檢查新的路徑是否更好滑黔。更低的G值意味著更好的路徑。如果是這樣环揽，就把這一格的父節(jié)點改成當前格略荡，并且重新計算這一格的G和F值。如果你保持你的開啟列表按F值排序歉胶，改變之后你可能需要重新對開啟列表排序汛兜。
d) 停止，當你
把目標格添加進了開啟列表通今，這時候路徑被找到粥谬，或者
沒有找到目標格，開啟列表已經(jīng)空了辫塌。這時候帝嗡，路徑不存在。
保存路徑璃氢。從目標格開始哟玷，沿著每一格的父節(jié)點移動直到回到起始格。這就是你的路徑。
題外話
離題一下巢寡，見諒喉脖，值得一提的是，當你在網(wǎng)上或者相關論壇看到關于A*的不同的探討抑月，你有時會看到一些被當作A*算法的代碼而實際上他們不是树叽。要使用A*，你必須包含上面討論的所有元素－－特定的開啟和關閉列表谦絮，用F,G和H作路徑評價题诵。有很多其他的尋路算法，但他們并不是A*层皱，A*被認為是他們當中最好的性锭。Bryan Stout在這篇文章后面的參考文檔中論述了一部分，包括他們的一些優(yōu)點和缺點叫胖。有時候特定的場合其他算法會更好草冈，但你必須很明確你在作什么。好了瓮增，夠多的了怎棱。回到文章绷跑。
實現(xiàn)的注解
現(xiàn)在你已經(jīng)明白了基本原理拳恋，寫你的程序的時候還得考慮一些額外的東西。下面這些材料中的一些引用了我用C++和Blitz Basic寫的程序砸捏，但對其他語言寫的代碼同樣有效谬运。
維護開啟列表：這是A*尋路算法最重要的組成部分。每次你訪問開啟列表带膜，你都需要尋找F值最低的方格。有幾種不同的方法實現(xiàn)這一點鸳谜。你可以把路徑元素隨意保存膝藕，當需要尋找F值最低的元素的時候，遍歷開啟列表咐扭。這很簡單芭挽，但是太慢了，尤其是對長路徑來說蝗肪。這可以通過維護一格排好序的列表來改善袜爪，每次尋找F值最低的方格只需要選取列表的首元素。當我自己實現(xiàn)的時候薛闪，這種方法是我的首選辛馆。
在小地圖。這種方法工作的很好，但它并不是最快的解決方案昙篙。更苛求速度的A*程序員使用叫做“binary heap”的方法腊状，這也是我在代碼中使用的方法。憑我的經(jīng)驗苔可，這種方法在大多數(shù)場合會快2～3倍缴挖，并且在長路經(jīng)上速度呈幾何級數(shù)提升(10倍以上速度)。如果你想了解更多關于binary heap的內(nèi)容焚辅，查閱我的文章：Using Binary Heaps in A* Pathfinding映屋。
其他單位：如果你恰好看了我的例子代碼，你會發(fā)現(xiàn)它完全忽略了其他單位同蜻。我的尋路者事實上可以相互穿越棚点。取決于具體的游戲，這也許可以埃仪，也許不行乙濒。如果你打算考慮其他單位，希望他們能互相繞過卵蛉，我建議在尋路算法中忽略其他單位颁股，寫一些新的代碼作碰撞檢測。當碰撞發(fā)生傻丝，你可以生成一條新路徑或者使用一些標準的移動規(guī)則(比如總是向右甘有，等等)直到路上沒有了障礙，然后再生成新路徑葡缰。為什么在最初的路徑計算中不考慮其他單位呢亏掀？那是因為其他單位會移動，當你到達他們原來的位置的時候泛释，他們可能已經(jīng)離開了滤愕。這有可能會導致奇怪的結果，一個單位突然轉(zhuǎn)向怜校，躲避一個已經(jīng)不在那里的單位间影，并且會撞到計算完路徑后，沖進它的路徑中的單位茄茁。
然而魂贬，在尋路算法中忽略其他對象，意味著你必須編寫單獨的碰撞檢測代碼裙顽。這因游戲而異付燥，所以我把這個決定權留給你。參考文獻列表中愈犹，Bryan Stout的文章值得研究键科，里面有一些可能的解決方案(像魯棒追蹤，等等)。
一些速度方面的提示：當你開發(fā)你自己的A*程序萝嘁，或者改寫我的梆掸，你會發(fā)現(xiàn)尋路占據(jù)了大量的CPU時間，尤其是在大地圖上有大量對象在尋路的時候牙言。如果你閱讀過網(wǎng)上的其他材料酸钦，你會明白，即使是開發(fā)了星際爭霸或帝國時代的專家咱枉，這也無可奈何卑硫。如果你覺得尋路太過緩慢，這里有一些建議也許有效：
使用更小的地圖或者更少的尋路者蚕断。
不要同時給多個對象尋路欢伏。取而代之的是把他們加入一個隊列，把尋路過程分散在幾個游戲周期中亿乳。如果你的游戲以40周期每秒的速度運行硝拧，沒人能察覺。但是他們會發(fā)覺游戲速度突然變慢葛假，當大量尋路者計算自己路徑的時候障陶。
盡量使用更大的地圖網(wǎng)格。這降低了尋路中搜索的總網(wǎng)格數(shù)聊训。如果你有志氣抱究，你可以設計兩個或者更多尋路系統(tǒng)以便使用在不同場合，取決于路徑的長度带斑。這也正是專業(yè)人士的做法鼓寺，用大的區(qū)域計算長的路徑，然后在接近目標的時候切換到使用小格子/區(qū)域的精細尋路勋磕。如果你對這個觀點感興趣妈候，查閱我的文章 ：Two-Tiered A* Pathfinding。
使用路徑點系統(tǒng)計算長路徑挂滓，或者預先計算好路徑并加入到游戲中苦银。
預處理你的地圖，表明地圖中哪些區(qū)域是不可到達的杂彭。我把這些區(qū)域稱作“孤島”墓毒。事實上吓揪，他們可以是島嶼或其他被墻壁包圍等無法到達的任意區(qū)域亲怠。A*的下限是，當你告訴它要尋找通往那些區(qū)域的路徑時柠辞，它會搜索整個地圖团秽，直到所有可到達的方格/節(jié)點都被通過開啟列表和關閉列表的計算。這會浪費大量的CPU時間∠扒冢可以通過預先確定這些區(qū)域（比如通過flood-fill或類似的方法)來避免這種情況的發(fā)生,用某些種類的數(shù)組記錄這些信息踪栋，在開始尋路前檢查它。在我Blitz版本的代碼中图毕，我建立了一個地圖預處理器來作這個工作夷都。它也標明了尋路算法可以忽略的死端，這進一步提高了尋路速度予颤。
不同的地形損耗：在這個教程和我附帶的程序中囤官，地形只有兩種－可通過的和不可通過的。但是你可能會需要一些可通過的地形蛤虐，但是移動耗費更高－沼澤党饮，小山，地牢的樓梯驳庭，等等刑顺。這些都是可通過但是比平坦的開闊地移動耗費更高的地形。類似的饲常，道路應該比自然地形移動耗費更低蹲堂。
這個問題很容易解決，只要在計算任何地形的G值的時候增加地形損耗就可以了不皆。簡單的給它增加一些額外的損耗就可以了贯城。由于A*算法已經(jīng)按照尋找最低耗費的路徑來設計，所以很容易處理這種情況霹娄。在我提供的這個簡單的例子里能犯，地形只有可通過和不可通過兩種，A*會找到最短犬耻，最直接的路徑踩晶。但是在地形耗費不同的場合，耗費最低的路徑也許會包含很長的移動距離－就像沿著路繞過沼澤而不是直接穿過它枕磁。
一種需額外考慮的情況是被專家稱之為“influence mapping”的東西（暫譯為影響映射圖）渡蜻。就像上面描述的不同地形耗費一樣，你可以創(chuàng)建一格額外的分數(shù)系統(tǒng)计济，并把它應用到尋路的AI中茸苇。假設你有一張有大批尋路者的地圖，他們都要通過某個山區(qū)沦寂。每次電腦生成一條通過那個關口的路徑学密，它就會變得更擁擠。如果你愿意传藏，你可以創(chuàng)建一個影響映射圖對有大量屠殺事件的格子施以不利影響腻暮。這會讓計算機更傾向安全些的路徑彤守，并且?guī)椭苊饪偸莾H僅因為路徑短(但可能更危險)而持續(xù)把隊伍和尋路者送到某一特定路徑。
處理未知區(qū)域：你是否玩過這樣的PC游戲哭靖，電腦總是知道哪條路是正確的具垫，即使它還沒有偵察過地圖？對于游戲试幽，尋路太好會顯得不真實筝蚕。幸運的是，這是一格可以輕易解決的問題铺坞。
答案就是為每個不同的玩家和電腦（每個玩家饰及，而不是每個單位－－那樣的話會耗費大量的內(nèi)存）創(chuàng)建一個獨立的“knownWalkability”數(shù)組，每個數(shù)組包含玩家已經(jīng)探索過的區(qū)域康震，以及被當作可通過區(qū)域的其他區(qū)域燎含，直到被證實。用這種方法腿短，單位會在路的死端徘徊并且導致錯誤的選擇直到他們在周圍找到路屏箍。一旦地圖被探索了，尋路就像往常那樣進行橘忱。
平滑路徑：盡管A*提供了最短赴魁，最低代價的路徑，它無法自動提供看起來平滑的路徑钝诚∮庇看一下我們的例子最終形成的路徑（在圖7）。最初的一步是起始格的右下方凝颇，如果這一步是直接往下的話潘拱，路徑不是會更平滑一些嗎？
有幾種方法來解決這個問題拧略。當計算路徑的時候可以對改變方向的格子施加不利影響芦岂，對G值增加額外的數(shù)值。也可以換種方法垫蛆，你可以在路徑計算完之后沿著它跑一遍禽最，找那些用相鄰格替換會讓路徑看起來更平滑的地方。想知道完整的結果袱饭，查看 Marco Pinter 發(fā)表在 Gamasutra.com 的 一篇文章：Toward More Realistic Pathfinding?(免費川无，但是需要注冊)。
非方形搜索區(qū)域：在我們的例子里虑乖，我們使用簡單的2D方形圖懦趋。你可以不使用這種方式。你可以使用不規(guī)則形狀的區(qū)域决左。想想冒險棋的游戲愕够，和游戲中那些國家。你可以設計一個像那樣的尋路關卡佛猛。為此惑芭，你可能需要建立一個國家相鄰關系的表格，和從一個國家移動到另一個的G值继找。你也需要估算H值的方法遂跟。其他的事情就和例子中完全一樣了。當你需要向開啟列表中添加新元素的時候婴渡，不需使用相鄰的格子幻锁，取而代之的是從表格中尋找相鄰的國家。
類似的边臼，你可以為一張確定的地形圖創(chuàng)建路徑點系統(tǒng)哄尔，路徑點一般是路上，或者地牢通道的轉(zhuǎn)折點柠并。作為游戲設計者岭接，你可以預設這些路徑點声怔。兩個路徑點被認為是相鄰的如果他們之間的直線上沒有障礙的話忙芒。在冒險棋的例子里，你可以保存這些相鄰信息在某個表格里昧廷，當需要在開啟列表中添加元素的時候使用它粘拾。然后你就可以記錄關聯(lián)的G值（可能使用兩點間的直線距離）窄锅，H值（可以使用到目標點的直線距離），其他都按原先的做就可以了缰雇。
另一個在非方形區(qū)域搜索RPG地圖的例子入偷，查看我的文章：Two-Tiered A* Pathfinding。
進一步的閱讀
好械哟，現(xiàn)在你對一些進一步的觀點有了初步認識盯串。這時，我建議你研究我的源代碼戒良。包里面包含兩個版本体捏，一個是用C++寫的，另一個用Blitz Basic糯崎。順便說一句几缭，兩個版本都注釋詳盡，容易閱讀沃呢，這里是鏈接年栓。
例子代碼：A* Pathfinder (2D) Version 1.71
如果你既不用C++也不用Blitz Basic,在C++版本里有兩個小的可執(zhí)行文件。Blitz Basic可以在從Blitz Basic網(wǎng)站免費下載的 litz Basic 3D(不是Blitz Plus)演示版上運行薄霜。Ben O''Neill提供一個聯(lián)機演示可以在這里找到某抓。
你也該看看以下的網(wǎng)頁纸兔。讀了這篇教程后，他們應該變得容易理解多了否副。
Amit 的 A* 頁面：這是由Amit Patel制作汉矿，被廣泛引用的頁面，如果你沒有事先讀這篇文章备禀，可能會有點難以理解洲拇。值得一看。尤其要看Amit關于這個問題的自己的看法曲尸。
Smart Moves：智能尋路：Bryan Stout發(fā)表在Gamasutra.com的這篇文章需要注冊才能閱讀赋续。注冊是免費的而且比起這篇文章和網(wǎng)站的其他資源，是非常物有所值的另患。Bryan用Delphi寫的程序幫助我學習A*纽乱，也是我的A*代碼的靈感之源。它還描述了A*的幾種變化昆箕。
地形分析：這是一格高階迫淹，但是有趣的話題，Dave Pottinge撰寫为严，Ensemble Studios的專家敛熬。這家伙參與了帝國時代和君王時代的開發(fā)。別指望看懂這里所有的東西第股，但是這是篇有趣的文章也許會讓你產(chǎn)生自己的想法应民。它包含一些對mip-mapping，influence mapping以及其他一些高級AI/尋路觀點夕吻。對"flood filling"的討論使我有了我自己的“死端”和“孤島”的代碼的靈感诲锹，這些包含在我Blitz版本的代碼中。
其它一些值得一看的網(wǎng)站：
其它參考文章：
Artificial Intelligence:Pathfinding and Searching
Featured Articles:Featured Articles
好了涉馅，這就是全部归园。如果你剛好寫一個運用這些觀點的程序，我想見識見識稚矿。你可以這樣聯(lián)系我：
現(xiàn)在庸诱，好運！?
