C# 開發智慧型手機推箱子遊戲 (五) - 廣度優先尋路優化：byte 地圖與三態標記

優化動機

原版 FindPath 使用 ushort[,] map，標記值隨距離遞增，導致：

• 搜尋距離受限於 13 bits（8192 步），大地圖可能失效。
• 記憶體佔用是 byte[,] 的 2 倍。

改進版採 byte 地圖 + 三態循環標記 (1→2→3→1…)，解決上述問題。

核心演算碼（已重構為 byte[,]）

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 };

    /// 
公開介面：回傳從 from 到 to 的最短路徑方向佇列
    public static Queue Seek(byte[,] map, Point from, Point to)
    {
        var path = new Queue();
        if (SeekCore(map, to, out int mark)) // 反向搜尋：從目的地找起點
        {
            Point cur = from;
            // mark 目前為目的地標記值，下一步應為 (mark % 3) + 1
            for (int nextMark = (mark % 3) + 1; cur != to; nextMark = (nextMark % 3) + 1)
            {
                for (int i = 0; i < 4; i++)
                {
                    Point nbr = Fcl.Add(cur, Offsets[i]);
                    if (Block.Value(map[nbr.Y, nbr.X]) == nextMark)
                    {
                        path.Enqueue(Dir[i]);
                        cur = nbr;
                        break;
                    }
                }
            }
        }
        Block.CleanAllMark(map); // 還原地圖
        return path;
    }

    /// 
核心 BFS：從 to 向外波前擴散，標記 1/2/3 循環
    static bool SeekCore(byte[,] map, Point to, out int finalMark)
    {
        var q = new Queue();
        Block.Mark(ref map[to.Y, to.X], 1); // 目的地標記 1
        Point nbr;

        while (true)
        {
            int curMark = Block.Value(map[to.Y, to.X]);
            int nextMark = (curMark % 3) + 1; // 1→2→3→1…

            for (int i = 0; i < 4; i++)
            {
                nbr = Fcl.Add(to, Offsets[i]);
                if (Block.IsMan(map[nbr.Y, nbr.X])) // 找到工人(起點)
                {
                    finalMark = curMark;
                    return true;
                }
                if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可通行
                {
                    Block.Mark(ref map[nbr.Y, nbr.X], nextMark);
                    q.Enqueue(nbr);
                }
            }
            if (q.Count == 0) { finalMark = 0; return false; } // 無路可走
            to = (Point)q.Dequeue(); // BFS：取隊首繼續擴散
        }
    }
}

三態標記運作示意

• 紅色 1：目的地（搜尋起點）
• 依序黃(2)→綠(3)→藍(1)→粉(2)→青(3)… 向外波前擴散
• 遇到工人(紅圈)即停止，回傳成功
• 標記值永遠在 {1,2,3} 循環，不再受 8192 步限制

副作用與修正

1. 全專案 `ushort → byte`：Block.cs、DataFile.cs、Level.cs 等所有地圖相關簽名同步修改。
2. Block.Mark/Value/CleanAllMark 位元操作調整：
   原 block |= (ushort)(value << 3) → 現 block |= (byte)(value << 3) (低 3 bits 留給格子型別，高 5 bits 足夠存 1~31，三態僅用 1~3)。
3. 記憶體減半：32×32 關卡從 2 KB 降至 1 KB，對行動裝置極為友善。

效能比較 (32×32 空地圖，對角線最長路徑)