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

    ASJC Scopus subject areas

    • 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