C# 實作走迷宮演算法（一）：廣義樹與堆疊尋路

前言

走迷宮是經典資料結構練習。本文使用 C# 實作廣義樹 表示迷宮拓撲，配合堆疊 進行深度優先回溯搜尋，並提供圖形化繪製與逐步演示功能。

核心類別設計

1. 座標資訊類別 (CCoor)

public class CCoor
{
    public Point CurrentPoint { get; set; } // 當前位置
    public Stack WayPath { get; set; }      // 可移動方向堆疊

    public CCoor(Point p, Stack way)
    {
        CurrentPoint = p;
        WayPath = way;
    }
}

2. 迷宮主類別 (CMaze)

public class CMaze
{
    private bool[,] _map;           // true=通路, false=牆壁
    private Stack _pathStack;       // 走過路徑堆疊
    private Point _start, _exit;    // 入口/出口
    private Point _drawOrigin;      // 繪圖起點
    private Size _cellSize;         // 格子大小
    private int _stepCount;

    public CMaze(bool[,] map, Point start, Point exit)
    {
        _map = map; _start = start; _exit = exit;
        _pathStack = new Stack();
        _cellSize = new Size(50, 50);
        _stepCount = 0;
        InitPath();
    }

    private void InitPath()
    {
        Stack ways = Test(_start, _start);
        _pathStack.Push(new CCoor(_start, ways));
        _stepCount = 1;
    }

    // 嘗試走一步，回傳 0=繼續, 1=到達出口
    public int Step()
    {
        CCoor current = (CCoor)_pathStack.Peek();
        if (current.CurrentPoint == _exit) return 1;

        if (current.WayPath.Count == 0) // 死胡同，回溯
        {
            _pathStack.Pop();
            return 0;
        }

        Point next = (Point)current.WayPath.Pop();
        if (next == _exit)
        {
            _pathStack.Push(new CCoor(next, new Stack()));
            return 0;
        }

        Stack nextWays = Test(next, current.CurrentPoint);
        if (nextWays.Count > 0)
        {
            _pathStack.Push(new CCoor(next, nextWays));
            _stepCount++;
        }
        return 0;
    }

    public void Run() { while (Step() != 1) ; }

    // 探測四周可行方向 (右→前→左→後)
    private Stack Test(Point p, Point prev)
    {
        Stack ways = new Stack();
        int[][] dirs = { new[]{0,1}, new[]{1,0}, new[]{0,-1}, new[]{-1,0} }; // 右下左上
        foreach (var d in dirs)
        {
            int x = p.X + d[0], y = p.Y + d[1];
            if (x >= 0 && x < _map.GetLength(0) && y >= 0 && y < _map.GetLength(1))
                if (_map[x, y] && !(x == prev.X && y == prev.Y))
                    ways.Push(new Point(x, y));
        }
        return ways;
    }

    // 繪圖方法：DrawBox(迷宮)、DrawPath(路徑)、DrawNextPath(可選方向)
    public void DrawBox(Graphics g) { ... }
    public void DrawPath(Graphics g) { ... }
    public void DrawNextPath(Graphics g) { ... }
}

演算法流程說明

1. 初始化：將入口座標與其可移動方向壓入堆疊。
2. 逐步前進：
   • 取得堆疊頂端座標的可移動方向。
   • 若無方向 → 回溯。
   • 彈出一個方向 → 若為出口則推入並結束；否則探測新位置四周，將新位置與其方向壓入堆疊。
3. 結束條件：堆疊頂端座標等於出口座標。

視覺化呈現

在 WinForm 的 Paint 事件中呼叫：

private void panel1_Paint(object sender, PaintEventArgs e)
{
    maze.DrawBox(e.Graphics);       // 綠=路, 紅=牆
    maze.DrawPath(e.Graphics);      // 藍=已走路徑
    maze.DrawNextPath(e.Graphics);  // 黃=當前可選方向
}

配合 Timer 每隔 200ms 呼叫 maze.Step() 並 Invalidate()，即可動畫展示尋路過程。

擴充方向

• 支援廣度優先搜尋 (BFS) 找最短路徑
• 加入 A* 啟發式演算法
• 將迷宮地圖從檔案載入或隨機生成

結語

廣義樹配合堆疊回溯，直觀實作深度優先走迷宮。程式碼結構清晰，易於延伸為其他圖搜尋演算法教學與視覺化工具。