基礎(chǔ) | 圖與路徑查找----BFS
本系列為筆者初學(xué)c/c++和游戲AI開發(fā)的學(xué)習(xí)過程，算法為主，不涉及到具體的游戲開發(fā)軟件學(xué)習(xí)(如unity，虛幻4等),若有錯誤請在評論區(qū)留下批評意見。? ??
語言：c/c++ (11及以上)
平臺：macOS mojave
編輯器/編譯器：vs Code / g++
圖與路徑查找
四、BFS 廣度優(yōu)先搜索
4.1 廣度優(yōu)先搜索
? 廣度優(yōu)先搜索（Breadth First Search）是一種盲目搜索算法，圖形搜索算法。
簡單來講，BFS是從根節(jié)點開始，沿著樹的寬度遍歷樹的節(jié)點。如果所有節(jié)點均被訪問，則算法中止。廣度優(yōu)先搜索的實現(xiàn)一般采用open-closed表。
----維基百科
? 以上圖為例，我們先搜索節(jié)點1，再搜索節(jié)點1的全部子節(jié)點2、3、4，接著搜索節(jié)點2的全部子節(jié)點......以此類推，直到樹的全部節(jié)點都搜索過。
? 對于圖來說，廣度優(yōu)先搜索的過程也是一樣的。直到把一個節(jié)點的全部子節(jié)點遍歷完，才會進行下一個節(jié)點的遍歷。
4.2?算法邏輯步驟??
? 廣度優(yōu)先搜索的實現(xiàn)可歸納為以下幾個步驟：
首先將根節(jié)點放入隊列中
從隊列中取出第一個節(jié)點，并檢驗它是否為目標。
如果找到目標，則結(jié)束搜索并回傳結(jié)果。
否則將它所有尚未檢驗過的直接子節(jié)點加入隊列中。
隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜索的目標。結(jié)束搜索并回傳“找不到目標”。
重復(fù)步驟2。
4.3?算法代碼實現(xiàn)????
? 對應(yīng)在游戲場景中，整個分割后的地圖就是一個個節(jié)點組成的圖（數(shù)學(xué)上），每個節(jié)點的子節(jié)點就是該節(jié)點周圍的8個節(jié)點。
? 因此，與A*算法類似，我們用一個openList存儲未遍歷的節(jié)點，closeList存儲遍歷過的節(jié)點，并且返回closeList列表當做需要渲染的搜索路徑。
這里筆者犯了個錯誤，應(yīng)該先講BFS再講A*算法，因為A*算法是BFS算法的改良，很多概念應(yīng)該先理解了BFS才更好。
? 我們用指針來記錄從起始節(jié)點A到目標節(jié)點B的路徑節(jié)點，并返回一個列表：
? 在算法主體 findPath（）方法中實現(xiàn)BFS：
? 在代碼實現(xiàn)過程中，我們因為項目需求而將BFS算法的步驟做了簡單的拆解，不僅記錄全部的搜索過程，還記錄了一條從A到B的路徑。
? 當然，圖里的步驟 2.1 需要消耗大量的計算資源，后面如果有需要可以再進一步的優(yōu)化。
? 由于我們之前在Game類中編寫大地圖的時候，已經(jīng)為項目拓展留下了空間，因此只要在原來的基礎(chǔ)上加入新的模塊，用來獲取BFS算法返回的結(jié)果即可。
4.3 結(jié)果演示
??
參考
維基百科
相關(guān)代碼下載? ??https://github.com/linpeijie/GameToy
