TL;DR
This paper introduces a system to automatically generate level generators for 2D games by evolving scripts written in the Marahel language. Using the NSGA-II multi-objective optimization algorithm, the authors successfully evolve fast, constructive generators for three distinct game problems (Binary mazes, Zelda, and Sokoban). While the system produces highly interpretable generators, the evolved scripts for more complex games tend to act as clever modifiers of initial random states rather than building levels entirely from scratch.
What Problem Does This Paper Address?
Designing procedural content generators (PCG) that consistently output high-quality, diverse game levels is notoriously difficult. While search-based PCG (using algorithms to find a good level) can produce great results, it is computationally slow at runtime. Constructive generators (rule-based systems like Cellular Automata) are incredibly fast, but require significant human expertise and trial-and-error to design the rules.
This paper tackles the problem of "Procedural Procedural Level Generation Generation"—automatically designing fast, constructive level generators. By searching the space of possible generator scripts, the authors aim to find rule sets that can instantly produce playable, interesting levels for 2D games without requiring a human to manually author the generation logic.
Methods
The authors use Grammatical Evolution (a form of genetic programming) to evolve scripts written in Marahel, a constructive level generator description language. To keep the search space manageable and the resulting generators human-readable, they restrict the scripts to a maximum of five "explorers" (rulesets that traverse and modify the map) plus one initialization explorer.
The chromosome (an array of 102 integers) is mapped to a Marahel script using the Tracery grammar engine. To optimize the generators, they use NSGA-II, a multi-objective evolutionary algorithm. Because they are evaluating a generator and not a single level, the fitness of a chromosome is calculated by sampling 50 levels from it and averaging the scores across multiple game-specific objectives (e.g., number of players, path length, number of enemies).
Datasets
The paper does not use standard static datasets for training. Instead, it evaluates the generated generators on three distinct 2D game environments adapted from the PCGRL (Procedural Content Generation via Reinforcement Learning) framework:
- Binary: A simple 2D maze where the goal is to create a fully connected map with a long shortest path.
- Zelda: A dungeon system port of The Legend of Zelda requiring one player, one key, one door, and a minimum path length.
- Sokoban: A puzzle game requiring a playable level with matching crates and targets, and a minimum solution length.
Key Insights and Ideas
- Interpretability is a major advantage: Because the generators are evolved as Marahel scripts, the resulting logic is human-readable. Designers can easily debug, understand, or manually tweak the evolved rules, which is a significant advantage over "black box" neural network generators.
- Generators as "Erasers": For complex games like Zelda, the evolved generators often learned to rely heavily on the initial random state of the map. Instead of building a level from an empty grid, they acted as "erasers," intelligently removing or substituting tiles to carve out playable paths.
- Cascading fitness functions create rough landscapes: In games like Sokoban and Zelda, a level is only playable (and thus can only have a measurable "solution length") if it meets strict prerequisites, like having exactly one player, one key, and one door. This creates a highly noisy fitness landscape, making it difficult for the evolutionary algorithm to satisfy all constraints simultaneously.
Key Results
- Binary Problem: The algorithm successfully found generators capable of producing fully connected mazes with significantly increased path lengths (an average increase of 18 tiles), resulting in interesting, loopy dungeon layouts.
- Zelda and Sokoban: The algorithm struggled to find a single "perfect" generator that satisfied all constraints 100% of the time. For example, the best Zelda generator achieved high fitness for having the right number of players (0.79) and doors (0.70), but scored low on solution length (0.14) because generating a strictly playable level from random noise is difficult.
- Pareto Front Exploration: The multi-objective approach successfully mapped the trade-offs between conflicting goals. For instance, in Zelda, the algorithm revealed an inverse relationship between the number of enemies and the likelihood of successfully spawning exactly one player.
Limitations and Future Work
- Limitations: The strict constraints placed on the Marahel scripts (limiting size to force interpretability) likely prevented the algorithm from finding generators that could perfectly satisfy all fitness functions for the more complex games. Additionally, using the average fitness of 50 sampled levels sometimes biased the evolution toward consistently mediocre generators rather than those that occasionally produce brilliant levels.
- Future Work: The authors suggest experimenting with less restricted evolution to see if larger scripts yield better results. They also propose removing the "initialization explorer" to force the generator to build from an empty map rather than just modifying random noise. Finally, they recommend exploring different aggregation operators (like "mixmin") and using improvement-based fitness functions rather than absolute target values.
Summary updated