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.
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.
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