Video game level repair via mixed integer linear programming

Hejia Zhang, Matthew C. Fontaine, Amy K. Hoover, Julian Togelius, Bistra Dilkina, Stefanos Nikolaidis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.*

Original languageEnglish (US)
Title of host publicationProceedings of the 16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020
EditorsLevi Lelis, David Thue
PublisherThe AAAI Press
Pages151-158
Number of pages8
ISBN (Electronic)9781577358497
StatePublished - 2020
Event16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020 - Virtual, Online
Duration: Oct 19 2020Oct 23 2020

Publication series

NameProceedings of the 16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020

Conference

Conference16th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2020
CityVirtual, Online
Period10/19/2010/23/20

All Science Journal Classification (ASJC) codes

  • Visual Arts and Performing Arts
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Video game level repair via mixed integer linear programming'. Together they form a unique fingerprint.

Cite this