C# 開發智慧型手機軟體：推箱子遊戲（四）Common/FindPath.cs 廣度優先尋路原始實作

前言

本系列第四篇，展示優化前的 FindPath.cs 原始實作：使用 ushort 儲存距離標記，廣度優先搜尋 (BFS) 從目的地反向尋找工人，雙階段（標記+重建）設計。

原始程式碼

namespace Skyiv.Ben.PushBox.Common
{
    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[] Dirs = { Direction.South, Direction.East, Direction.North, Direction.West };

        // 公開介面：傳回移動方向佇列
        public static Queue Seek(ushort[,] map, Point from, Point to)
        {
            var moveQueue = new Queue();
            if (Seek(map, to, out int value)) // 階段一：標記
            {
                Point here = from;
                // 階段二：依標記重建路徑
                for (value--; value > 0; value--)
                {
                    for (int i = 0; i < Offsets.Length; i++)
                    {
                        Point nbr = Fcl.Add(here, Offsets[i]);
                        if (Block.Value(map[nbr.Y, nbr.X]) == value)
                        {
                            moveQueue.Enqueue(Dirs[i]);
                            here = nbr;
                            break;
                        }
                    }
                }
            }
            Block.CleanAllMark(map);
            return moveQueue;
        }

        // 階段一：BFS 標記
        static bool Seek(ushort[,] map, Point to, out int value)
        {
            var q = new Queue();
            Block.Mark(ref map[to.Y, to.X], 1); // 目的地標記 1
            Point nbr = Point.Empty;

            for (;;)
            {
                value = Block.Value(map[to.Y, to.X]) + 1; // 下一層標記值 = 當前距離+1
                for (int i = 0; i < Offsets.Length; i++)
                {
                    nbr = Fcl.Add(to, Offsets[i]);
                    if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 找到工人
                    if (Block.IsBlank(map[nbr.Y, nbr.X])) // 可通行
                    {
                        Block.Mark(ref map[nbr.Y, nbr.X], value);
                        q.Enqueue(nbr);
                    }
                }
                if (Block.IsMan(map[nbr.Y, nbr.X])) break; // 成功
                if (q.Count == 0) return false; // 失敗
                to = q.Dequeue(); // 廣度優先：取出下一層節點
            }
            return true;
        }
    }
}

演算法詳細流程

1. 階段一：反向 BFS 標記
   • 從目的地 to 開始，標記為 1。
   • 每一層展開：取出佇列節點，檢查四鄰居。
   • 若鄰居為工人 → 成功結束。
   • 若鄰居為空白 (地/槽) → 標記為 當前距離+1，入佇列。
   • 佇列空 → 失敗。
2. 階段二：路徑重建
   • 從工人位置 from 出發。
   • 尋找鄰居標記值 = 目標標記-1 的方向，入佇列，移動至該鄰居。
   • 重複直到到達目的地 (標記 1)。

為什麼需要 ushort？

• 標記值 = 距離 + 1，最大距離受限於位元寬度。
• ushort = 16 bits，扣除 3 bits 狀態，餘 13 bits → 最大 8191 步。
• 127x127 地圖最長最短路徑 ≈ 8190 步，剛好在極限內。

視覺化範例

結語

原始實作邏輯清晰，但受限於 ushort 位元寬度。第 5 篇將展示如何透過標記值循環突破限制，並將地圖型別降為 byte。