游戲算法實踐——A星尋路

來自： https://segmentfault.com/a/1190000004503119

先展示效果圖：

如圖中亮綠色點為起點，藍點為終點，白色為墻體不可行走。黃色點區域為被試探到的位置，綠色的路徑為最后的最短路徑。其中這里移動規則是只能上下左右移動。

關于A星算法，大家可以去google。這里展一下本項目A星算法的部分（思路）：

+ 創建一個open集合，一個close集合
+ 把起點加入close集合，并把它設為Current節點
+ 重復如下過程：
  + 查找Current節點的相鄰節點（上下左右）
  + 如果節點不是墻也不在close集合并且也不在open集合的，計算G值H值，設置Parent為Current節點，然后加入到open集合
  + 如果已經加入了open集合，那么查找一下是不是從Current節點到這個節點G值更小，如果是那么改變這個節點的G值為更小值，Parent指針指向Current節點
  + 如果節點是終點，那么跳出循環
  + 遍歷open集合，查找F值最小的節點（F=G+H）
  + 如果找到了，把這個節點移到close集合
  + 如果沒有找到，并且open表又為空了，那么表示找不到路徑了，跳出循環
+ 循環后如果沒找不到路徑，那么結束
+ 如果找到路徑，那么從終點開始，在close表中通過parent指針來尋找路徑，直到起點

大家可以通過github來參考具體代碼。

工程實現了編輯地圖，保存地圖（為下次打開使用）功能。工程使用cocos2d-x3.x引擎。