Video Game Level Repair via Mixed Integer Linear Programming

Video Game Level Repair via Mixed Integer Linear Programming

The automatic generation of video game levels poses several challenges. New levels must be aesthetically appealing, and at the same time playable. A recent paper proposes a generate-then-repair approach for responding to both problems.

Firstly, generative adversarial networks are used to create levels stylistically similar to human-created ones. Then, they are repaired to be playable using a mixed-integer linear program with encoded playability constraints. For example, in platform games, such as The Legend of Zelda, nodes corresponding to grind cells must contain exactly one type of object, and the player needs to be able to reach the key object.

The main component of the framework is a metric which allows minimizing the number of edits needed to make a level playable. The results show that diverse playable levels with an aesthetic appeal may be generated from several examples created by humans.

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.

Link: https://arxiv.org/abs/2010.06627