AStar路徑演算法初探

A*是著名的尋路演算法,在即時戰略遊戲很常見,主要是用來找出最短路徑,筆者參考Patrick Lester的A* Pathfinding for Beginners一文,試著用Actionscript3實作A*,為了加快效能,全部改用Vector取代Array,所以以下範例請用Flash Player10以上版本觀看。

先簡單說明一下A*的邏輯,A*是藉由評分制來取得最短路徑,有三個參考值F、H、G,F是H跟G的總合,最後拿來參考用,而G是由起點到目前位置所需的移動耗費,也就是移動距離參考,而H比較特殊,這是一種啟發式的預測,估算目前位置到終點所需的移動量,H有很多種算法,這次的範例是採用最簡單的Manhattan演算法,直線且不考慮障礙物

第一個範例把評分列出,黃色區塊為算出的最短路徑,而淺藍色區塊為有運算過的節點,按下空白鍵可切換四方向及八方向移動

2009-10-05_011918.png

觀看範例

套用PV3D,這樣感覺就比較像遊戲了,如果加上移動限制及回合,就能做出SLG戰略遊戲的效果,下次再寫個範例試試

2009-10-05_011951.png

觀看範例

原始檔下載

AStar類別

2 意見 :: AStar路徑演算法初探

  1. 在嘗試執行您分享的原始檔時,找不到下列的as檔.

    import __AS3__.vec.Vector;

  2. 我有用到Flash10的Vector,在Flex需把Flash版本設定10以上