A*尋路法 (AS3)

前一陣子想寫個遊戲來玩，所以難免一定會遇到在地圖上的人物怎麼找路走的問題，所以看了一下A*。
參考資料是這一篇：
http://www.lihuasoft.net/article/show.php?id=3523
原文是：
http://www.policyalmanac.org/games/aStarTutorial.htm

其實在上面的文章裡面已經把這個演算法說明得很清楚了，所以似乎不太需要再多做說明。
基本上的原則就是：
1. 每次抓取一個點，計算該點附近接鄰點的F值，這個F值是G(移動到該點要花費的移動點數)+H(該點到終點的垂直距離+水平距離總合)。
2. 將被計算的點放到一個open list陣列裡，並將那些點的父節點指向到目前的節點，然後將目前的節點放到close list裡(表示已經走過並計算完成)。
3. 從所有的open list裡抓取F值最小的一個節點出來，重覆1~2步驟，直到計算到終點為止。
4. 取得終點的父節點，再取得父節點的父節點(依此類推)，這些被取出的父節點list就是路徑。

我寫了一個AS3的版本，如下(點圖開啟swf)：

黑色框框是不可經過的點，點選空白的方框可以設定起始點，再點選另一個方框後就是設定終點，勾選DebugMode之後，一次按一下NextStep來觀看每次尋找路徑的計算過程。點New Map會隨機產生新地圖。
原始檔可在此下載：下載

心得：其實這版的A*似乎是很簡易版的，尋找出來的路徑有時在人類的眼中看起來似乎有點怪異(ex:會繞路)，但是基本上對於簡易遊戲來說應該已經很足夠。如果需要更符合自己遊戲的話可以依這個演算法的邏輯去加一些判斷或變數。