C# 開發智慧型手機軟體：推箱子遊戲（五）尋路演算法優化與記憶體減半

前言

本文介紹 FindPath 尋路演算法的重大優化：標記值改為 1~3 循環、地圖儲存從 ushort 降為 byte，使搜索距離不再受限於 8192 步，記憶體使用減半。

優化前後對比

演算法核心改動

// 優化前：標記值 = 距離 + 1，需大量位元
Block.Mark(ref map[y, x], distance + 1); // 使用高 13 位

// 優化後：標記值循環 1,2,3
int mark = (distance % 3) + 1;
Block.Mark(ref map[y, x], mark); // 僅需 2 位元 (值 1~3)

搜尋流程（廣度優先 BFS）

1. 從**目的地**起始，標記為 1，加入佇列。
2. 取出佇列首元素，檢查四鄰居（南、東、北、西）。
3. 若鄰居為**空白**（地/槽），標記為 (當前標記 % 3) + 1，入佇列。
4. 若鄰居為**工人**，搜尋成功，進入路徑重建階段。
5. 佇列空則失敗（無法到達）。
6. 路徑重建：從工人位置出發，按標記值遞減（3→2→1）尋找下一步，直到目的地。

視覺化說明

• 紅色圓圈「1」為目的地（起始點）。
• 標記值按紅、黃、綠、藍、粉紅、青循環向外擴散。
• 遇到工人即停止，重建最短路徑。

程式碼修改範圍

• FindPath.cs：重寫 Seek 邏輯，標記值改為模 3 循環。
• Block.cs：所有 ushort 參數/欄位改為 byte，Mark/Value/CleanAllMark 配合 2 位元標記。
• 其他檔案：僅需將地圖陣列宣告 ushort[,] → byte[,]。

結語

巧妙的標記值循環設計，突破位元寬度限制，同時大幅降低記憶體佔用。此優化思想適用於所有記憶體受限環境的圖搜尋演算法。