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

我的推箱子遊戲(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 展開時一路帶著,找到解的瞬間就知道第一步是什麼,不用回溯路徑。

注意這個設計的含義:提示不是預錄的。玩家把局面推到任何地方,提示都是「從你現在這個爛攤子出發」的最優下一步。代價是每次按提示都重跑一次 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 判無解不用特殊邏輯,把可達的走完就是答案。

第二,爆炸來得比直覺快。盤面從 6×5 放大到 9×6、箱子一樣是兩顆,狀態數從 62 跳到 6,226——一百倍。這就是為什麼兩個版本都有 max_states 保險絲(Godot 20 萬、瀏覽器 40 萬):不是怕演算法錯,是怕有人餵一個大盤面把整個分頁凍住。預算爆掉一律回報「不可解」,對閘門來說這是保守而正確的判決——進不了版本庫的關卡,寧可錯殺。

為什麼不共用一份程式碼

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

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

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

帶得走的三件事

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

二、搜尋類的程式一律加狀態預算,而且爆預算時的語意要想清楚(我的選擇:一律視為不可解,保守偏安全)。

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