Multi-Objective level generator generation with Marahel

Ahmed Khalifa, Julian Togelius

Abstract

This paper introduces a new system to design constructive level generators by searching the space of constructive level generators defined by the Marahel language. We use NSGA-II, a multi-objective optimization algorithm, to search for generators for three different problems: Binary, Zelda, and Sokoban. We restrict the representation to a subset of the Marahel language to push the evolution toward finding more efficient generators. The results show that the evolved generators achieve strong performance across most fitness functions for these three problems. However, in Zelda and Sokoban, the generators tend to depend on the initial state rather than building the map from scratch.

Introduction

Designing procedural content generators (PCG) that consistently output high-quality, diverse game levels is a significant challenge. While search-based PCG can produce excellent results, it is often computationally expensive at runtime. Conversely, constructive generators—such as rule-based systems or Cellular Automata—are fast but typically require extensive human expertise to author. This paper explores "Procedural Procedural Level Generation Generation": the automated design of fast, constructive level generators by searching the space of scripts defined by the Marahel language.

Methodology

The system utilizes Grammatical Evolution to evolve scripts in Marahel, a language designed for constructive level generation. To maintain interpretability and manage the search space, scripts are restricted to a maximum of five "explorers" (rulesets for map modification) and one initialization explorer. The chromosome is mapped to a Marahel script using the Tracery grammar engine.

Optimization is performed using NSGA-II, a multi-objective evolutionary algorithm. The fitness of a generator is determined by sampling 50 levels and averaging their scores across multiple game-specific objectives, such as connectivity, path length, and entity counts. This approach allows the system to navigate trade-offs between conflicting goals, such as playability versus complexity.

Results and Discussion

The evolutionary process demonstrated clear convergence across all three domains. As shown in the optimization curves, the number of Pareto fronts decreases significantly over generations, indicating that the population is moving toward a stable set of non-dominated solutions.

Convergence of NSGA-II across the Binary, Zelda, and Sokoban problems, showing the reduction in the number of fronts over 2000 generations.

In the Binary problem, the algorithm successfully identified generators that produce fully connected maps with high path length improvement. The Pareto front analysis reveals a clear boundary where the evolved generators significantly outperform random sampling, effectively balancing the number of regions (connectivity) with path length.

Pareto front for the Binary problem, illustrating the trade-off between connectivity (Number of Regions) and Path Length Improvement compared to random samples.

For more complex games like Zelda and Sokoban, the evolved generators often adopted an "eraser" strategy. Rather than building from scratch, they learned to intelligently modify the initial random state to satisfy constraints. However, achieving 100% playability remained challenging due to the "cascading" nature of fitness functions. In these games, a level must meet basic structural requirements (like having exactly one player and one key) before higher-level metrics like solution length can be measured, creating a noisy fitness landscape.

Conclusion and Future Work

The proposed system successfully evolves interpretable, constructive level generators using Marahel. While the current constraints on script size favor readability, they may limit the complexity of the generated logic for advanced puzzles. Future work will explore relaxing these constraints, removing the initialization explorer to force generation from empty maps, and refining fitness aggregation methods to improve the consistency of generated playable content.

Summary updated

Abstract

This paper introduces a new system to design constructive level generators by searching the space of constructive level generators defined by Marahel language. We use NSGA-II, a multi-objective optimization algorithm, to search for generators for three different problems (Binary, Zelda, and Sokoban). We restrict the representation to a subset of Marahel language to push the evolution to find more efficient generators. The results show that the generated generators were able to achieve good performance on most of the fitness functions over these three problems. However, on Zelda and Sokoban, they tend to depend on the initial state than modifying the map.
BibTeX
@inproceedings{khalifa2020multi,
  author = {Ahmed Khalifa and Julian Togelius},
  title = {{Multi-Objective level generator generation with Marahel}},
  booktitle = {FDG},
  year = {2020},
  doi = {10.1145/3402942.3409606},
}
Figure