WPF/Silverlight 遊戲開發教程 (8)：完美實現 A* 尋路動態動畫 — PathFinderFast、關鍵幀平滑銜接、軌跡視覺化

前置準備：角色與障礙物

Ellipse player = new Ellipse(); // 簡易圓形代表主角
private void InitPlayer()
{
    player.Fill = Brushes.Blue;
    player.Width = player.Height = GridSize; // 20x20
    Carrier.Children.Add(player);
    Canvas.SetLeft(player, GridSize); // (1,1)
    Canvas.SetTop(player, 5 * GridSize);
}

障礙物矩陣 Matrix[1024,1024] 初始化為 1（通行），再手動設置部分為 0（阻擋），並同步建立紅色 Rectangle 視覺化。

引用第三方 A* 元件：PathFinderFast

使用 CodeGuru 開源 PathFinderFast（命名空間 QX.Game.PathFinder），支援多種啟發式：

• HeuristicFormula.Manhattan：曼哈頓距離，速度最快，適合 4/8 方向網格
• HeuristicFormula.Euclidean：歐幾里得距離
• HeuristicFormula.Diagonal：對角線啟發式

測試顯示曼哈頓在複雜迷宮中 3ms 內出路，效能卓越。

滑鼠點擊觸發動態 A* 尋路與動畫生成

private void Carrier_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
{
    Point p = e.GetPosition(Carrier);

    // 起點：角色當前格子座標
    int sx = (int)Canvas.GetLeft(player) / GridSize;
    int sy = (int)Canvas.GetTop(player) / GridSize;
    Start = new System.Drawing.Point(sx, sy);

    // 終點：點擊處格子座標
    int ex = (int)p.X / GridSize;
    int ey = (int)p.Y / GridSize;
    End = new System.Drawing.Point(ex, ey);

    // 執行尋路
    var finder = new PathFinderFast(Matrix);
    finder.Formula = HeuristicFormula.Manhattan;
    finder.SearchLimit = 2000;
    List path = finder.FindPath(Start, End);

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

    // 反轉路徑：A* 回傳終點→起點，需正向起點→終點
    Point[] frames = new Point[path.Count];
    for (int i = path.Count - 1; i >= 0; i--)
        frames[path.Count - 1 - i] = new Point(path[i].X * GridSize, path[i].Y * GridSize);

    // 建立 Storyboard 關鍵幀動畫
    var sb = new Storyboard();
    int cost = 100; // 每格 100ms

    var kfX = new DoubleAnimationUsingKeyFrames();
    kfX.Duration = new Duration(TimeSpan.FromMilliseconds(path.Count * cost));
    Storyboard.SetTarget(kfX, player);
    Storyboard.SetTargetProperty(kfX, new PropertyPath("(Canvas.Left)"));

    var kfY = new DoubleAnimationUsingKeyFrames();
    kfY.Duration = new Duration(TimeSpan.FromMilliseconds(path.Count * cost));
    Storyboard.SetTarget(kfY, player);
    Storyboard.SetTargetProperty(kfY, new PropertyPath("(Canvas.Top)"));

    for (int i = 0; i < frames.Length; i++)
    {
        var fx = new LinearDoubleKeyFrame
        {
            Value = i == 0 ? Canvas.GetLeft(player) : frames[i].X, // 平滑銜接
            KeyTime = KeyTime.FromTimeSpan(TimeSpan.FromMilliseconds(cost * i))
        };
        kfX.KeyFrames.Add(fx);

        var fy = new LinearDoubleKeyFrame
        {
            Value = i == 0 ? Canvas.GetTop(player) : frames[i].Y,
            KeyTime = KeyTime.FromTimeSpan(TimeSpan.FromMilliseconds(cost * i))
        };
        kfY.KeyFrames.Add(fy);
    }

    sb.Children.Add(kfX); sb.Children.Add(kfY);
    if (!Resources.Contains("storyboard")) Resources.Add("storyboard", sb);
    sb.Begin();

    // 視覺化軌跡：白點標記每個路徑節點
    for (int i = path.Count - 1; i >= 0; i--)
    {
        var dot = new Rectangle { Fill = Brushes.Snow, Width = 5, Height = 5 };
        Carrier.Children.Add(dot);
        Canvas.SetLeft(dot, path[i].X * GridSize);
        Canvas.SetTop(dot, path[i].Y * GridSize);
    }
}

關鍵技術點深度解析

1. 路徑反轉與關鍵幀陣列建構

PathFinderNode 列表為倒序（終點→起點），遊戲動畫需正序。反轉時同步乘以 GridSize 轉為像素座標。

2. 關鍵幀動畫 vs 簡單 DoubleAnimation

DoubleAnimationUsingKeyFrames + LinearDoubleKeyFrame 可精確控制每個網格節點的到達時間，實現「格子級勻速移動」。單純 DoubleAnimation 僅能直線插值，無法繞彎。

3. 平滑銜接邏輯：i == 0 ? 當前位置 : 目標節點

若角色正在移動中途被重新指派目標，新動畫第 0 幀必須從當前像素位置啟動，而非下一個網格中心。否則會產生瞬間「傳送跳動」。此技巧在後續章節（牽引式地圖、斜度地圖）反覆復用。

4. GridSize 與速度統一化的取捨

對角線距離 (1.414×) 大於直線 (1×)，若嚴格依物理距離分配時間，斜向會明顯變慢。教程採用統一每格固定耗時 (cost=100ms)，GridSize=20 時視覺差異可忽略，大幅簡化邏輯並提升效能。若 GridSize > 50 則需引入距離權重計算。