Procedural content generation via Machine Learning (PCGML) creates game levels from examples. PCGML for platformers with physics-based player movement generally has not guaranteed the reachability of goals, relying on post-generation filtering approaches or game-specific heuristic rules. In contrast, constraint-based PCGML can provide gameplay guarantees, but has typically been applied to games with simple grid-based movement. In this work, we present a constraint-based PCGML approach for platformers with physics-based player movement that guarantees playability and provides design controllability. Our approach exhaustively precomputes all possible player movement states in example tile-based platformer levels. It extracts metatiles containing local state information and uses them in constraint-based level generation that ensures legal tile neighbors and consistent movement state transitions. The approach can ensure constraints on gameplay, such as the reachability of goals, guaranteeing level playability, and other elements like platforms and bonuses. It can also incorporate other designer-controllable constraints.
Procedural content generation via Machine Learning (PCGML) is an approach to game level generation that learns from existing levels (Summerville et al. 2018). By learning to generate unique levels from hand-designed ones, PCGML methods can complement and support human designers’ creativity. They can generate new ideas that match well with the designer’s style and needs, helping with brainstorming or refinement of a level design.
While researchers have developed PCGML approaches to
generate levels for platformer games, these systems typically
do not provide guarantees about the reachability of level
elements, such as goals, and thus whether the resulting
levels are playable. They often rely on post-generation filtering
and playability heuristics and start over if the level is not
playable
Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Beyond playability, PCGML methods often struggle to
guarantee other attributes of the resulting levels such as the
distribution of design elements or the reachability of
collectible items. Many PCGML methods rely on neural
networks, probabilistic graphical models, and other similar
approaches that are not easily interpretable or controllable.
Designers may need to iteratively re-train, often guessing what
might help the system achieve their desired vision
In this paper, we propose an approach to constraint-based
PCGML for platformers with physics-based player
movement that allows reachability and other designer-controllable
constraints. Our approach precomputes all possible player
states, based on the game’s physics and movement rules,
in the training levels, and associates the tiles with those
states and the transitions between them to create metatiles.
By tracking and constraining state transitions when
generating levels, we ensure reachability of specific tiles like goals
and collectibles. We also include tile neighbor constraints
inspired by Wave Function Collapse (WFC)
We applied this level generation technique to a simple
tile-based platformer game we created called Turtle Loves
Pizza (TLP), shown in Figure 1. We trained on simplified
versions of Super Mario Bros. levels from the Video Game
Level Corpus (VGLC)
We applied two types of reachability constraints: playability, whether the generated level contains a path from the start to each goal; and usefulness, whether platforms and collectibles in the generated level are reachable and can be used or collected. The ideal generated level should be both useful and playable. We show that our approach can be used to generate playable levels that also meet additional user-specified design constraints including specific level dimensions and the number of certain tile types in the generated level.
The focus of this work is to propose a new technique for generating novel levels from existing ones in platformers. The contributions are (1) a level generation approach which ensures reachability and allows for other controllable constraints using constraint-based PCGML and precomputed player movement and (2) a demonstration of the approach using levels from an established domain with movement rules from a custom platformer game.
PCG for Platformers Many researchers have proposed
and tested methods for generating levels for platformer
games. One line of work used designer-defined libraries
or grammars, often paired with constraints or
optimizations.
Seeking to learn such patterns from training data,
Finally, others have focused on artificial neural network
(ANN) approaches, beginning with
Constraint-based Level Generation Outside of
platformers, researchers have experimented with constraint-based
level generation. In games, this began with the level
design tool SketchaWorld by Smelik et al. (2010), followed
by work by A. Smith et al. (2010; 2011) on generating
puzzle game designs and levels using ASP. As mentioned
above, Tanagra and Launchpad applied constraint solving
to platformer levels
Several released games use versions of Wave Function
Collapse (WFC)
Going beyond previous applications of constraint solving to platformers, our approach learns from existing levels to automatically determine playability constraints, melding ideas from WFC and ASP for dungeon generation with platformer physics modeling.
Precomputation and Sampling Previous work has also
applied extensive or exhaustive computation of gameplay
states. One application of this has been improved runtime
performance.
GOAL 4 GOAL
To generate levels using reachability constraints, we analyze existing playable levels to extract information from each tile and build a set of constraint rules that new levels must satisfy. We organize our method into: (1) enumerating the state graph, (2) extracting the metatiles and constraints, (3) solving the constraints to generate a new level. Here we discuss the generic high-level approach, summarized in Figure 2. Input Our approach takes as input (1) the game’s movement rules and (2) a playable level for training.
The game’s movement rules take an existing player state and an input action and return the resulting state. The player state contains at minimum a position component, a flag for being the start state, and a flag for being a goal state.
Next, we define a few simplifying assumptions about the movement rules in the game. We assume that the player’s movement is deterministic and that the player’s terminal velocity cannot exceed the length of a square tile. Hence, we assume that the movement rules are local: the player’s movement, current state, and next state are only affected by the player’s surrounding 3x3 neighborhood of tiles at each possible state in the level. Thus, we assume that the absolute position of the state and neighborhood does not matter, only the state’s relative position within its local neighborhood. These assumptions are used to extract metatiles which are then used to generate new levels (discussed below).
A valid training level is an existing level, represented as a grid of tile types, with a start tile (which defines the player’s start state), at least one goal tile, and a playable path from start to goal. In this work, we assume all tiles along the outer edge of the level (and none of the interior tiles) are border tiles, which block the player from going out of the level. We also assume that levels themselves are static, meaning tiles will never change positions during gameplay.
State Graph Enumeration The first step in the process is to enumerate the player’s state graph for the input level. We begin with the player’s start state and use the game’s movement rules to exhaustively precompute every reachable state in the level. The transitions in the directed graph represent the player’s ability to move from a source state to a destination state by performing a particular action. The enumerated state graph for a valid input level will always contain a path from the start state to every goal state.
Metatile Extraction After we enumerate the state graph for the input level, we extract the level’s metatiles. A metatile contains a tile type, a graph of all the player’s states within that specific metatile, and the transitions between them. A metatile’s state graph also includes outgoing edges, edges where the destination states are in adjacent metatiles. Each metatile’s graph is a subgraph of the fully enumerated level state graph. Every tile in the input level has a corresponding metatile. When extracting metatiles, each state’s position is offset to be relative to the metatile’s location in the input level. This way, with a level’s metatiles and knowledge of their locations in the input level, the metatiles’ graphs can be re-joined to reconstruct the fully enumerated state graph. Each unique metatile extracted from the input level is stored and assigned a unique ID.
Once we have extracted the set of unique metatiles from the input level, we examine the input level to determine the legal adjacent neighbors for each unique metatile. These are the metatiles that can be placed in each of the 8 possible neighbor positions surrounding each metatile.
At this point we have finished analyzing the input level and have obtained (1) a defined set of metatiles, each containing a unique subgraph of player states and their transitions and (2) the learned adjacency rules for each metatile in the set.
Level Generation Finally, we input the metatiles and their adjacency rules into a constraint solver and use WFC to assemble instances of the metatiles into a new generated level.
During level generation, when a metatile is assigned to a
position in the new level, all of its associated states and
transitions are also placed in the level and offset to the assigned
position. We use a technique similar to one suggested by
To assemble metatiles into a level, we use the following generic constraints:
Size: Levels are rectangular and must satisfy a given width and height, measured in tiles.
Metatile neighbors: Each of the 8 neighbors of a metatile I n p u t L e v e l + + + – + + – + +
must be one of the metatiles that was seen neighboring it
in the same direction in the training level. This is based
on the WFC
Goal reachability: All goal states must be reachable. This ensures playability.
We used the Potassco
To explore our approach, we implemented a tile-based platformer called Turtle Loves Pizza (TLP). The player controls a turtle that can move left and right and jump. The turtle’s (x; y) position is based on its center. The turtle moves smoothly within tiles and can occupy many possible positions within them due to the physics-based movement rules.
Its goal is to traverse the level to collect the pizza at the end.
There are several tile types that can be used in the game: empty tiles that the turtle can move though, block tiles that block the turtle from moving, hazard tiles that kill the turtle when touched, bonus tiles that behave like blocks but give a 1-1 1-2 1-3 534 614 222 500 750 1000 500 750 1000 200 300 400
G e n e tr a e d ? + + z– + + + y– + – 7 16 96 score bonus the first time they are hit from below, a start tile indicating where the turtle begins in the level, and a goal tile that completes the level when touched.
The movement rules in TLP are based on simple physics rules: the turtle’s state has an x and y position and an x and y velocity. For simplicity, we used integers for position and velocity. Jumping sets the y velocity to its maximum upward value, and gravity constantly accelerates the turtle downward in y. Moving left or right happens at a constant x velocity. In addition to position and velocity, each state in TLP has a flag for being a start, a goal, resting on the ground, or dead. Each state also has an indicator for being in contact with a bonus tile that can be collected in its local tile neighborhood, if any; the indicator specifies the cardinal direction of the bonus tile relative to the turtle. Thus, each state can be considered a tuple of (xpos; ypos; xvel; yvel; isstart; isgoal; isdead; isonground; whichbonus).
In order to have interesting input levels, we used
levels from Super Mario Bros. (SMB) from the VGLC
To prepare SMB levels for TLP we made several modifications, including mapping SMB tile types to TLP tile types; adding an additional bottom row of hazard tiles where there were pits in SMB so that the player would be classified as dead after falling into a pit; adding border tiles around the perimeter of the level; defining start and goal tiles, and making minute tile placement adjustments as needed for playability (e.g. removing a tile that Mario can pass through with a special power-up but the turtle cannot).
In addition to the generic constraints discussed above, we used the following constraints to generate levels:
Start and goal tiles: There must be exactly one start tile within the first 10 columns and one goal tile within the last 10 columns.
Other tile counts: The number of block, hazard, and bonus tiles must be within 20% of the number in the ---------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXXXXX---XXX?-----------------------------------?------------------------------- ---------------------?-----------XXXXXXXXXX---XXX?--------------------XXXXXXXXXX---XXX?------------------------------?----------------------------------------------------XX--------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXX--------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXX-----------------------------------------------------------------------------------------------------------------------------!--- -----------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXXX---------------------------------------------X?X-------------X-----XXXXXXXXXXXXX?X---------?---X?X?X---------------------XXXXXXXX ------------------?--?--?-----X?X----------------X-----XXXXXX?X----X?X----------------X-----XXXXXXXX?X---------?---X?X?X---------------------XX---------XX------------XXXXXX-----------------------------------------------------------------------------------------------------------------XX------XXXXXXXX -------------------------------------------------------------------------------------------------------------------------------------XX------XX---------XX-----------XXXXXXX-------------------------------------------------------------------------------------------------------XX--------XX------XXXXXXXX ---------------------------------------------------------------------------------------------------------------------------XX--------XX------XX---------XX-------XX-XXXXXXXX-------------------------------*-----------------------------------------------------------------------XX--------XX------XXXXXXXX ------*--------------------------------------------------------------------------------------------------------------------XX--------XX------XX---------XX-------XXXXXXXXXXX-----------------------!-----!: goal. Border tiles omitted for clarity. 150%; 1-2, 100% and 150%; 1-3, 100% and 150%. Tile characters are -: blank, X: block, @: hazard, ?: bonus, : start, and * input level, scaled by the relative size of the output level (e.g. the counts are halved for levels generated at 50% size). This constraint helps prevent the solver from generating uninteresting levels like rectangles of blocks.
Platform reachability: All blocks that do not have a block or a goal above them must have a reachable state in the tile above them with isong r ound true. This prevents the solver from creating superfluous unreachable platforms in the air. We did not use this constraint when using SMB 1-2 for input, as that training level itself had many unreachable platforms.
Bonus reachability: All bonuses must have a reachable state in the tile below, with w hichbonus set so they can be collected.
Processing took place on an AWS r5.4xlarge instance with 16 cores and 128GB RAM, using Python 3 and pypy 3. The clingo constraint solver was run with 12 threads, using a different random seed for each level generation.
To explore how different levels would impact the generation process, we used SMB levels 1-1, 1-2, and 1-3 for input.
We ran two sets of level generation tests: a size test and a controllability test. To confirm playability, we (1) parsed the solver output to verify that a reachable path existed from the start to goal and (2) manually played all generated levels.
First, to explore the kinds of levels generated, how long it took, and how size impacted them, we generated levels of varying sizes: we used the input level height, and generated levels at 50%, 100% and 150% of the input level width.
For each input level and size, we generated five levels. A summary of the size test and the levels generated is given in Table 1, and examples of levels generated in Figure 3.
Second, to explore how controllable the generated levels could be, we generated levels requiring exact counts of specific tile types. For each of the block, hazard, and bonus tile types, we tried generating a level that required an exact count for that tile type (while allowing the other two tile types to fall within the ranges previously discussed) for 100% size. A summary of the controllability test’s results is given in Table 2, and examples of levels generated in Figure 4.
Although we only requested five levels to be generated from
each training level, we observed a few patterns across the
generated levels. The generated levels were largely made up
of repeated “motifs” that could be found in the training
levels, such as stairs, pits, and groupings of platforms. These
motifs are similar to the “scenes” with specific game
mechanics that
4: Example levels generated from the controllability test. From top to bottom: 1-1, 500 blocks; 1-1, 10 hazards; 1-2, 500 blocks; 1-2, 10 bonuses; 1-3, 300 blocks; hazards. Tile characters are -: blank, X: block, @: hazard, ?: bonus, *
: start, and !: goal. Border tiles omitted for clarity. the training levels that had more empty space. 1-2 and 13 failed to generate smaller size levels, possibly due to not having enough room to work with to place metatiles.
We found that we needed to add some additional constraints to
produce interesting and usable levels. Without the tile count constraints the solver could produce uninteresting levels such as simple rectangles of blocks. We also found that border tiles were needed to prevent the solver from finding undesirable solutions like levels with no bottom blocks to stand on (as it could
exploit the fact that the neighbor metatile constraints only apply to metatiles that are present).
In terms of controllability, we found mixed results. Levels were only generated for about half of the tile count configurations we tested. This may be due to the limitations of the “motifs” discussed above: for example, in 1-1 there was no pit with only one hazard in it, and the solver could not generate a level with only one hazard. In practice, using rangebased or soft constraints may be helpful to enable the solver to find valid solutions.
TLP has relatively simple physics-based movement rules. For example, the turtle accelerates when jumping or falling in the y-direction, but moves at a fixed constant velocity in the x-direction.
We believe the general technique would work with a more complex movement physics simulation, but would result in a larger state graph to precompute. The turtle also has no animation state that might influence its movement, and the world itself is static.
The training and level generation process was memory and computation intensive, necessitating a powerful machine to
run on. For example, the average solving process to generate a level from 1-1 grounding and at 150% width took nearly an hour. However, we have since been able to upgrade our approach to
ground once and solve multiple times with
different random seeds to generate multiple levels, thus reducing the time taken to generate a level.
Finally, although generated levels are playable, the path from start to goal can be technically difficult to follow (i.e.
require precise
timings for specific actions at exact locations). It may be interesting to be able to express the difficulty of following a path as a constraint as well.
character
Future work can explore games where has more complex movement rules, as well the as more complex levels involving larger local neighborhoods (which would allow for the incorporation of moving elements like moving platforms and enemies) and generating levels by training on multiple levels at once. We could also consider other types of level generation primitives: in SMBstyle levels, it may make sense to train on columns rather than individual tiles. Optimizations to improve the speed of training and level generation are also areas for future work.
This research uses levels authored by humans, and future work based on it must grapple with ethical questions of compensation, privacy, and equity, among others. Due to space constraints, we focus here on compensation and equity, and refer readers to
ford (2016) for a discussion of privacy concerns in ML.
In
implementations and continuations
of
this
research,
people should be fairly compensated for their labor to make
levels that train
the system.
previously done by people, the profits or savings should be shared with the people who enabled them.
compensation,
al. (2020) call on implementers and researchers to ask whether their use of data empowers users or exploits them.
Moreover, machine learning may amplify harms in design (Phillips et
al. 2016; Bennett and Keyes 2019): this system may create level elements that are harmful or inaccessible,
or that reproduce intentionally abusive input. Often, machine learning focuses on removing “bias,” but this is not sufficient: ML systems may reproduce hate symbols or add harmful
elements, even if they are not “biased”
towards them
of this detection, human
review may be necessary. We further call for future work to
undergo careful design and ethical review, going beyond this
incomplete list of potential risks and engaging with
intersectional analysis
In this work, we present an approach for constraintbased platformer level generation that guarantees playability, based on player movement, without the need for postgeneration evaluation and filtering. Our approach also supports additional constraints to offer designers more creative control and allow for flexible level generation. We believe this
controllable, constraint-based PCGML technique can aid game designers in
elaborating on new ideas, re-mixing and expanding on existing levels, and rapidly iterating, while maintaining playability. Summerville, A. J.; Philip, S.; and Mateas, M. 2015. MCMCTS PCG 4 SMB: Monte Carlo tree search to guide platformer level generation. Eleventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Togelius, J., and Dahlskog, S. 2013. Patterns as objectives for level generation. In Proceedings of the Second Workshop on Design Patterns in Games.
Yu, D., and Hull, A. 2009. Spelunky (PC Game).