聲明

????本文譯自 Patrick Lester先生的一片博文，覺著實在是一片優(yōu)秀的文章，于是打算花點時間將其翻譯成中文展辞，一來自己學(xué)習(xí)一番，二來可以方便國內(nèi)讀者万牺。如有謬誤罗珍，歡迎拍磚。原文請參見： https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/

序

????A-Start 算法對于初學(xué)者來說可能有些復(fù)雜脚粟，盡管網(wǎng)上有很多講解它的文章覆旱，但大多是在認為讀者已對該算法有一定程度了解的基礎(chǔ)上寫的。這篇博文則主要面向入門小白核无。
????這篇文章不是我們學(xué)習(xí)A*算法的終點，而是我們閱讀其他相關(guān)內(nèi)容的基礎(chǔ)团南，因此在文末我列出了一些優(yōu)秀的博文以供大家進一步學(xué)習(xí)。
????最后我還得聲明一點，這篇文章并不是面向程序設(shè)計的局义，你可以將本文的觀點運用到任何編程語言當中檩帐。我也在文末給出了一個例子程序的鏈接湃密，你也許會用得上。這個例子包含C++和Basic兩個版本四敞，當然也包含了可執(zhí)行文件在里面勾缭。

介紹：搜索區(qū)

圖1

????你應(yīng)該已經(jīng)發(fā)現(xiàn)努释，我們需要做的第一件事就是把搜索區(qū)與分成一個一個的網(wǎng)格，即搜索區(qū)簡化咬摇。通過這個方法將我們的搜索區(qū)域簡化成了一個二維數(shù)組伐蒂，數(shù)組中的每個元素都代表一個網(wǎng)格，并且記錄了狀態(tài)為可達或不可達肛鹏。在路徑搜尋的過程中逸邦，逐步判斷下一步應(yīng)當踏入哪個網(wǎng)格，直到達到目標點在扰。
????我們把每個網(wǎng)格的中心點叫做“節(jié)點”缕减，當參閱其他一些關(guān)于路徑搜尋的文章時，你會發(fā)現(xiàn)他們也是稱“節(jié)點”芒珠。為什么不直接叫網(wǎng)格呢桥狡？因為除了正方形格網(wǎng)外我們還可將搜索去分成其他不同形狀的多邊形，比如矩形皱卓、正六邊形裹芝、三角形甚至其他任意形狀。所以我們在這些多邊形上選取一個代表點（幾何中心娜汁、重心等）來代表多邊形本身嫂易，統(tǒng)一稱為“節(jié)點”。

開始搜索

????在上面的討論中掐禁，我們將搜索區(qū)簡化成了一個個網(wǎng)格炬搭，下一步就是在此基礎(chǔ)上搜索最短路徑蜈漓。從A點開始，向外搜索相鄰網(wǎng)格知道到達目標點宫盔。
????1.從A點開始融虽，將其添加到待考慮的“open list”中，"open list"就像一張購物清單灼芭，現(xiàn)在單子里只有一件物品有额，但稍后我們會往里加入更多。里面包含了到目標點的最短路徑沿途可能會經(jīng)過的網(wǎng)格彼绷，因此需要我們逐個檢查判別巍佑。
????2.考察與起點A相鄰的所有網(wǎng)格，代表墻寄悯、水域或其他非法區(qū)域（不可達區(qū)域）的直接略過萤衰，可達的網(wǎng)格加入“open list”，對于所有選中的相鄰的網(wǎng)格猜旬，同時記錄網(wǎng)格A為其"父親網(wǎng)格"脆栋，這對于我們追蹤路徑十分重要，后面我們將詳細討論洒擦。
????3.把網(wǎng)格A從"open list"中去掉椿争，將其加入"closed list"中，從現(xiàn)在開始就不需要再考慮它了熟嫩。
????到這一步你就進行到了如下圖所示的一個狀態(tài)秦踪。中間綠色的網(wǎng)格代表你的起點，起點網(wǎng)格的邊緣以亮綠色高亮顯示表示該網(wǎng)格已經(jīng)加入到"closed list"掸茅。周圍所有相鄰的網(wǎng)格都被加入到了"open list"等待檢核椅邓，并且每個網(wǎng)格里都有一個個灰色的指針標記指向該網(wǎng)格的“父親網(wǎng)格”，也就是我們的起點網(wǎng)格A昧狮。

圖2

????下一步我們將從"open list"中選取一個F值最小的網(wǎng)格希坚，因此如何計算F值是我們接下來要討論的內(nèi)容。

路徑評分

????路徑構(gòu)建過程中網(wǎng)格選取的關(guān)鍵就是如何計算下面這個等式：F=G+H

• G=從起始網(wǎng)格A到指定其他網(wǎng)格的移動耗費
• H=任意格網(wǎng)到終點網(wǎng)格B的移動耗費陵且。我們通常使用啟發(fā)式算法來計算裁僧，看到這里你也許有些迷惑。之所以稱為啟發(fā)式算法是因為它實質(zhì)就是一種估計慕购，在找到最短路徑之前我們都不清楚到B的實際最短距離是多少聊疲，因為中途可能遇到擋墻、水體等障礙物而導(dǎo)致你繞道沪悲。在本文我們將介紹一種計算H值的方法获洲，當然你在其他文章中還可以找到更多優(yōu)秀的方法。通過反復(fù)遍歷"open list"選取具有最小F值的網(wǎng)格殿如。在后面我們將詳細討論這個過程贡珊，首先我們來看看如何計算這個等式最爬。
  ????上面我們指出，G代表起點網(wǎng)格A到路徑經(jīng)過的網(wǎng)格所耗費的距離门岔。在這個例子中爱致，定義網(wǎng)格移動的水平或垂直耗費為10，對角移動的耗費為14寒随。采用這兩個距離耗費值是因為糠悯，對角移動的實際耗費距離為2的算術(shù)平方根，大概是水平和垂直移動距離耗費的1.414倍妻往。為了簡單起見互艾，分別使用10和14代替，這樣可避免開方和浮點數(shù)的計算讯泣。所以這并不是因為我們在犯迷糊或者討厭數(shù)學(xué)纫普，哈哈。在計算機中使用整數(shù)進行計算比使用小數(shù)更快好渠，很快你會發(fā)現(xiàn)昨稼，如果不使用整數(shù)計算，那么路徑尋找真的是太慢了晦墙。
  ????計算G值的方法就是獲取到該點“父親節(jié)點”的G值，然后在此基礎(chǔ)上根據(jù)從"父親節(jié)點"是否對角移動到該節(jié)點加上10或者14的耗費肴茄。這個方法的必要性稍后會顯得更加明顯晌畅，因為我們有不止一條從起始網(wǎng)格開始的路徑。
  ????H 值的計算方法有很多寡痰，我們在這里采用的是曼哈頓距離抗楔，通過計算從考察網(wǎng)格到目標網(wǎng)格的水平和垂直移動的網(wǎng)格數(shù)目之和，期間不可慮對角移動以及途中的障礙物拦坠，然后將總數(shù)和乘上10连躏。看到這里你也許會猜想說贞滨，這啟發(fā)式算法就是估算當前網(wǎng)格與目標網(wǎng)格之間的直線距離入热。其實不對，我們實際上是在嘗試估計到終點的剩余距離晓铆，估計越準確勺良，算法就越快。如果估計距離大于實際距離骄噪，那就不能保證最后得到的路徑是最短的了尚困，只能說近似最短，我們稱這種情況為“不可接受的啟發(fā)式”链蕊。在這個例子采用的曼哈頓方法就是“不可接受”的事甜，因為曼哈頓距離比實際距離稍長谬泌。但因為這種方法簡單明了，并且只是比實際長度稍微長了些逻谦，所以還是堅持采用它掌实。在很少情況下會導(dǎo)致求得的路徑不是最短的，如果你想了解更多關(guān)于啟發(fā)式算法的內(nèi)容跨跨，請參考這個鏈接潮峦。
  ????通過逐步累加G和H值計算得到F，路徑搜索第一步的結(jié)果如下圖所示勇婴，每個網(wǎng)格都標注了F忱嘹、G和H評分，左上角是F值耕渴，左下角是G值拘悦，右下角是H值。
  
  圖3
  
  ????注意看標記了字母的這個網(wǎng)格橱脸，G=10表示從起點網(wǎng)格A向右移動一個水平距離即到達該網(wǎng)格础米，類似的，從該網(wǎng)格向右移動三個水平距離即到達終點紅色網(wǎng)格添诉，因此H值為30亏掀，而緊接著這個網(wǎng)格上面一個網(wǎng)格的H值對應(yīng)就是40（注意H值的計算我們只能水平或是垂直運動）。以此類推你就可以計算出其他網(wǎng)格的評分值了巡揍。

繼續(xù)搜索

????在路徑搜索過程中耿眉，我們從"open list"中選出F值最小的網(wǎng)格，然后進行下面的步驟：
????最初的9個網(wǎng)格中须眷，在起始網(wǎng)格A(綠色)被移至"closed list"后竖瘾，"open list"中就還剩下周圍的8個網(wǎng)格，從圖4我們會發(fā)現(xiàn)花颗，緊接著右邊的那個網(wǎng)格就是F最小(40)的網(wǎng)格捕传，所以選擇這個格網(wǎng)作為下一步位置。對應(yīng)圖中邊緣高亮顯示的網(wǎng)格扩劝。

圖4

????首先將選出的最小F值的網(wǎng)格從"open list"中移除并加入到"closed list"（這就是為什么該網(wǎng)格邊緣現(xiàn)在是高亮顯示的）庸论，該網(wǎng)格記為node1，然后開始檢核node1接下周圍的8個網(wǎng)格再次選出F值最小的一個網(wǎng)格棒呛。右邊的網(wǎng)格代表的是墻體所以忽略掉葡公，左邊的綠色網(wǎng)格（即我們的起始網(wǎng)格）由于在前面的步驟中已經(jīng)加入到"closed list"，所以也不予考慮条霜。剩下的四個網(wǎng)格已經(jīng)加入的"open list"催什，接下來我們考察經(jīng)由網(wǎng)格node1到達"open list"中的網(wǎng)格的路徑長度是否比不經(jīng)過node1的路徑短。以node1正上方的網(wǎng)格為例，如果我們不經(jīng)由node1直接從網(wǎng)格A到達該點蒲凶，那么G值為14气筋，如果經(jīng)過了node1，G值為20（在node1 G值為10的基礎(chǔ)上再加上垂直向上移動的耗費10）旋圆，20>14所以選擇不經(jīng)過node1直接從A對角到達node1正上方的網(wǎng)格宠默。對"open list"中的4個網(wǎng)格執(zhí)行同樣的判斷，我們發(fā)現(xiàn)都不會因為經(jīng)過node1而使得路徑變短灵巧。所以將直接考察這4個網(wǎng)格以從中選出下一步將到達的位置搀矫。
????去除node1后"open list"還剩下7個考察對象，遍歷"open list"獲取F最小的那個網(wǎng)格刻肄，在給出的例子中瓤球，F(xiàn)最小值為54,并且有兩個網(wǎng)格都是54。選哪個呢敏弃？這不是那么重要卦羡。處于算法的速度考慮，我們應(yīng)該選擇相對后加入到"open list"中那個網(wǎng)格麦到，這會使得我們的搜索算法在一步步接近終點的搜索過程中更偏向于選擇最新發(fā)現(xiàn)的網(wǎng)格绿饵。但這確實不是那么重要（這就是為什么兩個不同版本的A-Start算法會得到不同的最短路徑長度）。因此我們選擇起始網(wǎng)格A右下方的網(wǎng)格瓶颠，如下圖所示拟赊，同樣邊緣已高亮顯示。

圖5

圖6

????注意：如上圖所示起始網(wǎng)格以下的第二個網(wǎng)格的個指標值發(fā)生了變化淑仆，在此之前G值為28涝婉，父親節(jié)點為它右上方的網(wǎng)格，現(xiàn)在它的父親節(jié)點為正上方的網(wǎng)格蔗怠。在路徑搜索過程中墩弯，當我們發(fā)現(xiàn)有一條更低耗費的路徑存在時，該網(wǎng)格的父親節(jié)點就會更新并且重新計算各指標值寞射。但是這個改變在這個例子中看起來也不是那么重要渔工，因為整個過程中有那么多的最佳道路的調(diào)整選擇二導(dǎo)致了許多不同的解決方案。
????所以我們是如何獲取到這條路徑的呢怠惶？簡單涨缚，從紅色的目標網(wǎng)格開始，根據(jù)記錄的父親節(jié)點逐個往回取策治，和箭頭的指示方向是一致的脓魏。這樣就回到了起始的網(wǎng)格Ａ，同時也得到了我們的最短路徑鏈通惫。如下面的插圖所示茂翔，Ａ移動到Ｂ的路徑搜尋說白了就是這么簡單的一件事：從一個網(wǎng)格的中心點移動到下一個網(wǎng)格的中心點，直到找到你希望到達的目標點為止履腋。

圖７

算法總結(jié)

????到這里你已經(jīng)對整個算法有了大概的了解珊燎，現(xiàn)在讓我們逐步羅列出算法過程：
????1.將當前網(wǎng)格currentNode從open list中刪除并加入到closed list；
????2.檢查currentNode周圍的網(wǎng)格遵湖，對于已加入到closed list的和現(xiàn)實中不可達的網(wǎng)格（如墻體悔政、水域或其他非法區(qū)）直接忽略，對于剩下的并且尚未加入到open list的網(wǎng)格延旧，我們將其加入到open list谋国，同時記錄currentNode為它們的父親網(wǎng)格；
????3.對于剩下的并且已經(jīng)加入到open list的與currentNode相鄰的網(wǎng)格記為neighborNode迁沫，考慮從起始點到該neighborNode是否還存在一條更佳的路徑芦瘾。換句話說，如果我們選擇經(jīng)由currentNode到達neighborNode是否會使得neighborNode的G值變得更小集畅，如果不會近弟，那啥也不用做；如果G值可變得更小挺智，就改變neighborNode的父親節(jié)點為currentNode祷愉，最后計算出neighborNode新的F值和G值并更新記錄。
????4.接著步驟2說，尚未加入到open list的網(wǎng)格我們會將其加入進去（當然也可能是算法啟動時初次加入起始點網(wǎng)格）二鳄；
????5.重復(fù)下面的步驟：
????????a)獲取到open list中最小F值對應(yīng)的網(wǎng)格迫摔，將其作為新的currentNode
????????b)將currentNode移到closed List
????????c)對于其周圍相鄰的8個網(wǎng)格......
???????????? - 如果網(wǎng)格不可達或者已經(jīng)加入到closed list，忽略泥从，否則執(zhí)行下面的步驟
???????????? - 如果網(wǎng)格不在open list中句占，則加入到open list，記錄當前網(wǎng)格currentNode為其父親節(jié)點躯嫉，計算出F值纱烘、G值和H值并記錄。
???????????? - 如果已經(jīng)加入到open list中祈餐，以G為指標考察是否存在更佳路徑擂啥，G值越低我們則認為路徑約佳。如果經(jīng)由currentNode達到這個相鄰網(wǎng)格的路徑耗費更低（即路徑更佳）帆阳，那么就需更改這個相鄰網(wǎng)格的付清節(jié)點為currentNode并重新計算F值和G值哺壶。如果你的open list是按F值排序的，那么還需要進行重排序蜒谤。
????????d)出現(xiàn)下列情況之一則算法終止：
???????????? - 終點網(wǎng)格已加入到closed list山宾，表示已找到最佳路徑，現(xiàn)在我們需要把這條路徑保存下來鳍徽。從終點網(wǎng)格開始资锰，根據(jù)記錄的父親節(jié)點往回逐步遞推直到起始網(wǎng)格，沿途經(jīng)過的網(wǎng)格即是我們所求的路徑了阶祭；
???????????? - 還沒有移動到終點網(wǎng)格但open list已經(jīng)空了绷杜，那就表示無解，算法終止濒募；
（注意：在這篇文章的早期版本中我們建議當目標網(wǎng)格被加入到open list時即終止算法鞭盟，而不是等到加入到closed list才終止，這樣可以提升算法效率并且在大多數(shù)時候會得到最短路徑解瑰剃。但也并不總是這樣齿诉，比如如果有條河流處于倒數(shù)第二個網(wǎng)格和最后一個網(wǎng)格之間時，它們之間的移動耗費可能發(fā)生很大變化）

題外話

????值得一提的是培他，當你在網(wǎng)上或者一些論壇讀到關(guān)于A-Star的文章時鹃两，你可能會發(fā)現(xiàn)有些人把一些并不是A-Star算法的代碼也稱作是A-Start遗座。提到A-Star算法舀凛，那一定包含我們在上面提到的這些元素，尤其是"open list"途蒋、"closed list"以及F猛遍、G、H的評分機制。當然還有許多其他的路徑搜索算法懊烤，但它們都不是A-Star梯醒，A-Star的算法性能總體上來說更為優(yōu)秀，在本文末給出的一片參考文章中腌紧，Bryan Stout先生討論了很多路徑尋找的算法的原理以及它們的優(yōu)缺點茸习。其實這些算法無孰優(yōu)孰劣之分，都有其適應(yīng)的場景壁肋，所以你在應(yīng)用相應(yīng)的算法之前必須搞清楚你的應(yīng)用場景号胚。好啦，回到正文......

算法實現(xiàn)的注意事項

????現(xiàn)在你已經(jīng)弄清楚了算法的基本原理浸遗，但是在算法實現(xiàn)的過程中還有一些需要注意的點猫胁。下面這些觀點雖然是針對C++和Blitz Basic的，但對于其他程序設(shè)計語言我想也同樣適用跛锌。
????1.避免碰撞
????如果你仔細看過我的代碼就會發(fā)現(xiàn)弃秆，屏幕上的其他單元都是被忽略掉的，這些單元之間可相互穿行髓帽。是否考慮這些單元取決與你的游戲設(shè)計菠赚。如果你打算在算法中考慮這些單元并讓他們相互移動，那么我建議你只考慮在計算路徑時已停止或與尋路單元相鄰的單位郑藏，把它們代表的當前位置視為不可達锈至。對于正在移動的相鄰單元，你可以通過懲罰位于其各自路徑上的節(jié)點來阻止沖突译秦，從而促使尋路單元找到備用路徑峡捡。
????如果你選擇考慮那些移動著非相鄰單元，那么需要一個方法來預(yù)測在給定時間點該單元的位置筑悴，這樣才能準確避開它们拙。否則你可能得到的是一條為了避開一些實際并不存在的單元而形成的彎彎曲曲的路徑。
????當然了阁吝，你還需要碰撞檢測代碼砚婆，因為無論當前計算出的路徑多么優(yōu)質(zhì)，它都是會隨著時間改變的突勇。當一個單元發(fā)生碰撞時装盯，就會重新計算路徑，如果另一個單元正在移動而不是正面碰撞甲馋，則在繼續(xù)當前路徑之前等待另一個單元走開埂奈。
????上面這些建議也許已經(jīng)足夠你開始A-Star之旅了，如果你想了解更多定躏，下面這些鏈接倒是很有用哦账磺。

• 自主導(dǎo)航：Craig Reynold's在自主導(dǎo)航上的工作與路徑搜索有所不同芹敌，但是也可集成到路徑搜索中以使單元移動和障礙規(guī)避方面的內(nèi)容更加完善；
• 計算機游戲中的轉(zhuǎn)向長短：這是一片十分有意思的關(guān)于導(dǎo)航和路徑搜索的文章垮抗，PDF格式氏捞。
• 協(xié)調(diào)單位運動：這篇文章的前面兩部分第一部分是由Age of Empires設(shè)計師Dava Pottinger撰寫的關(guān)于運動的形成和群體運動的內(nèi)容；
• 協(xié)調(diào)單位運動-續(xù)：Dava Pottinger的第二部分內(nèi)容冒版。
  ????2.可變區(qū)域耗費
  ????在這篇文章以及我提供的代碼中液茎，區(qū)域被分為兩大類---可達區(qū)域和不可達區(qū)域。但是如果如果有一種區(qū)域可達但是需要更高的移動耗費該如何處理呢辞嗡？比如沼澤豁护、山丘、地牢中的臺階等等欲间，我們有很多這樣的例子楚里。同樣的也存在一些區(qū)域可達但是移動耗費更低的區(qū)域，比如開闊地猎贴。
  ????這個問題還是比較好處理的班缎，在計算G值時把這些額外的耗費也考慮進去。在我們之前討論的A-Star算法中她渴，區(qū)域被分為可達和不可達兩類达址，A-Star將會找出最短、最直接的路徑趁耗。但是在區(qū)域耗費可變的情況下沉唠，最低耗費的路徑可能意味著更長的距離，比如說我們選擇繞過沼澤區(qū)域而不是直接坐船通過苛败。
  ????還需要考慮的一個比較有趣的點就是"影響地圖"满葛，跟上面討論到的可變區(qū)域耗費類似，我們可以創(chuàng)建一個額外的點體系運用到人工智能路徑中罢屈。設(shè)想一下嘀韧，你有一張地圖，其中存在一片難以同行的山區(qū)缠捌。每次我們的計算機在送角色通過這片區(qū)域時都十分“費勁”锄贷。因此你可以創(chuàng)建一個“影響地圖”，對經(jīng)過“屠殺區(qū)”的網(wǎng)格賦予響應(yīng)的懲罰因子曼月。這樣就會促使電腦選擇更為安全的區(qū)域通行谊却，這樣就可避免往一些危險的地方輸送軍隊，因為僅考慮了路徑最短二忽視了安全因素哑芹。
  ????另外一個需要加懲罰因子的就是移動單元附近的網(wǎng)格炎辨。A-Star算法的一個不足之處在于，當一組單元都在尋找到達相近位置的路徑時可能會產(chǎn)生大量的交叉覆蓋區(qū)域绩衷，因為會有多個網(wǎng)格選擇了相近的路徑到達目的地蹦魔。對已經(jīng)被其他起始網(wǎng)格占據(jù)的網(wǎng)格添加懲罰因子可保證各條線路的獨立性并減少碰撞。但不可以簡單把這些網(wǎng)格視為不可達區(qū)域咳燕，因為我們還是希望能在這有限的區(qū)域內(nèi)盡可能開辟更多的路徑勿决。當然了，對于路徑周圍的網(wǎng)格我們也應(yīng)施與一定的懲罰力度招盲，但并不是所有道路都這樣低缩，否則你就會得到一條為了閃避這些網(wǎng)格二形成的奇奇怪怪的路徑。道路所處的當前網(wǎng)格和即將通過的網(wǎng)格也要施以懲罰因子曹货，但并不包括已經(jīng)通過的網(wǎng)格區(qū)域咆繁。
  ????3.未知區(qū)域的處理
  ????你有沒有玩過這種電腦游戲，電腦總是很清楚該選擇哪條道路顶籽，即使你面對的是一片未知的地圖區(qū)域玩般。在游戲中看起來這似乎是不可實現(xiàn)的，但實際上這個問題很容易解決礼饱。
  ????問題的答案就是為每個玩家建立一個"已知可通行區(qū)"這樣一個數(shù)組來記錄玩家已經(jīng)達到過的區(qū)域坏为。使用這種方法，移動網(wǎng)格最終會走投無路并作出一些類似的錯誤選擇镊绪，知道它們清楚的了解到路徑周圍的情況匀伏。一旦地圖都被玩家“勘探”過以后，那么正常的路徑查找也就不是問題了蝴韭。
  ????4.道路平滑
  ????盡管A-Star算法可以搜索出歷程最短够颠、耗費最低的路徑，但卻沒有保證所給路徑是最平滑的榄鉴÷哪ィ看看前面的插圖7就會發(fā)現(xiàn)，路徑第一步是向右下方邁出的庆尘，還有沒有什么其他選擇讓道路看起來更加平滑呢蹬耘，如果你想深入了解，請參考這篇文章如何獲取更加真實的路徑减余。
  ????5.非正方形網(wǎng)格搜索區(qū)
  ????在本文的例子中综苔，
  ????......未完待續(xù)