本文轉(zhuǎn)自Unity Connect博主?majorWu
起源
? ? ? 由于一次面試被問(wèn)起AStar算法原理，我當(dāng)場(chǎng)面紅耳赤，不知怎么開(kāi)口，這個(gè)耳熟能詳?shù)膶ぢ匪惴?，我?duì)它的原理卻渾然不知，一直都有聽(tīng)大家說(shuō)到這個(gè)算法，也有調(diào)用過(guò)相關(guān)接口，然自己卻那么陌生，真想一頭鉆到地底。于是就有這邊篇記錄AStar算法原理的學(xué)習(xí)文章。
? ? ? ? AStar算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法。在包含各種障礙物的地圖中，為游戲角色的移動(dòng)，尋找一條到目標(biāo)地點(diǎn)最短路徑。
簡(jiǎn)介?
? ? ? ? AStar（又稱 A*），它結(jié)合了 Dijkstra 算法的節(jié)點(diǎn)信息（傾向于距離起點(diǎn)較近的節(jié)點(diǎn)）和貪心算法的最好優(yōu)先搜索算法信息（傾向于距離目標(biāo)較近的節(jié)點(diǎn)）?？梢韵?Dijkstra 算法一樣保證找到最短路徑，同時(shí)也像貪心最好優(yōu)先搜索算法一樣使用啟發(fā)值對(duì)算法進(jìn)行引導(dǎo)。
? ? ? ? 簡(jiǎn)單點(diǎn)說(shuō)，AStar的核心在于將游戲背景分為一個(gè)又一個(gè)格子，每個(gè)格子有自己的靠譜值，然后通過(guò)遍歷起點(diǎn)的格子去找到周圍靠譜的格子，接著繼續(xù)遍歷周圍…… 最終找到終點(diǎn)。
AStar算法原理
? ? ? ? 在游戲的地圖中，AStar會(huì)被預(yù)先烘焙成相應(yīng)的格子記錄相關(guān)信息。
上圖A表示起點(diǎn)，B表示終點(diǎn)，藍(lán)色方塊表示障礙物，我們需要找出一條路，從A點(diǎn)開(kāi)始，繞過(guò)藍(lán)色方塊，到達(dá)B點(diǎn)。
首先說(shuō)一下用到的名詞：
開(kāi)放列表：一個(gè)記錄所有被考慮來(lái)尋找最短路徑的網(wǎng)格集合
關(guān)閉列表：一個(gè)記錄下不會(huì)被考慮的網(wǎng)格集合
G ：表示從起點(diǎn)方格移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi) (可沿斜方向移動(dòng)).
H ：表示從指定的方格移動(dòng)到終點(diǎn)方格的預(yù)計(jì)耗費(fèi) (H啟發(fā)函數(shù)).
核心部分
? ? ? ? 下圖所示的中心方塊為當(dāng)前塊，已被放入關(guān)閉列表，那接下來(lái)怎么確定下一步要走的方格？
這就是Astar核心部分：路徑代價(jià)
? ? ? ? ? ? 權(quán)重值：F=G+H，G和H前面我們有介紹過(guò)，我們將根據(jù)這個(gè)權(quán)重值引導(dǎo)每一步的走向，直至目標(biāo)點(diǎn)
? ? ? ? ? ? 那么G和H我們應(yīng)該怎么計(jì)算，下面給出了三種基本的估價(jià)算法(也稱估價(jià)公式)，其算法示意圖如下：
分別為：曼哈頓估價(jià)法、幾何估價(jià)法、對(duì)角線估價(jià)法
我們以曼哈頓估價(jià)法為例：起點(diǎn)A(X1，Y1)，終點(diǎn)B(X2，B2)，那么距離可根據(jù)上圖第一幅圖可得出：D=X2-X1+Y2-Y1
現(xiàn)在我們知道了估價(jià)法，接下來(lái)我們繼續(xù)下一步方塊的確定。下圖是我們對(duì)前相鄰的每個(gè)方塊的估價(jià)，左上角表示F值，左下角表示G值，右下角表示H值。
通過(guò)F值比較，我們找出F值最小的方塊，也就是當(dāng)前方塊右側(cè)的那塊，標(biāo)記為C（F值為40），我們把當(dāng)前方塊放入關(guān)閉列表，周圍的方塊放到開(kāi)啟列表中，然后同上反復(fù)操作，找到C周圍相鄰的方塊（過(guò)濾掉藍(lán)色方塊的障礙區(qū)域及已被添加到關(guān)閉列表的），估價(jià)計(jì)算出相應(yīng)的F值，上下F值一樣，然后隨機(jī)找到了D，把當(dāng)前C放入關(guān)閉列表，周圍的方塊放到開(kāi)啟列表中(已存在的跳過(guò))
實(shí)現(xiàn)步驟:
1.把起始格添加到開(kāi)啟列表。
2.重復(fù)如下的工作：
? ? ? a) 尋找開(kāi)啟列表中估量代價(jià)F值最低的格子。我們稱它為當(dāng)前格。
? ? ? b) 把它切換到關(guān)閉列表。
? ? ? c) 對(duì)相鄰的8格中的每一個(gè)進(jìn)行如下操作
? ? ? ? ? * 如果它不可通過(guò)或者已經(jīng)在關(guān)閉列表中，略過(guò)它。反之如下。
? ? ? ? ? * 如果它不在開(kāi)啟列表中，把它添加進(jìn)去。把當(dāng)前格作為這一格的父節(jié)點(diǎn)。記錄這一格的F,G,和H值。
? ? ? ? ? * 如果它已經(jīng)在開(kāi)啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節(jié)點(diǎn)改成當(dāng)前格，并且重新計(jì)算這一格的G和F值。如果你保持你的開(kāi)啟列表按F值排序，改變之后你可能需要重新對(duì)開(kāi)啟列表排序。
? ? ? d) 停止，當(dāng)你
? ? ? ? ? * 把目標(biāo)格添加進(jìn)了關(guān)閉列表(注解)，這時(shí)候路徑被找到，或者
? ? ? ? ? * 沒(méi)有找到目標(biāo)格，開(kāi)啟列表已經(jīng)空了。這時(shí)候，路徑不存在。
3.保存路徑。從目標(biāo)格開(kāi)始，沿著每一格的父節(jié)點(diǎn)移動(dòng)直到回到起始格。這就是你的路徑。
最后本文是按自己對(duì)AStar的理解，按照自己的思路寫(xiě)出來(lái)，作為總結(jié)和備忘。有不對(duì)或理解錯(cuò)誤的地方，煩請(qǐng)指正。
原文鏈接：https://connect.unity.com/p/astar-xun-lu-yuan-li?app=true
歡迎大家戳上方鏈接，下載Unity官方app，和博主一起探討交流，在這里可以認(rèn)識(shí)很多有趣的小伙伴，還有在線答疑，更多實(shí)用干貨。
