Evolutionary Level Repair CCS: Applied computing Computer games CCS: Theory of computation Evolutionary algorithms

Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis, Ahmed Khalifa · 2025

Read Evolutionary Level Repair CCS: Applied computing Computer games CCS: Theory of computation Evolutionary algorithms by Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis, Ahmed Khalifa (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-19359.txt.

Introduction

Bhaumik and three co-authors fix broken game levels with search. Their 2025 paper tackles levels that look right but cannot be played. A fix may mean making spots reachable or the goal reachable at all. The repair should also change as little as it can.

The team tests evolution-based search, plus methods that keep varied fixes. Their test levels come from a learning-based generator that makes stylish but often broken stages. The search then patches them into working shape. Results were strong across the trials. Pairing a maker with a fixer, the authors argue, is a strong path for game building tools.

Catalog record

CREATORDebosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis, Ahmed Khalifa
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-19359

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Evolutionary Level Repair CCS: Applied computing Computer games CCS: Theory of computation Evolutionary algorithms Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis, Ahmed Khalifa Abstract . We address the problem of game level repair, which consists of taking a designed but non-functional game level and making it functional. This might consist of ensuring the completeness of the level, reachability of objects, or other performance characteristics. The repair problem may also be constrained in that it can only make a small number of changes to the level. We investigate search-based solutions to the level repair problem, particularly using evolutionary and quality-diversity algorithms, with good results. This level repair method is applied to levels generated using a machine learning-based procedural content generation (PCGML) method that generates stylistically appropriate but frequently broken levels. This combination of PCGML for generation and search-based methods for repair shows great promise as a hybrid procedural content generation (PCG) method. 1. Introduction Many types of game content, such as levels, exhibit a dual nature where both visual aesthetics and functionality are important. The way the content looks is important, not only for the visual appeal but also for what it communicates about how it can be played. But functionality is, in many games, even more crucial; it determines what is possible to do in the game and what leads to success and failure. For example, a Super Mario Bros level gives a sense of thematic unity, foreshadows challenges, and gently tells the player where to go. Still, it also defines the challenges that need to be overcome. The fusion of visual aesthetics and functionality is central to what a game level is, but functionality is more important. While a playable level that looks like a mess is still passable game content, a beautiful but non-completable level is game-breaking. Training (or fine-tuning) a self-supervised learning model of the type usually used for visual data can therefore yield a model that outputs pretty but broken levels. For example, training an autoencoder on a set of levels from the classic puzzle platformer Lode Runner ( Bhaumik et al. 2021 ) results in a neural network that generates nice-looking levels that mostly cannot be solved. After training GANs to generate Mario levels, most of the naively sampled content is not functional ( Volz et al. 2018 ) . Many machine learning models can not, on their own, ensure functionality. So, how can you generate content that both looks good and plays well? One approach is to train a model on existing levels using self-supervised methods, and then use some kind of search algorithm to search the learned space for good content. This is the general approach of latent variable evolution ( Bontrager et al. 2018 ; Volz et al. 2018 ) and latent variable illumination ( Fontaine et al. 2021 ) . Still, this approach introduces certain constraints on the machine learning method, notably that it has a latent space, which might exclude some ML methods. Even after using these methods and restricting the latent search around the broken level, there is still a chance that the space might not contain a repaired version of it. This reduces the learned latent space to a smaller subset and discards a huge part of the search space because of small mistakes in it, which causes the method to have less creative freedom. Another approach is to generate and then repair. The problem of level repair then becomes one of making sure the level functions correctly or follows some defined constraints (e.g., that it is playable and contains the appropriate challenges) while maintaining the overall visual aesthetics of the level. Preserving the visual aesthetics can intuitively be achieved by limiting the number of changes made. Different work has combined constraint solving ( Bazzaz and Cooper 2024 ; Cooper 2022 ) , linear programming ( Zhang et al. 2020 ) , machine learning models ( Jain et al. 2016 ; Chen et al. 2020 ) , and search-based methods ( Liapis et al. 2013 ; Cooper and Sarkar 2020 ) with PCGML to battle the functionality issue. Inspired by the “generate then repair” we are trying to combine the advantage of machine learning methods with evolutionary methods to repair unplayable levels. (a) Maximum Fitness during optimization. (b) Quality diversity score of the MAP-Elites algorithm. Figure 1 . The average performance for all four algorithms with 95% confidence interval over 200 runs. 2. Methods Repairing broken game levels is not a straightforward task, especially when the goal is to make the level functional. A good repair function will try to make a small number of changes to the existing content to make it playable. If the repaired level differs significantly from the visual aesthetic of the given level, it is generally not a good repair. At the same time, a good evaluation metric is required to measure the changes made by the repair function and guide the process in the right direction. For repairs, we use two different algorithms: \mu+\lambda Evolution Strategy (ES) ( Beyer 2007 ) for normal optimization and MAP-Elites (ME) ( Mouret and Clune 2015 ) for Quality Diversity. We have selected Lode Runner for this project. Lode Runner levels are of size 32x22 tiles and made of eight different tile types: empty, brick, solid-brick, rope, ladder, gold, enemy, and player. The objective of the game is to collect all the gold in the level without being caught by the enemies. The player can move horizontally on brick tiles and ropes and navigate vertically using ladders. Lode Runner was selected as our domain problem due to its relatively large level, which makes it easy to see when a level looks “noisy”. 2.1. Representation and Operators We use direct representation, where the levels are represented as a 1D array of tiles (flattened representation of the 32x22 level). For modifying the chromosomes, we only use mutation. The mutation operator picks 1 to m (m is the maximum number of modifications at each step) random locations and changes them. The tile values are changed either randomly by selecting any other tile or copying the corresponding tile from the starting level for that location. The probability of which mutation will be applied is determined based on the fitness value. Lower fitness favors random mutation to explore more towards the beginning of the evolution, while higher fitness encourages copy mutation to ensure that the repaired level still looks similar to the starting level. One important note on the mutation is that we removed the ability to erase or add gold tiles or the player tile to force evolution to repair the level by making it connected instead of removing unreachable gold. Finally, the initial population is created by applying random mutations on the starting level. 2.2. Fitness Function and Characteristics In our problem, the fitness function needs to deal with playability and similarity. Both are equally important for a good repair function, also difficult to balance. To improve playability, tiles need to be modified, which affects the similarity score in the opposite direction. To solve this, we are using a cascading elitism ( Togelius et al. 2007 ) fitness function. This encourages evolution to prioritize playability first, then it tries

Read the complete text