Controllable Procedural Content Generation via Constrained Multi-Dimensional Markov Chain Sampling.

Sam Snodgrass, Santiago OntañónIJCAI 2016 · OpenReview

Abstract

Statistical models, such as Markov chains, have recently started to be studied for the purpose of Procedural Content Generation (PCG). A major problem with this approach is controlling the sampling process in order to obtain output satisfying some desired constraints. In this paper we present three approaches to constraining the content generated using multi-dimensional Markov chains: (1) a generate and test approach that simply resamples the content until the desired constraints are satisfied, (2) an approach that finds and resamples parts of the generated content that violate the constraints, and (3) an incremental method that checks for constraint violations during sampling. We test our approaches by generating maps for two classic video games, Super Mario Bros. and Kid Icarus.

Introduction

Procedural Content Generation (PCG) typically faces a trade-off between constructive, constraint-based methods and statistical learning methods. While constructive methods ensure playability through strict rules, they often lack the organic "feel" of human-designed levels. Conversely, statistical methods like Multi-Dimensional Markov Chains (MdMCs) excel at mimicking aesthetics by learning from existing data but frequently produce unplayable "gibberish" because they lack global control mechanisms.

Tile-based representation of a Super Mario Bros. level used for Markov chain training.

This paper addresses this gap by introducing a "control layer" over the MdMC sampling process. By predicting the next tile in a grid based on its neighbors, MdMCs can recreate the style of games like Super Mario Bros., but they require additional algorithmic strategies to enforce specific constraints, such as ensuring a path exists from start to finish or maintaining a specific enemy density.

Methods for Constrained Sampling

The authors propose three distinct strategies to enforce constraints during the generation process:

  1. Generate and Test (G+T): This baseline approach generates a complete map and evaluates it against constraints. If the map fails, it is discarded, and the process restarts. While simple, it is computationally inefficient for complex constraint sets.
  2. Violation Location Resampling (VLR): This "surgical" method identifies specific regions within a generated map that violate constraints—for instance, a jump that is too wide for the player. The algorithm then resamples only the problematic tiles, iterating until the local cost is minimized.
  3. Incremental Sampling (IS): This approach builds the map section by section, verifying that each segment satisfies local constraints before proceeding. If a violation is detected, the current section is resampled immediately, preventing errors from propagating.
A generated Kid Icarus level with a constraint violation highlighted for resampling.

A key distinction in these methods is the use of Location-Aware Constraints, which provide the specific coordinates of violations, enabling the targeted repairs used in VLR.

Experimental Setup and Datasets

The models were trained and evaluated using levels from two NES classics:

  • Super Mario Bros. / The Lost Levels: 16 horizontal, linear maps.
  • Kid Icarus: 6 vertical maps.

Kid Icarus presents a significant challenge for statistical samplers due to its verticality and the precise platform placement required for playability.

Key Results and Insights

The integration of constraints proved transformative, particularly for more difficult datasets. In Kid Icarus, where a baseline MdMC produced 0% playable maps, the constrained approaches achieved 94-100% playability.

  • Efficiency: VLR and IS significantly outperformed G+T in terms of sampling efficiency. In Mario tests, G+T required sampling over 75 sections on average to find a valid map, whereas VLR and IS required only 21-23 sections.
  • Style Preservation: Importantly, the constraints did not overwrite the learned probabilities of the Markov chain. The resulting levels maintained the aesthetic "feel" of the original training data while meeting all functional requirements.
  • Locality: The success of VLR highlights that most generation errors are local. Fixing a broken jump in isolation is often more effective than restarting the entire generation process.

Limitations and Future Work

While effective, these algorithms can occasionally encounter "local minima" where tight or conflicting constraints prevent convergence within a set number of resamples. Additionally, the optimal choice between VLR and IS appears to depend on the game's structural orientation (horizontal vs. vertical).

Future research will explore more complex, non-linear environments like Lode Runner and investigate aesthetic or "fun" constraints that go beyond basic playability.

Summary updated

Abstract

Statistical models, such as Markov chains, have recently started to be studied for the purpose of Procedural Content Generation (PCG). A major problem with this approach is controlling the sampling process in order to obtain output satisfying some desired constraints. In this paper we present three approaches to constraining the content generated using multi-dimensional Markov chains: (1) a generate and test approach that simply resamples the content until the desired constraints are satisfied, (2) an approach that finds and resamples parts of the generated content that violate the constraints, and (3) an incremental method that checks for constraint violations during sampling. We test our approaches by generating maps for two classic video games, Super Mario Bros. and Kid Icarus.
BibTeX
@inproceedings{snodgrass2016controllable,
  author = {Sam Snodgrass and Santiago Ontañón},
  title = {{Controllable Procedural Content Generation via Constrained Multi-Dimensional Markov Chain Sampling.}},
  booktitle = {IJCAI},
  year = {2016},
  url = {https://openreview.net/forum?id=XPBCzOdzPuo},
}
Figure