I wrote the same BFS twice: once as a quality gate, once as a teacher

Revised September 21, 2026: corrected budget-exhaustion semantics and added a reproducible same-board comparison. The original Node 22, 200-run timing table is historical and lacks its raw run output here; it does not validate current mobile performance.

My Sokoban game (BoxCat) has a hundred levels, each guaranteed solvable, and each labeled with an official minimum move count that is genuinely minimal. No human verified that — a BFS solver guards it in CI.

Later I built a Sokoban lab on this site, where you can watch BFS solve puzzles. It contains a solver too — the same algorithm — but I rewrote it from scratch in TypeScript.

Two solvers, one algorithm: sounds like an engineering mistake. Only after finishing did I see it clearly — they are two different products, and sharing an algorithm is almost coincidental surface resemblance.

First, how similar they are

The core loops correspond almost line for line. The GDScript version:

# GDScript (Godot) — BFS main loop
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            # state budget exhausted: not accepted by the gate
    var item: Array = queue[head]
    head += 1
    for dir in dirs:
        # skip walls; pushing checks the box's next cell...
        if not visited.has(key):
            visited[key] = true
            queue.append([next, new_boxes, depth + 1, step_first])

The TypeScript skeleton is identical: the same visited set, the same head-pointer sweep instead of shift() (shift is O(n) — a disaster once the queue grows), the same state-budget fuse.

State representation differs — Godot uses Vector2i with a Dictionary as a set, TS uses "x,y" strings with a Set — but that is language idiom, not design.

The real divergence is elsewhere: what they return.

The Godot version returns one move: it is a gate and a hint

The Godot version's full return value is {"steps": minimum, "move": first move of an optimal solution}. That is all — not even the full path.

Because both of its consumers need exactly that and nothing more:

The first consumer is CI. Before any level enters levels.json, the test suite uses the solver to prove two things: the level is solvable (steps ≠ -1), and the par shown to players is the true minimum. Generator candidates that are unsolvable or have inflated pars never reach the repository. A gate needs a verdict, not a journey.

The second consumer is the hint system. A stuck player taps hint; the game feeds the current position to the solver and gets back the optimal next move. Hence the move in the return value — the first move from the root, carried along during expansion, known the instant a solution is found, no path reconstruction needed.

Hints search the player’s current state rather than replay a fixed answer. Latency depends on the board and device; a state budget does not guarantee millisecond completion.

The browser version returns everything: it is a teacher

The TypeScript version's return value:

export interface SolverResult {
  steps: number;
  path: readonly DirectionName[];      // the full solution path
  visited: number;                     // total states explored
  layers: readonly SearchLayer[];      // per depth: state count, player cells
  budgetExceeded: boolean;
}

The full path, the exploration total, and a snapshot of every layer — how many states at each depth, which cells the player might occupy. Useless to a gate; the entirety of teaching. The lab page draws layers one by one, and you watch the BFS ripple spread and the state count swell per depth.

Same algorithm; the return value assigns its identity. Return a boolean and it is a test. Return one move and it is a hint. Return per-layer history and it is a teacher.

The numbers: what state explosion looks like

While writing this I benchmarked the browser version (Node 22, 200 runs averaged per level):

Two things worth seeing.

First: the unsolvable level is fast. "Corner deadlock" exhausted its entire reachable space after only 21 states — once a box is pushed into a corner, nothing further is possible and the state space collapses. BFS needs no special logic to prove unsolvability; walking everything reachable is the proof.

Second, the search space can grow rapidly, which makes a budget useful. A browser result with steps: -1 still requires checking budgetExceeded: true means the search stopped without deciding solvability; false means the search exhausted its reachable states without a solution. CI can reject both for release, but only one establishes unsolvability under this solver’s rules.

Why not share one implementation

The natural question: extract a shared core with bindings on both sides — is that not better engineering?

I considered it seriously. It is not worth it. GDScript and TypeScript share no runtime; "sharing" means one side crossing a language bridge or transpiling, and maintaining that bridge costs far more than 60 lines of BFS. Moreover the two return interfaces genuinely differ — one wants a move, the other wants layers — so a shared core would still need a wrapper on each side.

When the algorithm is small enough, writing it twice is the honest option. What actually needs guarding is behavioral agreement — the same board must yield the same move count on both sides. Tests guard that: both suites carry the same boards with the same expected values.

Three things to take away

One — a solver's identity is its return value; know the consumer before designing the interface. A gate wants a verdict, a hint wants one move, a teacher wants the journey: one algorithm, three products.

Two — keep three outcomes: solved, exhausted without a solution, and unresolved because the budget ran out. A release gate may reject unresolved candidates, while the UI should explain why.

Three — for small cross-language algorithms, writing twice plus behavioral tests routinely beats extracting a shared core. Sixty lines of BFS does not justify a bridge.

One result type, three distinct outcomes

The example uses this site’s solver. The first board is solvable in three moves; a budget of one leaves it unresolved. A separate board traps the box in a non-goal corner and exhausts the search without a solution. The download includes the solver for reproduction; it does not verify every Godot level.

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 });