我沒有手刻 100 個關卡：用反向生成、BFS 與 CI 替 Godot 推箱子把關

BoxCat 1.0 上架時有 40 關。準備 1.1.0 時，我想把關卡擴到 100 關，並加入卡關時的提示。

最直接的做法，是繼續編輯 levels.json，一關一關排地圖、試玩，再填上預估步數。做到第十關還行；做到第一百關，問題已經不是耐心，而是我還能不能相信這份資料。

只要一個箱子放錯位置，關卡可能永遠無解。par 填得太低，玩家永遠拿不到三星；填得太高，又會讓難度看起來比實際更深。新增內容變快之後，人工檢查反而成了最不穩定的部分。

我要的不是很多關，是一份可以相信的關卡表

我先把「一關可以進版本」寫成幾個能由程式判斷的條件：

這些條件沒有一項能判斷關卡是否有趣，但至少能擋住幾種最昂貴的錯：不能玩、評分門檻寫錯，以及標示的難度曲線和資料互相矛盾。

先從終點開始，再把箱子拉亂

一般推箱子是從起點把箱子推到目標。關卡產生器反過來做：先把每個箱子放在目標上，得到已完成的盤面，再讓玩家在地圖裡移動，從目標位置把箱子一個個拉開。

完成盤面：箱子全部在目標上
↓ 玩家自由移動
↓ 從箱子前方往外拉
↓ 重複多次，保留拉動紀錄所隱含的反向路徑
候選關卡：把拉動順序倒過來，就有一條推回目標的路

每一次拉箱都可以反過來變成一次合法推箱，因此這種生成方式不是先亂排再祈禱它有解。它從一開始就保留了一條回到完成狀態的路。

產生器仍然會丟掉不少候選：地板區域不連通、生成後已經完成、箱子一開始就在死角、內容重複，或 solver 算出的最短路徑太淺，都不會進入候選清單。normal、hard 與 expert 模式則用不同房間大小、箱子數量和拉動次數，產生不同深度的盤面。

反向生成負責提高「拿到可解候選」的機率，不負責最後簽核。每一關仍然要重新交給 solver，從正式起點證明一次。

BFS 算的是最短移動步數，不是作者的感覺

Solver 使用 BFS。每個狀態由玩家位置和排序後的箱子位置組成；從目前狀態嘗試上、下、左、右四個方向，撞牆或同時推兩個箱子的路徑直接跳過。第一次找到所有箱子都在目標上的狀態，就是最短移動步數。

var visited := {_key(board.player, board.boxes): true}
var queue := [[board.player, board.boxes, 0, Vector2i.ZERO]]

while head < queue.size():
    if visited.size() > max_states:
        return NO_MOVE
    # 展開四個方向；第一次完成時回傳 depth + 1

目前關卡產生與 CI 驗證把狀態預算設為 400,000。超過預算不會被當成「大概可解」，而是直接失敗。這會犧牲某些可能有解、但搜尋空間太大的盤面，換來可以預期的建置時間。

這裡的 par 是玩家完成關卡所需的最少移動步數，包含走路和推箱，不是最少推箱次數。它直接影響星級：追平 par 才拿得到三星，所以不能靠作者試玩幾次後填一個看起來合理的數字。

同一個 solver，順便回答「下一步怎麼走」

BFS 的 queue 除了 depth，還保留 first_move：從目前盤面出發，到達這個狀態時走的第一步是什麼。找到最短解時，solver 不只知道還剩幾步，也能回傳最佳路徑的第一個方向。

BoxCat 1.1.0 的提示功能直接重用這個結果。提示不是另外維護一份解答，也不是讓 AI 猜下一步；它從玩家當下的盤面重新搜尋，真的執行最短路徑上的一步。測試會再次計算提示前後的距離，確認剩餘最短步數剛好減少一。

同一套演算法因此負責三件事：關卡能不能進資料表、par 應該是多少，以及玩家卡住時下一步往哪裡走。三份答案來自同一個來源，比各自維護三套規則容易對帳。

CI 不相信 levels.json 裡自己寫的 par

產生器會把候選輸出成 JSON，人工挑選後才併進正式 levels.json。進入版本庫不代表驗證完成；測試會重新載入整張表，逐關解析，再跑一次 BFS。

var steps := SokobanSolver.solve(board, 400000)
assert_gt(steps, 0, "level must be solvable")
assert_eq(steps, int(level.get("par", -1)),
    "par must equal solver optimum")

所以手動把 par 改漂亮沒有用。下一次測試會用 solver 重算，數字不一致就擋下來。難度曲線也是同樣做法：照 l001 到 l100 排序，每一關的 par 都不能低於上一關。

發文前我重新跑過目前的 KOF Forge：100 關從 l001 到 l100，par 從 1 增加到 28；GUT 跑完 30 個測試、491 個 assertions，全部通過。

Scripts               7
Tests                30
Passing Tests        30
Asserts             491
Time              22.596s

---- All tests passed! ----

這次測試也留下另一個現實問題：GUT 印出全部通過後，Godot 仍會在關閉階段遇到已知 crash。release script 因此不只相信 process exit code，而是同時要求出現「Passing Tests」和「All tests passed!」兩個判定字串；測試沒跑完或真的失敗，都不會有這組結果。

可解不等於好玩，par 也不等於難度

BFS 可以證明最短路徑有幾步，不能證明玩家會不會在關鍵位置停下來思考。兩關都可能是 20 步，一關只是沿著走廊把箱子往前推；另一關則要求先把箱子推離目標，騰出轉身空間。數字相同，體感完全不同。

反向生成也會產生很無聊的盤面。有些地圖雖然合法，解法卻一路到底；有些箱子很多，真正需要做的選擇很少。這些問題沒有一個 boolean assertion 可以替我判斷。

所以流程最後仍然保留人工挑選。機器負責排除錯誤、重複計算和守住資料契約；人負責看節奏、辨識假難度，決定一關值不值得佔據玩家的時間。

目前上架的是 1.0.0，100 關仍在 1.1.0

版本邊界要說清楚：App Store 上的 BoxCat 目前是 1.0.0，提供 40 關。本文拆解的 100 關、solver 提示與相關測試位於準備中的 1.1.0 程式碼，發文時尚未成為商店公開版本。

我沒有用生成器取代關卡設計。它取代的是那些很適合交給機器、又很容易因為疲勞漏掉的檢查：到底有沒有解、最少幾步、資料是不是誠實。

做到 100 關後，我反而更確定人的工作在哪裡。重複驗證交給機器；等它證明「這關可以玩」，人再決定這一關值不值得留下。