圖的表示
學(xué)習(xí)算法的首要任務(wù)是理解數(shù)據(jù)。什么是輸入？什么是輸出？
- 輸入
- 輸出
- 權(quán)衡
對(duì)于游戲地圖有很多種圖的表示方法
圖的屬性
- 基于圖的尋徑算法需要知道當(dāng)前的位置，以及位置之間的相互連接關(guān)系竹宋。
事實(shí)上算法并不知道這些，它只知道位置之間的連接關(guān)系地技。 - 圖的布局并不是圖的一部分
- 路徑搜索算法并不知道網(wǎng)格圖的布局和屬性蜈七，它只知道網(wǎng)格之間的連接關(guān)系。
算法
關(guān)鍵思想: 跟蹤一個(gè)被稱為邊界的擴(kuò)展環(huán)
- 廣度優(yōu)先搜索
平等的探索所有可能的路徑 - Dijstra算法
優(yōu)先向低成本路徑探索莫矗，需要跟蹤移動(dòng)的成本（move cost）
根據(jù)移動(dòng)成本去選擇下一個(gè)位置 - A算法
A是對(duì)Dijkstra算法的修改飒硅，針對(duì)單個(gè)目標(biāo)進(jìn)行優(yōu)化
參考
A*算法介紹：https://www.redblobgames.com/pathfinding/a-star/introduction.html
