Video Game Level Repair via Mixed Integer Linear Programming


  • Hejia Zhang University of Southern Californi
  • Matthew C. Fontaine University of Southern California
  • Amy K. Hoover New Jersey Institute of Technology
  • Julian Togelius New York University
  • Bistra Dilkina University of Southern California
  • Stefanos Nikolaidis University of Southern Californi



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.




How to Cite

Zhang, H., Fontaine, M., Hoover, A., Togelius, J., Dilkina, B., & Nikolaidis, S. (2020). Video Game Level Repair via Mixed Integer Linear Programming. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 16(1), 151-158.