C# 開發智慧型手機推箱子遊戲 (四) - 廣度優先尋路演算法詳解

尋路需求

玩家點擊螢幕任意可達位置，工人需自動沿最短路徑走過去。採用 Breadth-First Search (BFS)，從目的地反向搜尋起點(工人)，保證找到最短步數。

原始實作 (ushort 地圖版)

static class FindPath
{
    static readonly Size[] Offsets = { new Size(0,1), new Size(1,0), new Size(0,-1), new Size(-1,0) };
    static readonly Direction[] Dir = { Direction.South, Direction.East, Direction.North, Direction.West };

    public static Queue Seek(ushort[,] map, Point from, Point to)
    {
        var path = new Queue();
        if (SeekCore(map, to, out int dist))
        {
            Point cur = from;
            for (int d = dist - 1; d > 0; d--) // 依距離遞減回溯
            {
                for (int i = 0; i < 4; i++)
                {
                    Point nbr = Fcl.Add(cur, Offsets[i]);
                    if (Block.Value(map[nbr.Y, nbr.X]) == d)
                    {
                        path.Enqueue(Dir[i]);
                        cur = nbr;
                        break;
                    }
                }
            }
        }
        Block.CleanAllMark(map);
        return path;
    }

    static bool SeekCore(ushort[,] map, Point to, out int dist)
    {
        var q = new Queue();
        Block.Mark(ref map[to.Y, to.X], 1); // 目的地標記 1
        Point nbr;

        while (true)
        {
            dist = Block.Value(map[to.Y, to.X]) + 1; // 距離 = 當前標記 + 1
            for (int i = 0; i < 4; i++)
            {
                nbr = Fcl.Add(to, Offsets[i]);
                if (Block.IsMan(map[nbr.Y, nbr.X])) { dist = Block.Value(map[to.Y, to.X]); return true; }
                if (Block.IsBlank(map[nbr.Y, nbr.X]))
                {
                    Block.Mark(ref map[nbr.Y, nbr.X], dist);
                    q.Enqueue(nbr);
                }
            }
            if (q.Count == 0) return false;
            to = (Point)q.Dequeue();
        }
    }
}

演算法逐步圖解

1. Phase 1：反向標記 從目的地(紅圈 1) 向四周擴散，可通行格標記距離+1 並入隊。遇到工人即停止。
2. Phase 2：路徑重建 從工人位置出發，每步尋找標記值 = 當前距離-1 的鄰居，方向入佇列，直到目的地。

為何用 ushort？位元分配分析

若改用 byte (8 bits)，扣除 3 bits 型別，剩 5 bits 僅能標記 31 步，**不足以覆蓋大地圖對角線最長路徑**。

最長路徑理論值

對於 N×N (N 為奇數) 全空地圖，工人從一角走到對角另一角的最短步數：

Steps = (N² - 1) / 2 + N - 1

• N=9 → 48 步
• N=127 → 8,190 步 (逼近 8191 上限)
• N=129 → 8,320 步 (超過上限，舊版會失效)

這正是第 5 篇優化為 byte + 三態標記的動機來源。

關鍵輔助類別

• Fcl.Add(Point, Size)：Point 加 Size，CF 缺少此運算子。
• Block.IsBlank/IsMan/Mark/Value/CleanAllMark：地圖格子查詢與標記操作，封裝位元運算細節。