基礎(chǔ) | 圖與路徑查找----A*算法
本系列為筆者初學(xué)c/c++和游戲AI開發(fā)的學(xué)習(xí)過程，算法為主，不涉及到具體的游戲開發(fā)軟件學(xué)習(xí)(如unity，虛幻4等),若有錯(cuò)誤請(qǐng)?jiān)谠u(píng)論區(qū)留下批評(píng)意見。?
? 語言：c/c++ (11及以上)
平臺(tái)：macOS mojave
編輯器/編譯器：vs Code / g++
圖與路徑查找
三、A*算法
? Patrick Lester在2005年的一篇論文中詳細(xì)講解了A*算法的原理，這篇論文應(yīng)該算是該算法最好的講解了，所以筆者在這里也就不再贅述，直接結(jié)合工程實(shí)現(xiàn)來講解。
? 讀者也可以直接到到文章出處看原文：
https://www.cnblogs.com/alex-tech/archive/2012/03/09/2387908.html? ?論文翻譯
http://csis.pace.edu/~benjamin/teaching/cs627/webfiles/Astar.pdf? ? ? ? ? 論文地址
3.1 搜索區(qū)域??
? 在游戲中，我們通常會(huì)用方格或者多邊形來分隔地圖，這些格子表示一個(gè)個(gè)不同的區(qū)域，可以放置資源，或者讓角色通過。
? 全部的方格便構(gòu)成了一個(gè)搜索區(qū)域，尋路算法在這個(gè)簡(jiǎn)化的區(qū)域內(nèi)去尋找路徑。路徑被描述為從A到B經(jīng)過的方塊的集合。
? 這些方格在數(shù)學(xué)模型中也被稱為節(jié)點(diǎn)。
? 如下圖，假設(shè)我們想要從綠色的方塊移動(dòng)到紅色的方塊，中間隔了一堵藍(lán)色的墻：??
??3.2 開始搜索
? 簡(jiǎn)單來講，A*算法也是啟發(fā)式算法的一種，通過不斷向外擴(kuò)展搜索未接觸過的節(jié)點(diǎn)，來抵達(dá)目標(biāo)。
步驟一：
? 做如下開始搜索：
從點(diǎn)A開始，并且把它作為待處理點(diǎn)存入一個(gè)“開啟列表”。OpenList存儲(chǔ)待搜索的方格。
尋找起點(diǎn)周圍所有可到達(dá)或者可通過的方格，跳過有墻，水，或其他無法通過地形的方格，并把它們放入開啟列表。
從開啟列表中刪除點(diǎn)A，把它加入到一個(gè)“關(guān)閉列表”，ClosedList列表中保存所有不需要再次檢查的方格。
步驟二：
??依據(jù)“路徑評(píng)分F”從“開啟列表”中取出一個(gè)方格。我們選取的是F值最小的那個(gè)方格。
? 所謂的F是如下公式：
F = G + H
? 其中：
G = 從起點(diǎn)A，沿著產(chǎn)生的路徑，移動(dòng)到網(wǎng)格上指定方格的移動(dòng)耗費(fèi)。
H =?從網(wǎng)格上那個(gè)方格移動(dòng)到終點(diǎn)B的預(yù)估移動(dòng)耗費(fèi)。
當(dāng)前方格的 G =?上一個(gè)方格的G + 上一個(gè)方格到當(dāng)前方格的移動(dòng)耗費(fèi)，通常我們令水平或垂直移動(dòng)的耗費(fèi)為10，對(duì)角線的耗費(fèi)為14。
當(dāng)前方格的 H = 當(dāng)前方格到目標(biāo)方格的曼哈頓距離，從當(dāng)前格到目的格之間水平和垂直的方格的數(shù)量總和，忽略對(duì)角線方向，忽略一切障礙物。
經(jīng)過這個(gè)步驟，你應(yīng)該得到如下圖所示的結(jié)果：
? 從圖上我們可以看到，F(xiàn)值最小的是綠色方格右邊那個(gè)方格，F(xiàn) = 40，G = 10， H = 30
步驟三：
? 對(duì)選中的方格，我們做以下操作：
把它從開啟列表中刪除，然后添加到關(guān)閉列表中。
檢查所有相鄰格子。跳過那些已經(jīng)在關(guān)閉列表中的或者不可通過的(有墻，水的地形，或者其他無法通過的地形)，把他們添加進(jìn)開啟列表，如果他們還不在里面的話。把選中的方格作為新的方格的父節(jié)點(diǎn)。
如果某個(gè)相鄰格已經(jīng)在開啟列表里了，檢查現(xiàn)在的這條路徑是否更好。如果不是，那就什么都不做。如果新的G值更低，那就把相鄰方格的父節(jié)點(diǎn)改為目前選中的方格。最后，重新計(jì)算F和G的值。
接著，檢查開啟列表，選擇其中F值最低的那個(gè)格子。如果有F值相同的點(diǎn)，隨便選哪個(gè)都可以。
最后，重復(fù)以上幾個(gè)小步驟，直到找到目標(biāo)方格即可。
3.3 A*算法總結(jié)
? 整個(gè)A*算法可以歸納成以下的邏輯步驟：
把起始格添加到開啟列表。
重復(fù)如下的工作：
尋找開啟列表中F值最低的格子。我們稱它為當(dāng)前格。
把它切換到關(guān)閉列表。
對(duì)其相鄰的8格中的每一個(gè)？
如果它不可通過或者已經(jīng)在關(guān)閉列表中，略過它。反之如下。
如果它不在開啟列表中，把它添加進(jìn)去。把當(dāng)前格作為這一格的父節(jié)點(diǎn)。記錄這一格的F,G,和H值。
如果它已經(jīng)在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一格的父節(jié)點(diǎn)改成當(dāng)前格，并且重新計(jì)算這一格的G和F值。如果你保持你的開啟列表按F值排序，改變之后你可能需要重新對(duì)開啟列表排序。
停止，當(dāng)你
把目標(biāo)格添加進(jìn)了關(guān)閉列表(注解)，這時(shí)候路徑被找到，或者
沒有找到目標(biāo)格，開啟列表已經(jīng)空了。這時(shí)候，路徑不存在。
?? 3.?保存路徑。從目標(biāo)格開始，沿著每一格的父節(jié)點(diǎn)移動(dòng)直到回到起始格。這就是你的路徑。
3.3 A*算法實(shí)現(xiàn)
? 因?yàn)槲覀兪窃诹硪粋€(gè)類中調(diào)用A*算法來計(jì)算路徑，所以我們額外需要：
setMaze（）：每次計(jì)算的時(shí)候都要重置地圖
GetPath（）：返回計(jì)算出來的路徑列表，并將其坐標(biāo)轉(zhuǎn)換為世界坐標(biāo)。
getSearchPath（）：返回所有搜索過的方格，包括被丟棄不用的那些方格，其實(shí)就是? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?closeList。
? 因?yàn)閷?duì)于計(jì)算機(jī)來說，二維數(shù)組是最方便的計(jì)算方式，所以我們會(huì)將世界地圖上的方格坐標(biāo)轉(zhuǎn)換為二維數(shù)組中相對(duì)應(yīng)的坐標(biāo)。
? 智能指針Point和世界地圖上的方格一一對(duì)應(yīng)，保存著一個(gè)父節(jié)點(diǎn)和子節(jié)點(diǎn)。
? A*算法的主體實(shí)現(xiàn)起來十分的簡(jiǎn)單，這也是這個(gè)算法如此流行的原因，簡(jiǎn)單而又強(qiáng)大，不需要太復(fù)雜的修改就能適應(yīng)多種場(chǎng)合。
? 其他細(xì)節(jié)可以到倉庫中下載代碼查看，直接閱讀代碼是最好的學(xué)習(xí)方式，更能加深理解。
? 如果讀者已經(jīng)正確安裝好了SFML和其他工具，只需要make就可以直接運(yùn)行了。
3.3 A*算法演示
? 視頻中，黃色是起始節(jié)點(diǎn)，紅色是目標(biāo)節(jié)點(diǎn)，黑色為墻壁，綠色為全部查找節(jié)點(diǎn)，藍(lán)色為查找路徑：
