Procedural Content Generation using Neuroevolution and Novelty Search for Diverse Video Game Levels

Michael Beukman, Christopher W. Cleghorn, Steven James

Abstract

Procedurally generated video game content has the potential to drastically reduce the content creation budget of game developers and large studios. However, adoption is hindered by limitations such as slow generation, as well as low quality and diversity of content. We introduce an evolutionary search-based approach for evolving level generators using novelty search to procedurally generate diverse levels in real time, without requiring training data or detailed domain-specific knowledge. We test our method on two domains, and our results show an order of magnitude speedup in generation time compared to existing methods while obtaining comparable metric scores. We further demonstrate the ability to generalise to arbitrary-sized levels without retraining.

Introduction

Procedural Content Generation (PCG) is a cornerstone of modern game development, promising infinite replayability and significantly reduced production costs. Despite its potential, current PCG techniques often struggle with a "trilemma" of trade-offs:

  1. Search-based methods (e.g., Genetic Algorithms) produce high-quality, solvable levels but are computationally expensive, often requiring a new search process for every level generated.
  2. Machine Learning methods (e.g., GANs) offer rapid generation but require massive, high-quality human-authored datasets which may not exist for new games.
  3. Reinforcement Learning (RL) can learn to build levels but often requires complex, game-specific reward engineering and can suffer from low output diversity.

To address these challenges, we propose PCGNN (Procedural Content Generation using Neuroevolution and Novelty Search). PCGNN shifts the focus from searching for a single level to searching for a generator—a neural network capable of producing an infinite variety of levels. This approach provides the speed of ML methods without the need for training data, while maintaining the robustness of search-based methods.

Methodology

The core of PCGNN is an offline evolution phase using NeuroEvolution of Augmenting Topologies (NEAT). Instead of optimizing for a single fitness score, we employ Novelty Search. This encourages the evolution of neural networks that produce levels distinct from those already discovered in the population, effectively exploring the "behavior space" of level design.

During evolution, the fitness function evaluates three primary criteria:

  • Solvability: An A* agent must be able to complete the generated level.
  • Novelty: The generator's output must be significantly different from the outputs of other generators in the archive.
  • Intra-Generator Novelty: A single network must demonstrate the ability to produce diverse levels when provided with different random noise seeds.

Online Generation

Once a high-performing generator is evolved, it is deployed for real-time use. The network operates as a "sliding window" generator. It takes a local context (the surrounding tiles) and a noise seed as input to predict the next tile in the sequence. Because the heavy computational work is performed during the offline evolution phase, generating a new level online requires only a series of rapid neural network forward passes.

Experimental Setup

We evaluated PCGNN on two distinct 2D tilemap environments:

  1. Maze: A grid-based environment requiring a path from start to finish.
  2. Super Mario Bros.: A simplified platformer environment featuring ground tiles, pipes, and enemies (Goombas).

Notably, PCGNN requires no pre-existing level data. It learns the underlying logic of these domains from scratch by interacting with the game rules and simulators during the evolution process.

Key Results

Performance and Speed

PCGNN achieved an order-of-magnitude speedup in generation time compared to traditional search and RL methods. For a standard Maze level, PCGNN generated content in approximately 0.002 seconds. In comparison, RL-based methods took ~1.6 seconds, and direct search methods (DirectGA) required ~7.4 seconds. This makes PCGNN highly suitable for real-time, on-the-fly level generation during gameplay.

Solvability and Scaling

In the Maze domain, PCGNN maintained 100% solvability even as the target level size increased. Direct search methods, by contrast, saw solvability drop to zero as the search space became too large for the algorithm to navigate effectively.

Generalization

Because the generator utilizes a local context window rather than a global map, it is inherently size-agnostic. A network evolved on a small 14x14 grid can successfully generate levels as large as 2000x2000 without any additional training or fine-tuning. This demonstrates true scale-invariance, a significant advantage for creating expansive game worlds.

Discussion and Future Work

While PCGNN offers significant advantages in speed and diversity, it faces limitations regarding global coherence. Because the network only perceives a local window, it may struggle with long-distance dependencies, such as placing a key at the beginning of a level that is required for a door at the very end. Additionally, while the generated Mario levels are functional, they do not yet match the aesthetic nuance of hand-crafted levels.

Future research will focus on incorporating more sophisticated fitness functions to improve aesthetic quality and exploring adaptive PCG. By using player behavior as an input to the generator network, we aim to create levels that dynamically adjust their challenge and structure in real-time to suit individual player styles.

Summary updated

Abstract

Procedurally generated video game content has the potential to drastically reduce the content creation budget of game developers and large studios. However, adoption is hindered by limitations such as slow generation, as well as low quality and diversity of content. We introduce an evolutionary search-based approach for evolving level generators using novelty search to procedurally generate diverse levels in real time, without requiring training data or detailed domain-specific knowledge. We test our method on two domains, and our results show an order of magnitude speedup in generation time compared to existing methods while obtaining comparable metric scores. We further demonstrate the ability to generalise to arbitrary-sized levels without retraining.
BibTeX
@inproceedings{beukman2022procedural,
  author = {Michael Beukman and Christopher W. Cleghorn and Steven James},
  title = {{Procedural Content Generation using Neuroevolution and Novelty Search for Diverse Video Game Levels}},
  booktitle = {GECCO},
  year = {2022},
  doi = {10.1145/3512290.3528701},
}
Figure