C# 開發 WPF/Silverlight 動畫與遊戲系列教程（七）傳說中的 A* 尋路算法（一）—— 算法選型與核心原理

地圖引擎兩大核心

1. 地圖實現（切割、合成、呈現）
2. 地圖物件實現（尋路、遮罩、傳送點）

為激發興趣，先講尋路。經典 A* 為尋路思維集大成者，衍生算法眾多：曼哈頓、對角線、歐幾里得、最大取值等，效能與路徑品質各異。參考國外高手工具（CodeGuru 專頁），橫向比較後發現曼哈頓啟發式算法速度最快，即便九曲十八彎迷宮也能 3ms 內找到最佳路徑。

測試截圖：棕色=障礙物，左上起點，中間紅框終點，藍色=路徑。右下角耗時 3ms。

入門資源推薦

中文翻譯入門文（需耐心閱讀，收穫巨大）：Gameres 論壇

核心原理簡述

從起點發散檢查周圍 8 點，經條件篩選最優點，以此點為新起點循環，最終所有起點集合即路徑。看似不難？動手嘗試！可參考上述開源專案源碼實現自己的 A*。