Game levels produced by learned generators often look right but cannot be finished: a ladder stops one tile short, or a gold piece sits in a sealed pocket. The most reliable fix today is search. An evolutionary algorithm mutates tiles, and a simulated player, meaning an automated solver that tries to complete the level, scores each candidate until one is playable. On Lode Runner this reaches full success with only a handful of edits, but it costs thousands of solver calls per level, which rules out interactive use. We propose to amortize that search. A U-Net, an image-to-image network that compresses a grid to coarse resolution and then expands it back with "skip" links that copy fine detail across, is trained on the outcomes of agent-driven repair. It learns to propose, in one forward pass, the few tile edits the search would have found. The solver stays in the loop only as a verifier and as a short fallback search.
The claim is narrow and testable. A multi-scale U-Net trained on agent-verified repairs, and given an extra output that predicts which tiles the solver can reach, should match the repair success of evolutionary search while cutting solver calls by one to two orders of magnitude and keeping edit counts near search's minimum. It should do so in games whose movement rules resist exact combinatorial encoding. If a single-scale network, or plain search with the same budget, does as well, the claim fails.
Why this gap, and why this version of it
The file shows the pieces exist separately. Evolutionary Level Repair repairs broken Lode Runner levels with evolution strategies and MAP-Elites, a search that keeps the best solution in each cell of a grid of behavioral traits. It scores candidates first on whether a solver can reach all gold and second on edit distance. It reports 100% repair success and about 4.63 edits on partially playable levels. Its authors explicitly suggest distilling those repair trajectories into faster learned models. That paper motivates this work and supplies our teacher.
Video Game Level Repair via Mixed Integer Linear Programming repairs Zelda levels exactly. It encodes reachability as a network-flow problem and reaches 100% playability in 0.13 seconds. Its authors note, however, that it cannot readily handle platformer jump dynamics. That paper constrains us: on Zelda, a learned repairer has nothing to add, so we treat MIP there as an upper bound rather than a target.
Several other papers use learned models for repair or generation but fall short in specific ways:
- Lode Encoder uses a variational autoencoder to pull user sketches toward valid structure. It has no agent verification, and only 24 of 132 sessions produced playable levels.
- Lode Enhancer upscales sketches across resolutions and leaves agent repair to future work.
- Procedural Level Generation with Diffusion Models from a Single Example uses a U-Net as a diffusion denoiser. It deliberately removes all down- and upsampling to avoid memorizing a single level, and it uses pathfinding agents only after sampling.
That last design choice matters to us. Reachability is a long-range property, and a network restricted to local patches cannot see that an edit at one end of a level opens a path to the other. Our proposal uses the multi-scale hierarchy Dai et al. removed. It can afford to, because a repairer is trained on many levels rather than one, and because its output is anchored by the input level through the skip links.
Finally, Bootstrapping Conditional GANs for Video Game Level Generation supplies a method we reuse: feed agent-accepted outputs back into training. Here, U-Net proposals that fail verification are handed to the search teacher, and its fixes become new training pairs.
Research Program
The input is a broken level, a categorical tile grid. The U-Net has two outputs.
Edit head. At each tile, it predicts whether to keep the tile or change it to a specific other type. We parametrize the output as edits rather than as a whole new level so that the natural default is to copy the input. This directly targets the minimal-change objective.
Reachability head. It predicts the set of tiles the solver can reach in the repaired level. This head is supervised by running the solver once on each teacher-repaired level. It is our key ingredient: it forces the bottleneck to represent global connectivity, which the edit labels alone signal only sparsely. It is related in spirit to Pathfinding Neural Cellular Automata, which learns grid pathfinding by repeated local propagation. We instead get long range from the U-Net's multi-scale hierarchy and use reachability as an auxiliary target, not as the generator.
Training data. Broken inputs come from two sources:
- corrupting playable VGLC levels (The VGLC: The Video Game Level Corpus, 150 Lode Runner levels);
- outputs of a learned generator trained on the same corpus. These are the realistic test distribution.
Targets are the minimal-edit repairs found by the MAP-Elites and evolution-strategy setup of Bhaumik et al.
Inference. The U-Net proposes a repair and the solver checks it. If the check fails, a short evolution-strategy search starts from the U-Net's proposal instead of the broken level. Training runs a DAgger-style loop, in which the model is retrained on corrections to its own mistakes: verified failures are sent to the teacher, and the teacher's fixes are added back to the training set.
Domains. The primary domain is Lode Runner. Its gravity, ladders, ropes and digging make reachability non-local, and it has published search-repair numbers to compare against. The second domain is Super Mario Bros. slices from VGLC and the PCG Benchmark. There, jump physics is the regime the MIP paper names as out of reach, and an A agent is the only verifier. Zelda* serves as a sanity check against MIP.
Baselines
The do-nothing reference is the broken input scored by the solver, along with a small random-search repair under matched compute. Evolutionary Level Repair reports random search succeeding 26% of the time. This anchors how hard the test set is.
The strongest existing method is agent-driven evolutionary repair, meaning MAP-Elites and the μ+λ evolution strategy from that same paper. It reports 100% success on its test levels and an average of 4.63 edits on 50–70% playable levels, compared with over 21 edits for hill climbing. We rerun it on our exact broken levels with the same solver. We then sweep its budget of solver calls to trace success and edit count as a function of calls. Beating it means one of two things:
- reaching the same success rate (at least 99% on held-out generator outputs) with equal or fewer edits using at least ten times fewer solver calls; or
- reaching higher success at every matched call budget below the budget where search saturates.
The model's training cost, including the teacher's search, is reported separately and amortized over the number of levels repaired.
On Zelda, the exact-solver reference is GAN plus MIP from Video Game Level Repair via Mixed Integer Linear Programming. It reports 100% playability, an 85.1% playable-and-unique rate, and 0.13 seconds per repair. We do not expect to beat it there. We report how close the U-Net comes, in edits and in path length (human levels average 12.5 tiles, GAN+MIP 8.6), to show the learned repairer is not systematically worse where an exact answer exists.
The architecture ablations keep data, parameter count and tuning budget fixed:
- the U-Net without its reachability head;
- a U-Net with down- and upsampling removed, as in Dai et al.;
- a plain convolutional encoder-decoder without skip links, close to the Lode Encoder design;
- a neural cellular automaton repairer.
The full model should beat the head-less and single-scale variants on success rate specifically for levels where the required edit is far from the unreachable gold. We bin the test set by that distance so the effect cannot hide in easy cases.
Why not just…?
Why not just run evolutionary repair, which already hits 100%? For offline batch generation that may be good enough, and we say so. The case for amortization is about cost per level in editors and generate-then-repair pipelines, where thousands of solver calls per level is too slow. The success-versus-solver-calls curve settles this directly. If search at a small budget already matches the U-Net, the proposal has no value. The warm-start comparison, which runs the same short search starting either from the broken level or from the U-Net proposal, isolates whether the network contributes anything beyond speed.
Why not just use the MIP solver everywhere? On Zelda it is faster and exact, and we concede that domain. Its limits are the effort of hand-writing flow constraints for each game and, per its own authors, jump physics. The U-Net needs only a solver that can say "reachable or not." Whether Lode Runner's gravity and digging can be encoded as flow constraints is not settled by the file. So the Mario experiment, where only a simulation agent can verify, is the decisive domain for this objection.
Why not just add a differentiable reachability loss, for example a pathfinding cellular automaton, and train end to end? This is a real alternative, and it is the direction the MIP paper flags. The NCA work shows learned propagation generalizes across maze sizes (84–91% accuracy on 32×32 mazes). However, it covers plain mazes, not game mechanics like falling or digging, so a learned proxy could reward edits the real solver rejects. We include the NCA as both a repairer and a reachability-head backbone. If an NCA-supervised model matches the U-Net on real-solver success, the multi-scale claim weakens and we report that.
Why not just use a denoising autoencoder or a single-scale U-Net? The Lode Encoder results (24 of 132 sessions playable) and Dai et al.'s local-only design suggest these capture local style but not global connectivity. The distance-binned ablation tests exactly that.
Proposed Experiments and Decisive Checks
On Lode Runner, we hold out 30 of the 150 levels and all generator outputs derived from them. For each method we report:
- solver-verified repair success;
- Hamming edits relative to the broken input;
- tile-pattern KL divergence to the corpus, where Lode Enhancer reports 2.441 for its scaling network;
- solver calls and wall-clock time per level.
To address the known problem that an agent's failure does not prove impossibility, we verify with two differently configured solvers. We report how often they disagree, so that "repaired" is not an artifact of one solver's blind spots.
On Mario slices, we measure A completion rate before and after repair. The only related reported figure is Dai et al.'s completion "up to 87.8%" for generation from a single level, which is a different task. No reported result was found on Lava for learned repair of Mario* slices, so the evolution-strategy teacher with a matched budget is the comparison there.
The proposal succeeds if three things hold together:
- the U-Net plus short fallback matches the teacher's success at a tenth of its solver calls on both games;
- removing the reachability head, or removing downsampling, measurably lowers success on long-distance repairs;
- the warm-started search beats cold-started search at equal budget.
It fails if matched-budget search or a single-scale network closes the gap.
References
- Evolutionary Level Repair
- Video Game Level Repair via Mixed Integer Linear Programming
- Lode Encoder: AI-constrained co-creativity
- Lode Enhancer: Level Co-creation Through Scaling
- Procedural Level Generation with Diffusion Models from a Single Example
- Bootstrapping Conditional GANs for Video Game Level Generation
- Pathfinding Neural Cellular Automata
- The VGLC: The Video Game Level Corpus.
- The Procedural Content Generation Benchmark: An Open-source Testbed for Generative Challenges in Games