基礎 | 圖與路徑查找----地圖分割
本系列為筆者初學c/c++和游戲AI開發(fā)的學習過程，算法為主，不涉及到具體的游戲開發(fā)軟件學習(如unity，虛幻4等),若有錯誤請在評論區(qū)留下批評意見。
語言：c/c++ (11及以上)
平臺：macOS mojave
編輯器/編譯器：vs Code / g++
圖與路徑查找
二、地圖
2.1 地圖
??在做路徑查找之前，我們首先需要對地圖進行劃分，也就是將地圖分割成便于計算的一系列節(jié)點。
? 通常地圖分割的方法有兩種：Grid（或Tile，方格）和Navmesh（導航網格）。
2.1.1 Grid 方格：
? Grid指的是將地圖離散化一個個相互獨立的方格，這樣每個方格代表了地圖上的一種資源，可能是道路、山體或者樹木等。
? 游戲中的角色根據每個方格屬性的不同，可以自動判斷是否可以通過這個方格前往下一個。
? 繪制方格地圖是相對比較簡單的，在我們項目中，只需要用一個二維數組就可以表達出一個地圖的方格。
? 如上圖，Tile類是我們自定義的方格類，存儲方格的位置、大小和標簽ID。
? 在地圖里，高height對應矩陣的行y，寬width對應列x。為了便于渲染，我們用一個動態(tài)數組tiles來存儲這些方格。
? 可見只要知道地圖的寬高，和方格的大小，就能夠定義方格在世界坐標中的中心位置，并將其表示為數學模型中的節(jié)點。
? 方格地圖的優(yōu)點在于簡單，且跟A*算法十分的契合。缺點是角色移動會不夠連續(xù)自然，十分僵硬，且在地圖大、路徑長的情況下十分耗費計算資源。
2.1.1 Navmesh 導航網格：
? 導航網格是一種用于在復雜空間中導航尋路、標記哪些地方可行走的多邊形網格數據結構? 。
? 一個導航網格是由多個凸多邊形（Convex Polygon, Poly Mesh）組成的。
? 這里主要應用了凸多邊形的性質：在凸多邊形邊上的一個點走到另外一點，不管怎么走都不會走出這個多邊形。（https://mathworld.wolfram.com/ConvexPolygon.html）
? 因此，我們在游戲地圖上，只要在空地上繪制好凸多邊形，角色在這個凸多邊形上無論怎么走都不會碰到障礙物。
? 導航網格的構建相對更麻煩，筆者在這個項目中并未采用這種方法，因此只簡單介紹一下在2D地圖上如何繪制一個Navmesh。
連接地圖的邊界點和障礙物的邊界點，??將地圖分割成多個三角形區(qū)域。
清除多余的三角形區(qū)域。
在網格的每條邊上放置節(jié)點（路徑點），將路徑點連接起來，就形成了導航網格。
? Navmesh導航網格的優(yōu)點是減少節(jié)點和搜尋的計算量，使角色移動更自然。缺點是計算三角形和合并相鄰的凸多邊形需要很大的計算量，且實現十分復雜。
2.2 用SFML繪制方格地圖
? 為了便于地圖分割，我們將地圖的大小設置為 1280x720，方格大小40x40，且地圖上有一個起始節(jié)點和一個目標節(jié)點，表示算法的開始和結束。
? 黑色方格是墻壁，表示無法通過的節(jié)點。
2.2.1?Tile類
??我們用Tile類來表示一個方格，相當于每個tile是一個貼圖。在SFML中，貼圖是可以直接在窗口中繪制的子類，需要繼承sf::Drawble類和sf::Transformable類。
??Tile類存儲方格在地圖上的基礎信息，包括位置、顏色和ID（方格標簽）。
? 其中有幾個比較特殊的類：??
RectangleShape：特殊表示的矩形，用來繪制方格，可隨意變換屬性。
IntRect：操縱2D軸對齊的矩形的類，輸入為方格左上角頂點的坐標和方格寬高，轉化為? ? ? ? ? ? ? ? ?標準格式。
draw()：該虛函數用來繪制圖形，按照官方的方法寫就好
2.2?Game類
??我們的項目主體是一個Game類，在這個類中定義地圖（世界）擁有的一些功能。
handleInput（）：處理鍵盤輸入。
S：source，繪制起始節(jié)點
T：target，繪制目標節(jié)點
W：wall，繪制墻壁節(jié)點
R：run，啟動路徑查找算法
C：clear，清除內存，重置地圖
A：A*算法，選擇A*算法作為路徑查找算法
B：BFS算法，選擇BFS算法作為路徑查找算法
render（）：渲染，由于我們需要展示路徑查找的過程，因此分開渲染路徑節(jié)點。通過延遲算法來控制渲染時間。
? 整個項目的邏輯設計：
啟動程序，初始化地圖。
鍵盤輸入R，選擇路徑查找算法。
按住S鍵或T鍵，鼠標點擊地圖，重置起始節(jié)點和目標節(jié)點的位置。
按住W鍵，鼠標點擊地圖，在地圖上繪制墻壁節(jié)點。
按R鍵，啟動路徑查找算法。
按C鍵，清除內存，重置地圖。
? 到這里，就能夠繪制出方格地圖，接受鍵盤輸入，選擇路徑查找算法，并運行算法展示查找路徑。
? 更詳細的工程實現，讀者可以下載代碼閱讀，筆者一直相信閱讀代碼是最好的學習方式。
2.3 結果展示
參考：
《游戲人工智能編程案例精粹》
https://en.wikipedia.org/wiki/Navigation_mesh#Advantages? Navmesh介紹
https://mathworld.wolfram.com/ConvexPolygon.html? ? ? ? ? ? 凸多邊形數學定義
https://www.sfml-dev.org/tutorials/2.5/
相關代碼下載? ??https://github.com/linpeijie/GameToy
