# Video Game Level Repair via Mixed Integer Linear Programming

arXiv: https://arxiv.org/abs/2010.06627 · HTML: https://mlsanity.com/paper/2010.06627/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Oct 2020.

## Built on by (most cited first, 18 of 18)

- [On the Importance of Environments in Human-Robot Coordination](https://mlsanity.com/paper/2106.10853/) (2021)
- [Illuminating Diverse Neural Cellular Automata for Level Generation](https://mlsanity.com/paper/2109.05489/) (2021)
- [Multi-Robot Coordination and Layout Design for Automated Warehousing](https://mlsanity.com/paper/2305.06436/) (2023)
- [DreamCraft: Text-Guided Generation of Functional 3D Environments in Minecraft](https://mlsanity.com/paper/2404.15538/) (2024)
- [DreamGarden: A Designer Assistant for Growing Games from a Single Prompt](https://mlsanity.com/paper/2410.01791/) (2024)
- [Arbitrarily Scalable Environment Generators via Neural Cellular Automata](https://mlsanity.com/paper/2310.18622/) (2023)
- [Surrogate Assisted Generation of Human-Robot Interaction Scenarios](https://mlsanity.com/paper/2304.13787/) (2023)
- [Mario Plays on a Manifold: Generating Functional Content in Latent Space through Differential Geometry](https://mlsanity.com/paper/2206.00106/) (2022)
- [GenCO: Generating Diverse Designs with Combinatorial Constraints](https://mlsanity.com/paper/2310.02442/) (2023)
- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)
- [Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems](https://mlsanity.com/paper/2510.03472/) (2025)
- [Active Learning for Classifying 2D Grid-Based Level Completability](https://mlsanity.com/paper/2309.04367/) (2023)
- [Guided Game Level Repair via Explainable AI](https://mlsanity.com/paper/2410.23101/) (2024)
- [On Linking Level Segments](https://mlsanity.com/paper/2203.05057/) (2022)
- [Reconstructing Existing Levels through Level Inpainting](https://mlsanity.com/paper/2309.09472/) (2023)
- [Algorithmic Scenario Generation as Quality Diversity Optimization](https://mlsanity.com/paper/2409.04711/) (2024)
- [Generating Diverse Indoor Furniture Arrangements](https://mlsanity.com/paper/2206.10608/) (2022)
- [Evolutionary Level Repair](https://mlsanity.com/paper/2506.19359/) (2025)

## Abstract (arXiv)

Recent advancements in procedural content generation via machine learning enable the generation of video-game levels that are aesthetically similar to human-authored examples. However, the generated levels are often unplayable without additional editing. We propose a generate-then-repair framework for automatic generation of playable levels adhering to specific styles. The framework constructs levels using a generative adversarial network (GAN) trained with human-authored examples and repairs them using a mixed-integer linear program (MIP) with playability constraints. A key component of the framework is computing minimum cost edits between the GAN generated level and the solution of the MIP solver, which we cast as a minimum cost network flow problem. Results show that the proposed framework generates a diverse range of playable levels, that capture the spatial relationships between objects exhibited in the human-authored levels.