C# 實現 A* 算法 (1) — 節點模型與基礎結構

背景：遊戲尋路與 A* 算法

遊戲地圖常抽象為單元格矩陣，傳統圖論最短路徑演算法 (如 Dijkstra) 不再最適合。A* 算法結合實際代價 G 與啟發式預估 H，能高效找到最優路徑 (若存在)。

圖示：3×3 單元格微型地圖，實際遊戲地圖規模更大。

AStarNode：搜尋過程中的節點狀態

public class AStarNode
{
    public AStarNode(Point loc, AStarNode previous, int costG, int costH)
    {
        Location = loc;
        PreviousNode = previous;
        _costG = costG;
        _costH = costH;
    }

    public Point Location { get; }           // X=Column, Y=Line
    public AStarNode PreviousNode { get; }   // 父節點，用於回溯路徑

    public int CostF => _costG + _costH;     // 總估價 F = G + H
    private int _costG;
    public int CostG { get => _costG; }      // 從起點到此節點實際代價

    private int _costH;
    public int CostH { get => _costH; }      // 從此節點到終點啟發式預估

    public void ResetPreviousNode(AStarNode previous, int costG)
    {
        PreviousNode = previous;
        _costG = costG;
    }

    public override string ToString() => Location.ToString();
}

設計重點

• Location：單元格座標，X=欄索引，Y=列索引。
• PreviousNode：形成鏈結串列，終點回溯即得完整路徑。
• CostG / CostH / CostF：核心評分三元組，F = G + H。
• ResetPreviousNode：發現更優路徑時更新父節點與 G 值。

後續文章將介紹 RoutePlanData、CompassDirections、GeometryHelper、ICostGetter 等輔助結構，最後呈現核心遞迴搜尋邏輯。