Video Game Level Repair via Mixed Integer Linear Programming
This addresses the issue of unplayable generated levels in procedural content generation for video games, offering an automated solution for game developers, though it is incremental as it builds on existing GAN and MIP methods.
The paper tackles the problem of generating playable video game levels by proposing a generate-then-repair framework that uses a GAN for initial generation and a mixed-integer linear program with playability constraints for repair, resulting in diverse, playable levels that capture spatial relationships from human-authored examples.
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.