WPF/Silverlight 遊戲開發教程 (7)：傳說中的 A* 尋路算法 — 曼哈頓啟發式、矩陣構建、動態終點尋路

地圖引擎雙核心：呈現與物件邏輯

• 呈現：地圖切割、合成、渲染方式
• 物件邏輯：尋路、遮罩、傳送點、碰撞

本章聚焦尋路，引入經典 A* (A-Star) 算法及其變體。

A* 算法變體與選型

經橫向評測，曼哈頓啟發式在複雜分支迷宮中耗時最短（3ms 級），本教程採用之。

核心資料結構

Rectangle rect;
IPathFinder PathFinder;
byte[,] Matrix = new byte[1024, 1024]; // 邏輯網格：1=通行, 0=阻擋
int GridSize = 20; // 單格像素大小
System.Drawing.Point Start, End; // 起點/終點 (格子座標)

GridSize 設計意義

視窗座標 (像素) ↔ 遊戲邏輯座標 (格子) 的縮放因子。
視窗 (800,600) → 邏輯 (40,30) 當 GridSize=20。
所有邏輯運算（A*、碰撞、AI）在格子座標系進行，渲染時乘回 GridSize。

矩陣初始化與障礙物構建

private void ResetMatrix()
{
    for (int y = 0; y < Matrix.GetUpperBound(1); y++)
        for (int x = 0; x < Matrix.GetUpperBound(0); x++)
            Matrix[x, y] = 1; // 預設全通行

    // 構建水平障礙牆 y=12, x=0~17
    for (int i = 0; i < 18; i++)
    {
        Matrix[i, 12] = 0;
        rect = new Rectangle { Fill = Brushes.Red, Width = GridSize, Height = GridSize };
        Carrier.Children.Add(rect);
        Canvas.SetLeft(rect, i * GridSize);
        Canvas.SetTop(rect, 12 * GridSize);
    }
    // 可繼續添加其他障礙物...
    Start = new System.Drawing.Point(1, 1);
}

滑鼠動態指定終點並尋路

private void Carrier_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
{
    Point p = e.GetPosition(Carrier);
    int x = (int)p.X / GridSize;
    int y = (int)p.Y / GridSize;
    End = new System.Drawing.Point(x, y);

    PathFinder = new PathFinderFast(Matrix);
    PathFinder.Formula = HeuristicFormula.Manhattan;
    PathFinder.SearchLimit = 2000;

    List path = PathFinder.FindPath(Start, End);

    if (path == null) { MessageBox.Show("路徑不存在！"); return; }

    string output = "";
    for (int i = path.Count - 1; i >= 0; i--)
    {
        output += $"({path[i].X},{path[i].Y}) ";
        rect = new Rectangle { Fill = Brushes.Green, Width = GridSize, Height = GridSize };
        Carrier.Children.Add(rect);
        Canvas.SetLeft(rect, path[i].X * GridSize);
        Canvas.SetTop(rect, path[i].Y * GridSize);
    }
    MessageBox.Show("路徑座標：" + output);
}

執行結果驗證

• 綠色方塊標記出的路徑完美繞開紅色障礙牆，到達滑鼠點擊處。
• 路徑座標列表輸出可供除錯驗證。
• 若終點在障礙物上或被封閉，正確提示「路徑不存在」。

教學重點總結

1. 座標系分離：視窗像素座標僅用於渲染與輸入，邏輯運算全在格子座標系。
2. GridSize 為橋樑：所有轉換統一除以/乘以 GridSize，修改單一常數即可調整網格精度。
3. 第三方元件封裝：PathFinderFast 隔離演算法複雜度，專注遊戲邏輯整合。
4. 動態終點：滑鼠點擊即時轉換為格子座標觸發尋路，體驗即時互動。

下章預告

下一章將動態生成關鍵幀動畫，讓角色沿 A* 路徑節點平滑移動，而非瞬間傳送，並引入平滑銜接、軌跡視覺化等實戰技巧。

1. 上一篇文章： WPF/Silverlight 遊戲開發教程 (8)：完美實現 A* 尋路動態動畫 — PathFinderFast、關鍵幀平滑銜接、軌跡視覺化
2. 下一篇文章： WPF/Silverlight 遊戲開發教程 (6)：完美移動 — 幀動畫與位移動畫融合、三大缺憾與解決路徑

關於C#

ASP.NET 圖表繪製核心技術：GDI+ 動態生成圖片實現數據視覺化

ASP.NET 無法直接使用傳統 ActiveX 圖表元件（

C# 設計模式深度解析：裝飾模式動態擴充物件功能的藝術

前言 裝飾模式 是結構型設計模式中最優雅的模式之一，核心意圖

Visual Studio 2010 IntelliSense 程式碼自動完成失效？完整修復方案

IntelliSense (智慧感知) 是 Visual S

Head First C# 中文版：認識 SQL 資料庫與查詢語言（第 19 頁）

當你告訴 IDE 專案加入新資料庫時，IDE 會自動建立一個