Return to Dr. Jacob Schrum's Homepage

A Hybrid Encoding For Large Scale Pattern Generation Applied to Video Game Levels: CPPN Then Direct To GAN

This page presents research in Procedural Content Generation via Machine Learning applied to video game level creation for Mario and Legend of Zelda. Specifically, individual level segments are created using a Generative Adversarial Network trained to emulate existing levels. Then evolution is used to combine GAN-generated segments into complete levels.

Three approaches are used to evolve large levels. The basic control approach based on previous work is called Direct2GAN: instead of evolving one vector of latent inputs to the GAN, a longer vector of many latent inputs is evolved, so each vector can produce a separate segment. A new approach developed through collaboration with Sebastian Risi and Vanessa Volz when attending Dagstuhl Seminar 19511 allows for evolution of large cohesive patterns of level segments, and is called CPPN2GAN: Compositional Pattern Producing Networks take segment locations (coordinates) as input and produce latent vectors that are then sent to a GAN to create a level segment. The locality in the latent space and the tendency of CPPNs to produce symmetric and repeating patterns means CPPN2GAN levels have gradual style transitions and appealing global patterns in contrast to the chaos of Direct2GAN. Later work by my SCOPE students Ben Capps and Kirby Steckel developed a hybrid approach named CPPNThenDirect2GAN that has the benefits of both approaches: The population is initialized with CPPNs that generate levels like CPPN2GAN. However, a mutation operation can be used to discard the CPPN after using it to generate the latent vectors required for the Direct2GAN representation. Thus, the population can contain both CPPNs and directly encoded vectors, allowing for a wider variety of levels to be generated.

This research makes use of the MM-NEAT software package to evolve both the CPPNs and real-valued latent vectors. All GANs used in this study were trained on data from the Video Game Level Corpus. The focus of the study is on how the genome encoding affects the quality of the levels discovered by the Quality Diversity Evolutionary Algorithm MAP-Elites (Multidimensional Archive of Phenotypic Elites).

MAP-Elites discovers a diversity of potential solutions based on dimensions of variation used by the archive. Different dimensions result in different binning schemes for the archive. Two binning schemes were used with each game. Only one level can occupy any bin, so only the best level is kept. In each game, levels with longer optimal solution paths (as determined by A*) are deemed to be of higher quality.
  • Zelda
    • Wall/Water/Rooms
      • Wall: Percentage of floor space occupied by wall obstacles (divided into 10% chunks)
      • Water: Percentage of floor space occupied by water obstacles (divided into 10% chunks)
      • Rooms: Number of reachable rooms out of 25 (5 by 5 grid)
    • Distinct/Backtracking/Rooms
      • Distinct: Number of distinct rooms our of 25 (5 by 5 grid)
      • Backtracking: Number of times a previously visited room is revisited in the solution path out of 25 (5 by 5 grid)
      • Rooms: Number of reachable rooms out of 25 (5 by 5 grid)
  • Mario
    • Decoration/Space Coverage/Leniency
      • Decoration: Percentage of tiles that are decorative (divided into 10% chunks)
      • Space Coverage: Percentage of tiles that are not empty (divided into 10% chunks)
      • Leniency: Average leniency value of all tiles (negative values are harder, positive values easier; split into 5 negative and 5 non-negative bins)
    • Distinct/Alternating Space Coverage/Alternating Decoration
      • Distinct: Number of distinct segments out of 10
      • Alternating Space Coverage: Sum of changes in space coverage between adjacent segments (divided into 10 bins)
      • Alternating Decoration: Sum of changes in decoration between adjacent segments (divided into 10 bins)

Appendix

This PDF appendix contains various results figures not available in our paper describing this research.

Example CPPNThenDirect2GAN Lineage For Zelda

Here is a short video showing off how a lineage transitions from CPPN2GAN to Direct2GAN throughout the course of evolution.

Zelda: Wall/Water/Rooms: Direct2GAN

These Zelda levels were generated from the Direct2GAN encoding when using the Wall/Water/Rooms binning scheme in MAP Elites. White X marks indicate spaces that were visited in the process of finding the shortest path through the dungeon, which is a path made of red X marks. Dungeons with no red path were unbeatable. Rooms with a magenta X on them are unreachable.

Zelda: Wall/Water/Rooms: CPPN2GAN

These Zelda levels were generated from the CPPN2GAN encoding when using the Wall/Water/Rooms binning scheme in MAP Elites. White X marks indicate spaces that were visited in the process of finding the shortest path through the dungeon, which is a path made of red X marks. Dungeons with no red path were unbeatable. Rooms with a magenta X on them are unreachable.

Zelda: Wall/Water/Rooms: CPPNThenDirect2GAN

These Zelda levels were generated from the CPPNThenDirect2GAN encoding when using the Wall/Water/Rooms binning scheme in MAP Elites. White X marks indicate spaces that were visited in the process of finding the shortest path through the dungeon, which is a path made of red X marks. Dungeons with no red path were unbeatable. Rooms with a magenta X on them are unreachable.

Zelda: Distinct/Backtracking/Rooms: Direct2GAN

These Zelda levels were generated from the Direct2GAN encoding when using the Distinct/Backtracking/Rooms binning scheme in MAP Elites. White X marks indicate spaces that were visited in the process of finding the shortest path through the dungeon, which is a path made of red X marks. Dungeons with no red path were unbeatable. Rooms with a magenta X on them are unreachable.

Zelda: Distinct/Backtracking/Rooms: CPPN2GAN

These Zelda levels were generated from the CPPN2GAN encoding when using the Distinct/Backtracking/Rooms binning scheme in MAP Elites. White X marks indicate spaces that were visited in the process of finding the shortest path through the dungeon, which is a path made of red X marks. Dungeons with no red path were unbeatable. Rooms with a magenta X on them are unreachable.

Zelda: Distinct/Backtracking/Rooms: CPPNThenDirect2GAN

These Zelda levels were generated from the CPPNThenDirect2GAN encoding when using the Distinct/Backtracking/Rooms binning scheme in MAP Elites. White X marks indicate spaces that were visited in the process of finding the shortest path through the dungeon, which is a path made of red X marks. Dungeons with no red path were unbeatable. Rooms with a magenta X on them are unreachable.

Mario: Decoration/Space Coverage/Leniency: Direct2GAN

These Mario levels were generated from the Direct2GAN encoding when using the Decoration/Space Coverage/Leniency binning scheme in MAP Elites. Blue X marks indicate spaces that were visited in the process of finding the shortest path through the level, which is a path made of red X marks. Levels with no red path were unbeatable.

Mario: Decoration/Space Coverage/Leniency: CPPN2GAN

These Mario levels were generated from the CPPN2GAN encoding when using the Decoration/Space Coverage/Leniency binning scheme in MAP Elites. Blue X marks indicate spaces that were visited in the process of finding the shortest path through the level, which is a path made of red X marks. Levels with no red path were unbeatable.

Mario: Decoration/Space Coverage/Leniency: CPPNThenDirect2GAN

These Mario levels were generated from the CPPNThenDirect2GAN encoding when using the Decoration/Space Coverage/Leniency binning scheme in MAP Elites. Blue X marks indicate spaces that were visited in the process of finding the shortest path through the level, which is a path made of red X marks. Levels with no red path were unbeatable.

Mario: Distinct/Alternating Space Coverage/Alternating Decoration: Direct2GAN

These Mario levels were generated from the Direct2GAN encoding when using the Distinct/Alternating Space Coverage/Alternating Decoration binning scheme in MAP Elites. Blue X marks indicate spaces that were visited in the process of finding the shortest path through the level, which is a path made of red X marks. Levels with no red path were unbeatable.

Mario: Distinct/Alternating Space Coverage/Alternating Decoration: CPPN2GAN

These Mario levels were generated from the CPPN2GAN encoding when using the Distinct/Alternating Space Coverage/Alternating Decoration binning scheme in MAP Elites. Blue X marks indicate spaces that were visited in the process of finding the shortest path through the level, which is a path made of red X marks. Levels with no red path were unbeatable.

Mario: Distinct/Alternating Space Coverage/Alternating Decoration: CPPNThenDirect2GAN

These Mario levels were generated from the CPPNThenDirect2GAN encoding when using the Distinct/Alternating Space Coverage/Alternating Decoration binning scheme in MAP Elites. Blue X marks indicate spaces that were visited in the process of finding the shortest path through the level, which is a path made of red X marks. Levels with no red path were unbeatable.

Associated Publications

Peer-Reviewed Journal Articles

Peer-Reviewed Conference Publications

Extended Abstracts

Technical Reports

Dagstuhl Reports

Undergraduate Poster Presentations Supervised

Associated Movies and Images

Miscellaneous Content

  • Summer 2021: Quality Diversity and Creative Divergent Search: SCOPE Research Presentation made by my SCOPE Summer research students to present to other SCOPE students
  • Fall 2020: Procedural Content Generation for Games with Generative Adversarial Networks: Presentation for the Games AI Research Group at Queen Mary University of London (video)
  • Fall 2020: Interactively Evolving Video Game Levels with Generative Adversarial Networks: 403 Lecture for Math and CS Department
  • Fall 2020: Evolving Mega Man Levels with Generative Adversarial Networks: Virtual SCOPE Open House Website
  • Fall 2020: Evolving Lode Runner Levels with Generative Adversarial Networks: Virtual SCOPE Open House Website
  • Summer 2020: Generating Video Game Levels Using AI: SCOPE Research Presentation made by my SCOPE Summer research students to present to other SCOPE students
  • Summer 2019: Playing and Creating Games With Deep Neural Networks: "Mad Science Monday" presentation made by my SCOPE Summer research students to present to other SCOPE students
  • Fall 2018: Evolutionary Computation Applied to Digital Entertainment and the Arts, poster presented at the President's Appreciation Celebration for Southwestern University donors.
  • Fall 2018: Evolving Mario Levels in the Latent Space of a Deep Convolutional Generative Adversarial Network: presented to Southwestern University students as a 107 Lecture.
  • Summer 2018: The machines have taught themselves to make Mario levels, article in Fast Company about my recent GECCO 2018 paper on generating levels for Super Mario Bros.
  • Spring 2018: Bored with your video game? Artificial intelligence could create new levels on the fly, article in Science about my recent GECCO 2018 paper on generating levels for Super Mario Bros.
  • Spring 2018: Doom and Super Mario could be a lot tougher now AI is building levels, article in The Register about my recent GECCO 2018 paper on generating levels for Super Mario Bros.
    • Last Updated: 5/2/2022