A* 尋路演算法入門教學 (附 C++/Blitz Basic 範例)

核心概念

• 搜尋區域網格化：將地圖劃分為方格節點，標記可通行/不可通行。
• 開啟清單：待檢查節點 (起點優先放入)。
• 關閉清單：已檢查完畢節點。
• 父節點：記錄路徑回溯關鍵。

演算法流程

1. 將起點加入開啟清單。
2. 檢查相鄰可通行格，加入開啟清單，設定父節點為當前節點。
3. 將當前節點移至關閉清單。
4. 從開啟清單挑選 F = G + H 最小 的節點作為新當前節點：
       G = 從起點移動到該節點的實際代價。
       H = 從該節點到終點的估算代價 (啟發式，如曼哈頓距離)。
5. 重複 2-4 直到終點被加入開啟清單 (找到路徑) 或開啟清單為空 (無路徑)。
6. 從終點沿父節點回溯至起點，得到最短路徑。

關鍵公式

F = G + H

啟發式函式 H 必須不可高估實際代價 (admissible) 以保證最優解。

範例程式

原文提供下載連結，包含 C++ 與 Blitz Basic 完整原始碼及可執行檔。文章以幽默淺顯筆者風格逐步推導，適合初學者建立直觀理解。