| Dijkstra 演算法 | A* 演算法 |
| 無障礙 |
 |  |
| 有障礙 |
 |  |
(圖片取自 Amit's Thoughts on Path-Finding and A-Star)
從以上的比較圖可以看出, A* 演算法的搜尋深度雖然不如 Dijkstra演算法, 但其結果仍然是很令人滿意的. 為什麼A* 演算法可以達到這樣的結果呢? 這是因為A* 演算法採用了一套特殊的啟發式評價(Heuristic Estimate)公式將許多明顯為壞的路徑排除考慮, 進而快速計算出一條滿意的路徑.
公式如下:
f(n) = g(n) + h(n)
h(n): 預測目前節點到結束點的距離(此為 A* 演算法的主要評價公式)
f(n): 目前結點的評價分數
其中, h(n) 主導著A* 演算法的表現方式. 有以下幾種情形:
1. h(n)=0: A* 演算法這時等同 Dijkstra演算法, 並且保證能找到最短路徑
2. h(n) <目前節點到結束點的距離: A* 演算法保證找到最短路徑, h(n)越小, 搜尋深度越深
3. h(n)=目前節點到結束點的距離: A* 演算法僅會尋找最佳路徑, 並且能快速找到結果
4. h(n)>目前節點到結束點的距離: 不保證能找到最短路徑, 但計算比較快
5. h(n)與g(n)高度相關: A* 演算法此時成為 BFS (Best-First Search)
A* 演算法的虛擬碼如下:Add START to OPEN list
while OPEN not empty
get node n from OPEN that has the lowest f(n)
if n is GOAL then return path
move n to CLOSED
for each n' = CanMove(n, direction)
g(n') = g(n) + 1
calculate h(n')
if n' in OPEN list and new n' is not better, continue
if n' in CLOSED list and new n' is not better, continue
remove any n' from OPEN and CLOSED
add n as n's parent
add n' to OPEN
end for
end while
if we get to here, then there is No Solution
以上虛擬碼適用於一般遊戲中方格圖(Grid Map)的情形. 當要在真實地圖的路網(Road Map)上使用A* 演算法時, g(n)與h(n)的計算方式便會有所不同.
相關參考資料:
網頁:
Amit's Thoughts on Path-Finding and A-Star
Creating an A* algorithm Robot for QUT SoKoBan
維基百科:
Shortest Path Problem
A* Search Algorithm
Dijkstra Algorithm
書籍:
Core Techniques and Algorithms in Game Programming (英文)
大師談遊戲程式設計：核心技術與演算法 (中文)
