1、A* 演算法簡介 (A* Algorithm Brief)2004/12/20 09:44 A* (A-Star) 演算法是在 Game 中通常用來解決 最短路徑(Shortest Path)問題的一種演算法. 相對於另一個知名的 Dijkstra 演算法來說, Dijkstra 演算法雖然可以保證找到一條最短的路徑, 但不如 A* 演算法這樣簡捷快速. 同時, Dijkstra 的搜尋深度在某些情形下也容易顯得不適用. A* 演算法便是為了這些情形而出現的, 可以算是 Dijkstra 演算法的一種改良.底下用幾張圖來表現 Dijkstra 演算法與 A* 演算法的不同:Dijkstra 演
2、算法 A* 演算法無障礙有障礙(圖片取自 Amits Thoughts on Path-Finding and A-Star)從以上的比較圖可以看出, A* 演算法的搜尋深度雖然不如 Dijkstra 演算法, 但其結果仍然是很令人滿意的. 為什麼 A* 演算法可以達到這樣的結果呢? 這是因為 A* 演算法採用了一套特殊的啟發式評價(Heuristic Estimate)公式將許多明顯為壞的路徑排除考慮, 進而快速計算出一條滿意的路徑 .公式如下:f(n) = g(n) + h(n)g(n): 從啟始點到目前節點的距離h(n): 預測目前節點到結束點的距離(此為 A* 演算法的主要評價公式)f
3、(n): 目前結點的評價分數其中, h(n) 主導著 A* 演算法的表現方式. 有以下幾種情形:1. h(n)=0: A* 演算法這時等同 Dijkstra 演算法, 並且保證能找到最短路徑2. h(n)目前節點到結束點的距離: 不保證能找到最短路徑, 但計算比較快5. h(n)與 g(n)高度相關: A* 演算法此時成為 BFS (Best-First Search)A* 演算法的虛擬碼如下 : Add START to OPEN listwhile OPEN not emptyget node n from OPEN that has the lowest f(n)if n is GOAL
4、 then return pathmove n to CLOSEDfor each n = CanMove(n, direction)g(n) = g(n) + 1calculate h(n)if n in OPEN list and new n is not better, continueif n in CLOSED list and new n is not better, continueremove any n from OPEN and CLOSEDadd n as ns parentadd n to OPENend forend whileif we get to here, t
5、hen there is No Solution以上虛擬碼適用於一般遊戲中方格圖(Grid Map)的情形. 當要在真實地圖的路網(Road Map)上使用 A* 演算法時, g(n)與 h(n)的計算方式便會有所不同.相關參考資料:網頁:Amits Thoughts on Path-Finding and A-StarCreating an A* algorithm Robot for QUT SoKoBan維基百科:Shortest Path ProblemA* Search AlgorithmDijkstra Algorithm書籍:Core Techniques and Algorithms in Game Programming (英文)大師談遊戲程式設計：核心技術與演算法 (中文)
