I did not hand-build 100 levels: reverse generation, BFS, and CI for a Godot Sokoban game

BoxCat launched with 40 levels. While preparing version 1.1.0, I wanted to expand that number to 100 and add a hint for players who get stuck.

The direct approach would be to keep editing levels.json: arrange one map, play it, and enter an estimated move count. That is manageable for ten levels. By level one hundred, the problem is no longer patience. It is whether I can still trust the data.

One misplaced box can make a level permanently unsolvable. A par that is too low makes three stars impossible; one that is too high makes the level look deeper than it is. Once content production speeds up, manual checking becomes the least reliable part of the system.

I did not need many levels. I needed a level table I could trust.

I first turned “this level may enter a release” into conditions that code could evaluate:

None of these conditions can decide whether a level is interesting. They do block several expensive failures: a level that cannot be completed, a false scoring threshold, and a labelled difficulty curve that contradicts its own data.

Start at the finish, then pull the boxes apart

Ordinary Sokoban starts with boxes away from their goals and asks the player to push them home. The generator runs the process backwards. It starts with every box on a goal, moves the player around the board, and pulls boxes away from those goal positions.

Solved board: every box is on a goal
↓ move the player freely
↓ pull a box away from its goal
↓ repeat while preserving the reverse path implied by those pulls
Candidate level: reverse the pull sequence to obtain a path back to the goals

Every pull can be reversed into a legal push. The generator is therefore not scrambling pieces and hoping that a solution exists; it preserves at least one route back to the completed state.

It still rejects many candidates. Disconnected floor areas, already solved boards, boxes that begin in a dead corner, duplicate layouts, and solutions that are too shallow never reach the candidate list. Normal, hard, and expert modes vary room size, box count, and pull count to produce boards of different depths.

Reverse generation improves the odds of producing a useful solvable candidate. It is not the final signature. Every level still returns to the solver for proof from its published starting position.

BFS measures the shortest move count, not the author’s intuition

The solver uses breadth-first search. Each state consists of the player position and the sorted box positions. From that state it tries up, down, left, and right, skipping moves into walls or attempts to push two boxes at once. The first state with every box on a goal has the shortest move count.

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
    # Expand four directions; return depth + 1 on the first solution

Level generation and CI currently allow a budget of 400,000 states. Exceeding that budget does not mean “probably solvable”; it fails. This discards some boards that might have solutions but require a much larger search, in exchange for predictable build time.

Par here is the minimum number of player moves, including walking and pushing. It is not the minimum number of pushes. The value directly controls star ratings: matching par is required for three stars, so it cannot be an estimate entered after a few playthroughs.

The same solver also answers “what should I do next?”

Each BFS queue item carries first_move alongside depth. It records the first step taken from the current board to reach that state. When the search finds its shortest solution, it knows both the remaining distance and the first direction on an optimal path.

The hint system in BoxCat 1.1.0 reuses that result. It does not maintain a separate answer sheet or ask an AI to guess. It searches from the player’s current board and executes one real step from the shortest path. A test recomputes the distance before and after the hint and checks that the remaining optimum falls by exactly one.

One algorithm now answers three questions: whether a level may enter the data table, what its par should be, and where a stuck player should move next. Keeping those answers behind one source is easier to reconcile than maintaining three rule sets.

CI does not trust the par written in levels.json

The generator prints candidates as JSON. A human selects them before merging them into the official levels.json. Entering the repository does not complete verification: tests reload the full table, parse every board, and run BFS again.

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")

Manually changing par to a prettier number does not work. The next test run recomputes it and blocks the mismatch. The curve is checked the same way: after sorting from l001 to l100, no par may be lower than the preceding one.

I reran the current KOF Forge before publishing. It contains 100 levels from l001 to l100, with par increasing from 1 to 28. GUT completed 30 tests and 491 assertions, all passing.

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

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

That run also exposed a separate practical issue: after GUT prints a passing result, Godot can still hit a known crash during shutdown. The release script therefore does not trust the process exit code alone. It requires both “Passing Tests” and “All tests passed!” in the verdict; an incomplete or genuinely failing run produces neither pair.

Solvable does not mean fun, and par does not equal difficulty

BFS can prove the length of a shortest path. It cannot prove where a player will need to stop and think. Two levels may both have a 20-move optimum. One is a corridor that asks for repeated pushes. The other requires moving a box away from its goal to make room for a turn. The number is identical; the experience is not.

Reverse generation also produces boring boards. Some are valid but have a single obvious route. Others contain several boxes but very few meaningful choices. No boolean assertion can make that judgement for me.

Human selection therefore remains the last step. Machines reject mistakes, repeat calculations, and enforce the data contract. A person reads the rhythm, spots fake difficulty, and decides whether a level deserves the player’s time.

The App Store still has 1.0.0; the 100 levels belong to 1.1.0

The version boundary matters. The public App Store build of BoxCat is currently 1.0.0 with 40 levels. The 100-level table, solver hints, and tests described here are in the 1.1.0 code under preparation and were not yet the public store build at publication time.

I did not use a generator to replace level design. It replaced checks that suit a machine and are easy to miss when a person gets tired: whether the board has a solution, how short that solution is, and whether the data tells the truth.

After reaching 100 levels, the human role became clearer. I no longer need to walk the same verification path one hundred times. I decide what deserves to remain after the machine proves that it can be played.