同一個 BFS，我寫了兩次：一次當品質閘門，一次當老師

2026-09-21 修訂：更正搜尋預算耗盡的語意，並補上同一盤面在不同預算下的可重做案例。原文 Node 22、每關 200 次的時間表是歷史紀錄，未附該次原始輸出，不能當成目前手機效能的驗證。

我的推箱子遊戲(BoxCat)有一百個關卡，每一關都保證可解，而且標示的「官方最短步數」是真的最短——這件事不是人肉驗的，是一個 BFS 解題器在 CI 裡把關的。

後來我又在網站上做了一個推箱子實驗室，讓人看 BFS 怎麼解題。裡面也有一個解題器，演算法一模一樣，但我從頭用 TypeScript 重寫了一次。

兩個解題器、同一個演算法，聽起來像工程失誤。寫完之後我才看清楚：它們根本是兩個不同的產品，共用同一個演算法只是巧合般的表象。

先看它們有多像

核心迴圈幾乎逐行對應。GDScript 版：

# GDScript(Godot)——BFS 主迴圈
var visited := {_key(board.player, board.boxes): true}
var queue := [[board.player, board.boxes, 0, Vector2i.ZERO]]
var head := 0
while head < queue.size():
    if visited.size() > max_states:
        return NO_MOVE            # 狀態預算用完:閘門不接受，尚未證明無解
    var item: Array = queue[head]
    head += 1
    for dir in dirs:
        # 撞牆跳過;推箱要檢查箱子的下一格...
        if not visited.has(key):
            visited[key] = true
            queue.append([next, new_boxes, depth + 1, step_first])

TypeScript 版的骨架完全相同：一樣的 visited 集合、一樣用「head 指標掃過陣列」代替 shift()(shift 是 O(n)，佇列一大就是災難)、一樣的狀態預算保險絲。

狀態的表示法不同——Godot 用 Vector2i 加 Dictionary 當集合，TS 用 "x,y" 字串加 Set——但那是語言慣用法的差異，不是設計差異。

真正的分歧在另一個地方：它們回傳什麼。

Godot 版回傳一步：它是閘門和提示

Godot 版的完整回傳是 {"steps": 最短步數， "move": 最優解的第一步}。就這兩樣，連完整路徑都不給。

因為它的兩個消費者都只需要這些：

第一個消費者是 CI。每一關進 levels.json 前，測試套件用它證明兩件事：這一關解得開(steps ≠ -1)，以及標示給玩家看的 par 就是最短步數。生成器產出的候選關卡，解不開或 par 灌水，一律進不了版本庫。它是品質閘門，閘門只需要判決，不需要過程。

第二個消費者是提示系統。玩家卡住按提示，遊戲把「當前局面」餵給解題器，拿回最優解的下一步。所以回傳裡有 move——從根節點出發的第一步方向，BFS 展開時一路帶著，找到解的瞬間就知道第一步是什麼，不用回溯路徑。

提示依玩家當前局面重新搜尋，而不是播放固定答案。手機上的等待時間會受盤面與裝置影響；狀態預算只能限制搜尋範圍，不能保證每次都在毫秒內完成。

瀏覽器版回傳全部：它是老師

TypeScript 版的回傳長這樣：

export interface SolverResult {
  steps: number;
  path: readonly DirectionName[];      // 完整解法路徑
  visited: number;                     // 總共探索了幾個狀態
  layers: readonly SearchLayer[];      // 每一層:深度、狀態數、玩家位置們
  budgetExceeded: boolean;
}

完整路徑、探索總量、還有每一層的快照——第幾層有幾個狀態、玩家可能站在哪些格子。這些對閘門毫無用處，但它們就是教學的全部：實驗室頁面拿 layers 一層一層畫出來，你可以親眼看 BFS 的波紋怎麼擴散、狀態數怎麼一層層長起來。

同一個演算法，回傳值決定它的身分：回傳布林值，它是測試；回傳一步，它是提示；回傳每一層的歷史，它是老師。

順手量的數字：狀態爆炸長什麼樣

寫這篇時我把瀏覽器版拉出來跑了一輪 benchmark(Node 22，每關 200 次取平均):

兩件事值得看。

第一，無解的關卡反而快。「角落卡死」只探索了 21 個狀態就把整個可達空間走完了——箱子一旦推進角落，後面什麼都做不了，狀態空間直接塌掉。BFS 判無解不用特殊邏輯，把可達的走完就是答案。

第二，狀態數可能隨盤面配置快速增加，因此要有搜尋預算。瀏覽器版回傳 steps: -1 時，還要看 budgetExceeded：true 代表預算用完、尚未證明有解或無解；false 才代表這次搜尋走完仍找不到解。兩者都可以讓 CI 暫不接受關卡，但不能對讀者都說成「已證明不可解」。

為什麼不共用一份程式碼

看到這裡自然會問：抽一個共用核心，兩邊 binding，不是更工程嗎？

我認真想過，答案是不值得。GDScript 和 TypeScript 沒有共用執行環境，「共用」意味著其中一邊要跨語言呼叫或轉譯，那個橋的維護成本遠超過 60 行 BFS 本身；而且兩邊的回傳介面根本不同——一邊要 move、一邊要 layers，共用核心還是得各自包一層。

演算法夠小的時候，「寫兩次」是誠實的選項。真正需要守住的是行為一致——同一個盤面，兩邊必須給出同樣的步數。這件事用測試守：兩邊各自的測試套件裡，擺著同一批盤面和同一組期望值。

帶得走的三件事

一、解題器的身分由回傳值決定，先想清楚消費者是誰再設計介面。閘門要判決、提示要一步、教學要過程，同一個演算法可以是三種產品。

二、搜尋加上狀態預算，並保留三種語意：找到解、搜尋完仍無解、預算用完而未定。發布閘門可以暫不接受未定結果，讀者介面則應清楚說明原因。

三、跨語言的小演算法，寫兩次加行為測試，常常比抽共用核心便宜。60 行的 BFS 不需要一座橋。

同一個盤面，三種回傳結果

下面例子使用本站 solver。第一個盤面可在 3 步內解開；把預算縮到 1，得到的是尚未完成判斷。另一個盤面把箱子放在非目標角落，讓搜尋完整走完後得到無解。下載包包含相同 solver，可自行重跑；它沒有驗證 Godot 版所有關卡。

import { parseBoard, solveBoard } from './solver.mjs';
const board = parseBoard({ id: 'budget-demo', name: 'Budget demo', par: 3,
  rows: ['#######', '#@    #', '# $ . #', '#     #', '#######'] });
for (const budget of [1, 400000]) {
  const { steps, budgetExceeded } = solveBoard(board, board.initial, budget);
  console.log({ budget, steps, budgetExceeded });
}
const dead = parseBoard({ id: 'deadlock', name: 'Deadlock', par: -1,
  rows: ['#####', '#$@ #', '# . #', '#####'] });
const result = solveBoard(dead, dead.initial);
console.log({ steps: result.steps, budgetExceeded: result.budgetExceeded });