Never ship an impossible level: a BFS solver as puzzle QA in TypeScript

The Hug Maze is one of four games in our free, fan-made Bubu & Dudu Cozy Game Suite. Two bears start on opposite sides of a 12 × 12 grid and have to meet on a heart tile. Dudu is heavy, so he can push giant blocks and honey jars. Bubu is small, so she fits through mouse holes. Either bear can push a cushion, which then slides until it hits something, and a pressure plate opens its gate while anything stands on it.

Rules like these combine in ways that are hard to predict by hand. A block pushed one tile too far blocks a corridor for good. A cushion slides past the plate it was meant to stop on. A gate closes behind the only bear who could have reopened it. The worst bug a puzzle game can ship is an impossible level, and the second worst is a level that is far easier than intended because one mechanic turns out to be optional.

This article shows how we used a small breadth-first solver as the level designer's QA tool. It proves that all 15 levels are solvable and sets the three-star par automatically. During design it also told us when a level didn't really need the mechanic it was supposed to teach.

Step one: an engine you can search

A solver can only explore a game whose rules it can run quickly and safely, thousands of times, without side effects. So the maze rules live in a plain TypeScript module with no DOM, no Phaser and no mutation. A state is plain data:

export interface MazeState {
  board: Board;          // static tiles: walls, holes, cats, plates, gates, the heart
  bubu: Pos;
  dudu: Pos;
  movers: Mover[];       // blocks, honey jars and cushions
  moves: number;
}

The whole rulebook is one function. It takes a state, a bear and a direction, and returns either null (the move is blocked) or a brand-new state:

export function move(s: MazeState, who: Who, dir: Dir): MoveResult | null {
  if (isWon(s)) return null;
  const [dx, dy] = DIRS[dir];
  const me = s[who];
  const other = who === 'bubu' ? s.dudu : s.bubu;
  const tx = me.x + dx;
  const ty = me.y + dy;
  const t = tileAt(s.board, tx, ty);
  if (t === 'wall' || t === 'cat') return null;
  if (t === 'hole' && who !== 'bubu') return null;
  if (!gateOpen(s, tx, ty)) return null;
  // Bears only share the heart tile.
  if (other.x === tx && other.y === ty && t !== 'heart') return null;

  const m = moverAt(s, tx, ty);
  if (m) {
    if ((m.kind === 'block' || m.kind === 'jar') && who !== 'dudu') return null;
    // Evaluate pushes with the pushing bear "lifted" off its tile, so it can't block itself.
    const probe: MazeState = { ...s, [who]: { x: -9, y: -9 } };
    if (!freeForMover(probe, tx + dx, ty + dy)) return null;
    let nx = tx + dx;
    let ny = ty + dy;
    if (m.kind === 'cushion') {
      const without: MazeState = { ...probe, movers: s.movers.filter((o) => o.id !== m.id) };
      while (freeForMover(without, nx + dx, ny + dy)) {
        nx += dx;
        ny += dy;
      }
    }
    // ...the pushed object moves to (nx, ny)
  }
  // ...return { state: { ...s, movers, [who]: { x: tx, y: ty }, moves: s.moves + 1 }, ... }
}

(condensed from games/maze/logic.ts)

Three details matter more than they look.

Gates are derived, not stored. A gate is open when any bear or object is on its plate, or when something is standing in the gate itself, so it can't close on a bear. Because this is computed from positions, the state holds no gate flags that could fall out of sync, and two states with the same positions really are the same state.

The pushing bear is lifted out before checking the push. Without the probe trick, a cushion pushed back the way the bear came would bump into the bear's own previous tile. It's a one-line fix, and the unit tests pin it down.

Every rule is a refusal. Holes refuse Dudu, the heart refuses blocks, and a mouse hole refuses anything pushed into it. Writing the rules as early return nulls keeps them independent, and the solver treats a refused move exactly the way the player sees it: nothing happens.

The Phaser scene calls the same move(). When it returns a state, the scene tweens the sprites to the new positions and plays a sound. When it returns null, the bear gives a little bump. The game and the solver cannot disagree about the rules.

Step two: breadth-first search over the whole puzzle

With an immutable move(), solving a level is a textbook breadth-first search. A node is a state, and an edge is one of eight possible moves: two bears times four directions. BFS explores states in order of move count, so the first winning state it reaches uses the fewest moves possible.

The only design choice is the visited-set key. Walls, plates and gates are static or derived, so the key needs just the bears and the movable objects:

export function stateKey(s: MazeState): string {
  const ms = s.movers
    .map((m) => `${m.kind[0]}${m.x},${m.y}`)
    .sort()
    .join(';');
  return `${s.bubu.x},${s.bubu.y}|${s.dudu.x},${s.dudu.y}|${ms}`;
}

Sorting the movers by kind and position, not by id, means two identical crates count as interchangeable. Swapping them gives the same key, which removes a whole class of duplicate states.

The solver stores each visited key with the key it came from and the move that got there, and walks back from the winning state to rebuild the path:

for (const who of ['bubu', 'dudu'] as Who[])
  for (const dir of dirs) {
    const r = move(s, who, dir);
    if (!r) continue;
    const k = stateKey(r.state);
    if (seen.has(k)) continue;
    seen.set(k, { prev: ks, step: { who, dir } });
    if (r.won) return rebuildPath(k);
    if (seen.size > limit) return null;
    next.push(r.state);
  }

(condensed)

How big does the search get? On our levels, the smallest search explores about 1,500 states and the hardest about half a million, the one with two honey jars and two plates. Even that finishes in a couple of seconds in Node. The limit guard turns a runaway level into a clear test failure instead of a hung CI job.

Step three: let the tests own the levels

Levels are ASCII art:

############
#B..#...D..#
#...#......#
#...#.J..J.#
#...#......#
#...P......#
#...#..p.q.#
#####Q######
#..........#
#.....H....#
#..........#
############

The test suite treats every level as a claim to verify, not a fixture to trust:

it.each(LEVELS.map((l, i) => [i + 1, l] as const))('level %i is solvable in exactly its par', (_n, l) => {
  const s = solve(parseLevel(l), 2_000_000);
  expect(s).not.toBeNull();
  expect(s!.moves).toBe(l.par);
  // Replaying the solver's path really wins.
  let st = parseLevel(l);
  for (const step of s!.path) st = move(st, step.who, step.dir)!.state;
  expect(isWon(st)).toBe(true);
});

This one test gives us three guarantees:

1. No impossible levels. Change a single character in a layout and the suite tells you right away if the level can no longer be won.
2. Pars are honest. The par stored with each level must equal the solver's optimum. Three stars means you matched the best possible solution, not a number someone guessed. If an edit creates a shortcut, the test fails and shows the new optimum.
3. The solver is checked too. Replaying its path through move() proves the path wins under the real rules, so a solver bug can't quietly approve a broken level.

Our browser tests reuse the same solver. The Playwright test for the maze solves level 1 in the test process, then plays that path with real key presses (WASD for Bubu, arrows for Dudu) and checks for the hug, the three stars and the Paw Coins.

Step four: ask whether a mechanic really matters

Solvable is not the same as good. While designing the levels, we ran a second check. For each level, we re-solved a copy with its featured mechanic removed:

• a mouse hole turned into a wall
• a block or jar turned into a wall, so it can't be pushed
• a plate turned into plain floor
• a cushion turned into a wall

If the level was still solvable, the mechanic was optional. For a level whose whole point is "slide the cushion onto the plate", that's a design bug.

This caught real mistakes. In our first draft of "Slippy Cushion", one bear could simply stand on the plate while the other walked through the gate, so the cushion was decoration. The fix was to put the heart behind the gate as well. Now both bears must pass, and only a cushion can hold the plate down while they do. "Honey Pot" works the same way: Dudu has to push the jar onto the plate because both bears need the gate open at once.

Not every level has to depend on every object. "Snoring Garden" is a deliberate breather where the cushions and blocks are mostly red herrings, and its hint says so. The check makes that a decision instead of an accident.

The same idea works in our platformer, which has no grid. Snack Run's tests build a reachability graph from the real jump arc: a 1-tile climb can span 4 tiles, a 2-tile climb 3, a 3-tile climb 2, and springs launch you 6 up. The tests then prove that both bears can reach the goal and every snack in all five levels. The first run found unreachable snacks in four of the five levels, mostly on platforms one row too high. Each fix was a one-number change in the level data.

What we took from it

• Make the rules a pure function first. The solver, the tests and the game all reuse one move(), and that only works because it has no side effects.
• Key states by what can change. Leaving derived and static data out of the visited set, and treating identical objects as interchangeable, keeps the search small enough for CI.
• Let tests own the numbers. Pars that must equal the solver's result can't drift, and a failing test tells the designer the new value.
• Test design intent, not just correctness. Re-solving without a mechanic is a cheap way to find levels that don't teach what they claim to.

The Bubu & Dudu Cozy Game Suite is an unofficial fan tribute: Bubu & Dudu are characters by their original creator. The full TypeScript source is a free download on the DEV3 marketplace, including the solver and all 15 levels. For the other three games, the code-drawn art and the share links that carry a whole decorated room, read the case study.