=Paper=
{{Paper
|id=Vol-2862/paper13
|storemode=property
|title=Precomputing Player Movement in Platformers for Level Generation with Reachability Constraints
|pdfUrl=https://ceur-ws.org/Vol-2862/paper13.pdf
|volume=Vol-2862
|authors=Vivian Lee,Nathan Partlan,Seth Cooper
|dblpUrl=https://dblp.org/rec/conf/aiide/LeePC20
}}
==Precomputing Player Movement in Platformers for Level Generation with Reachability Constraints==
https://ceur-ws.org/Vol-2862/paper13.pdf
Precomputing Player Movement in Platformers for Level Generation with
Reachability Constraints
Vivian Lee Nathan Partlan Seth Cooper
Northeastern University Northeastern University Northeastern University
lee.viv@northeastern.edu partlan.n@northeastern.edu se.cooper@northeastern.edu
Abstract
Procedural content generation via Machine Learning
(PCGML) creates game levels from examples. PCGML for
platformers with physics-based player movement gener-
ally 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 ap-
plied to games with simple grid-based movement. In this
work, we present a constraint-based PCGML approach Figure 1: Screenshot of Turtle Loves Pizza, showing the tur-
for platformers with physics-based player movement that
guarantees playability and provides design controllability.
tle, blocks, hazards, a bonus, and the pizza goal. Positions
Our approach exhaustively precomputes all possible player and transitions of enumerated state graph overlaid in teal.
movement states in example tile-based platformer levels. It Border tiles omitted for clarity.
extracts metatiles containing local state information and uses
them in constraint-based level generation that ensures legal
tile neighbors and consistent movement state transitions. Beyond playability, PCGML methods often struggle to
The approach can ensure constraints on gameplay, such guarantee other attributes of the resulting levels such as the
as the reachability of goals, guaranteeing level playability, distribution of design elements or the reachability of col-
and other elements like platforms and bonuses. It can also
incorporate other designer-controllable constraints.
lectible items. Many PCGML methods rely on neural net-
works, probabilistic graphical models, and other similar ap-
proaches that are not easily interpretable or controllable. De-
Introduction signers may need to iteratively re-train, often guessing what
Procedural content generation via Machine Learning might help the system achieve their desired vision (Sum-
(PCGML) is an approach to game level generation that merville, Philip, and Mateas 2015). Constraint-based meth-
learns from existing levels (Summerville et al. 2018). By ods allow designers to write a declarative description of their
learning to generate unique levels from hand-designed ones, requirements for the resulting level.
PCGML methods can complement and support human de- In this paper, we propose an approach to constraint-based
signers’ creativity. They can generate new ideas that match PCGML for platformers with physics-based player move-
well with the designer’s style and needs, helping with brain- ment that allows reachability and other designer-controllable
storming or refinement of a level design. constraints. Our approach precomputes all possible player
While researchers have developed PCGML approaches to states, based on the game’s physics and movement rules,
generate levels for platformer games, these systems typically in the training levels, and associates the tiles with those
do not provide guarantees about the reachability of level el- states and the transitions between them to create metatiles.
ements, such as goals, and thus whether the resulting lev- By tracking and constraining state transitions when generat-
els are playable. They often rely on post-generation filtering ing levels, we ensure reachability of specific tiles like goals
and playability heuristics and start over if the level is not and collectibles. We also include tile neighbor constraints
playable (Snodgrass and Ontañón 2016). Constraint-based inspired by Wave Function Collapse (WFC) (Gumin 2016),
PCG approaches can incorporate reachability constraints and generate levels by solving the constraints using Answer
that guarantee playability, but have typically been applied to Set Programming (ASP) (Gebser et al. 2011). We show how
games with simple tile-based movement rules (Nelson and this can be combined with other constraints to ensure other
Smith 2016). design requirements, e.g. specific ranges and numbers of tile
Copyright c 2020 for this paper by its authors. Use permitted un- types. This process can be divided into 3 steps: (1) enumer-
der Creative Commons License Attribution 4.0 International (CC ating the state graph, (2) extracting the metatiles and con-
BY 4.0). straints and (3) generating a new level that satisfies all the
constraints. We consider this to be a type of PCGML as some tinuing with Hoover, Togelius, and Yannakis (2015), whose
of the constraints are learned from the training levels. neuroevolution technique was inspired by music theory, and
We applied this level generation technique to a simple then by Guzdial and Riedl (2016). These, however, also did
tile-based platformer game we created called Turtle Loves not guarantee playability. Summerville and Mateas (2016)
Pizza (TLP), shown in Figure 1. We trained on simplified include special path tiles, but these tile-based paths may not
versions of Super Mario Bros. levels from the Video Game reflect the exact player movement rules. ANNs also lack ex-
Level Corpus (VGLC) (Summerville et al. 2016). plainability and transparency, making them less legible for
We applied two types of reachability constraints: playa- designers. Recent efforts to integrate PCGML with mixed-
bility, whether the generated level contains a path from the initiative tools (Hoover, Togelius, and Yannakis 2015; Guz-
start to each goal; and usefulness, whether platforms and col- dial, Liao, and Riedl 2018; Guzdial et al. 2019) may help by
lectibles in the generated level are reachable and can be used providing feedback and integrating playability checks (Hoyt
or collected. The ideal generated level should be both useful et al. 2019), but ANNs remain difficult to train and control.
and playable. We show that our approach can be used to gen- Our approach, using a constraint solver to generate coherent
erate playable levels that also meet additional user-specified levels that respect playability constraints, affords designers
design constraints including specific level dimensions and relative flexibility and control to specify additional local and
the number of certain tile types in the generated level. global constraints on levels.
The focus of this work is to propose a new technique for
generating novel levels from existing ones in platformers. Constraint-based Level Generation Outside of platform-
The contributions are (1) a level generation approach which ers, researchers have experimented with constraint-based
ensures reachability and allows for other controllable con- level generation. In games, this began with the level de-
straints using constraint-based PCGML and precomputed sign tool SketchaWorld by Smelik et al. (2010), followed
player movement and (2) a demonstration of the approach by work by A. Smith et al. (2010; 2011) on generating
using levels from an established domain with movement puzzle game designs and levels using ASP. As mentioned
rules from a custom platformer game. above, Tanagra and Launchpad applied constraint solving
to platformer levels (Smith, Whitehead, and Mateas 2010;
Related Work Smith et al. 2011), but their approach could only generate a
PCG for Platformers Many researchers have proposed single player path. Horswill and Foged (2012) applied con-
and tested methods for generating levels for platformer straint solving to ensure playability in dungeon generation.
games. One line of work used designer-defined libraries Several released games use versions of Wave Function
or grammars, often paired with constraints or optimiza- Collapse (WFC) (Gumin 2016), a method inspired by tex-
tions. Compton and Mateas (2006) proposed hill-climbing ture synthesis and model-based synthesis (Harrison 2005;
to generate segments of levels by difficulty, stitched to- Merrell 2009). Others have noted that WFC is, essen-
gether with grammars. Inspired by Spelunky (Yu and Hull tially, constraint solving without backtracking (Karth and
2009), Mawhorter and Mateas (2010) created more flexi- Smith 2017), and a PCGML method that learns from exam-
ble levels, at the expense of playability guarantees, by an- ples (Karth and Smith 2018). Using ASP to re-implement
choring hand-defined chunks based on player movement. G. WFC in a full constraint solver has proven successful in
Smith et al. (2010; 2011) followed these concepts of pat- generating playable levels for games with simple movement
tern analysis, adding the idea of rhythm and “beats,” by us- rules (Nelson and Smith 2016; Scurti and Verbrugge 2018).
ing a constraint solver and reactive planning. Another ap- Sandhu, Chen, and McCoy (2019) further demonstrated how
proach employed graph grammars (Londoño and Missura design constraints can be incorporated with a WFC approach
2015). Though some of these techniques guaranteed playa- to generate non-repetitive levels for a tile-based maze game.
bility, they only supported a single path through each level,
and required manual work to define the available patterns. Going beyond previous applications of constraint solv-
Seeking to learn such patterns from training data, Soren- ing to platformers, our approach learns from existing levels
son and Pasquier (2010), Shaker et al. (2012), and To- to automatically determine playability constraints, melding
gelius and Dahlskog (2013) employed evolutionary algo- ideas from WFC and ASP for dungeon generation with plat-
rithms. These did not guarantee playability, but did use former physics modeling.
fitness functions to search towards it. Controllability of
the output, however, was lacking. Others tried probabilis- Precomputation and Sampling Previous work has also
tic graphical models such as n-grams and Markov Models applied extensive or exhaustive computation of gameplay
(Dahlskog, Togelius, and Nelson 2014; Summerville, Philip, states. One application of this has been improved runtime
and Mateas 2015; Snodgrass and Ontañón 2017). However, performance. Stanton et al. (2016) extensively precomputed
these models have difficulty respecting global patterns or gameplay states to allow for high-quality rendering on mo-
constraints (Summerville and Mateas 2016). Snodgrass and bile devices, and Stanton et al. (2014) adaptively precom-
Ontañón (2016) approximated A* pathfinding to check for puted complex fluid dynamics that could be prohibitively
playability, but their test-and-regenerate approach could not expensive to compute at runtime. Another application is test-
guarantee it. ing and analysis. Bauer and Popović (2012) used rapidly-
Finally, others have focused on artificial neural network exploring random trees to analyze and visualize player
(ANN) approaches, beginning with Laskov (2009) and con- movement in a platformer game to support level editing.
1) State Graph Enumeration
3 6 6 6 6 6 6 3
2) Metatile Extraction
3) Level Generation
2 5 3 6 6 6 6 6 8 10
1 3 5 7 9
5 7
4 6 6 2 7
7 8
4 2 5 7 7 7 7 8 10
START GOAL
4 4 8 2 10 5 1 4 4 4 4 4 4 4
3 6
24
4 5 78
47
6 6 3 6 3
1 4 4 4 4 4 4 9
57 8 10
2 4 6 8 10
1 4 3 3
START GOAL 5
4 9 6 6
7 10 8
START GOAL
4 4 4 4 4 4 4 4
25 78
1 4 4 4 4 7
578 10
4 4 9 4 9
Figure 2: Illustrative example of the proposed level generation process. This simplified example does not use TLP physics;
the state only consists of the (x, y) position with start and goal flags, represented by the node color. 1) Given an input level
and the game’s movement rules, a graph of all reachable states is enumerated. 2) Next, all unique metatiles are extracted. A
metatile consists of a tile type and a state graph. We also track which metatiles were neighbors in the training level. 3) Finally, a
constraint solver is used to assemble metatiles into a new level such that metatile neighbor and transition destination constraints
are satisfied, along with any additional constraints supplied. Self transitions and border tiles omitted for clarity.
Overview from the start state to every goal state.
To generate levels using reachability constraints, we analyze Metatile Extraction After we enumerate the state graph
existing playable levels to extract information from each tile for the input level, we extract the level’s metatiles. A
and build a set of constraint rules that new levels must sat- metatile contains a tile type, a graph of all the player’s
isfy. We organize our method into: (1) enumerating the state states within that specific metatile, and the transitions be-
graph, (2) extracting the metatiles and constraints, (3) solv- tween them. A metatile’s state graph also includes outgo-
ing the constraints to generate a new level. Here we discuss ing edges, edges where the destination states are in adjacent
the generic high-level approach, summarized in Figure 2. metatiles. Each metatile’s graph is a subgraph of the fully
Input Our approach takes as input (1) the game’s move- enumerated level state graph. Every tile in the input level has
ment rules and (2) a playable level for training. a corresponding metatile. When extracting metatiles, each
The game’s movement rules take an existing player state state’s position is offset to be relative to the metatile’s loca-
and an input action and return the resulting state. The player tion in the input level. This way, with a level’s metatiles and
state contains at minimum a position component, a flag for knowledge of their locations in the input level, the metatiles’
being the start state, and a flag for being a goal state. graphs can be re-joined to reconstruct the fully enumerated
state graph. Each unique metatile extracted from the input
Next, we define a few simplifying assumptions about the
level is stored and assigned a unique ID.
movement rules in the game. We assume that the player’s
movement is deterministic and that the player’s terminal ve- Once we have extracted the set of unique metatiles from
locity cannot exceed the length of a square tile. Hence, we the input level, we examine the input level to determine the
assume that the movement rules are local: the player’s move- legal adjacent neighbors for each unique metatile. These are
ment, current state, and next state are only affected by the the metatiles that can be placed in each of the 8 possible
player’s surrounding 3x3 neighborhood of tiles at each pos- neighbor positions surrounding each metatile.
sible state in the level. Thus, we assume that the absolute At this point we have finished analyzing the input level
position of the state and neighborhood does not matter, only and have obtained (1) a defined set of metatiles, each con-
the state’s relative position within its local neighborhood. taining a unique subgraph of player states and their transi-
These assumptions are used to extract metatiles which are tions and (2) the learned adjacency rules for each metatile in
then used to generate new levels (discussed below). the set.
A valid training level is an existing level, represented as a Level Generation Finally, we input the metatiles and their
grid of tile types, with a start tile (which defines the player’s adjacency rules into a constraint solver and use WFC to as-
start state), at least one goal tile, and a playable path from semble instances of the metatiles into a new generated level.
start to goal. In this work, we assume all tiles along the outer During level generation, when a metatile is assigned to a
edge of the level (and none of the interior tiles) are border position in the new level, all of its associated states and tran-
tiles, which block the player from going out of the level. We sitions are also placed in the level and offset to the assigned
also assume that levels themselves are static, meaning tiles position. We use a technique similar to one suggested by
will never change positions during gameplay. Nelson and Smith (2016) to track state reachability: the start
State Graph Enumeration The first step in the process is state is inherently reachable and for any source state that is
to enumerate the player’s state graph for the input level. We reachable, all destination states that can be transitioned to
begin with the player’s start state and use the game’s move- from the source state are also reachable.
ment rules to exhaustively precompute every reachable state To assemble metatiles into a level, we use the following
in the level. The transitions in the directed graph represent generic constraints:
the player’s ability to move from a source state to a destina- • Size: Levels are rectangular and must satisfy a given
tion state by performing a particular action. The enumerated width and height, measured in tiles.
state graph for a valid input level will always contain a path • Metatile neighbors: Each of the 8 neighbors of a metatile
Input Level
Input Columns
Time
Enumeration
Time†
Rule Gen.
Time
Other Precomp.
Output Size
Time
Avg. Ground
Time
Avg. Solve
Generated?
Input Level
Input Blocks
Trial Blocks
Generated?
Input Hazards
Trial Hazards
Generated?
Input Bonuses
Trial Bonuses
Generated?
∗ ∗
50% 10m 5m + 500 + 1 – 1 +
∗
1-1 204 5m 7m 1m 100% 20m 11m + 1-1 534 750 + 7 5 + 13 5 +
‡ ∗
150% 33m 20m + 1000 – 10 + 10 +
50% 7m 3m – 500 + 1 – 1 –
1-2∗ 160 4m 5m 1m 100% 14m 7m + 1-2 614 750 + 16 5 – 9 5 –
150% 22m 13m + 1000 + 10 – 10 +
† ∗
50% 5m 3m – 200 – 50 – 0 +
1-3 152 2m 3m 1m 100% 10m 5m + 1-3 222 300 + 96 75 + 1 5 –
∗
150% 16m 8m + 400 – 125 – 10 –
Table 1: Summary of outcomes from size test. All levels Table 2: Summary of outcomes from controllability test.
have 17 rows; sizes include border tiles. Average times are Timings were similar to those for 100% size, except for
mean for 5 levels. Rule gen time is the time it took to gen- those with a ∗ took 1.5–3x as long to solve, † took roughly
erate the generic ASP rules from the extracted metatiles and 80m to solve, and ‡ were stopped after roughly 24h.
constraints for each input level. ∗ SMB 1-2 did not include
the Platform reachability constraint. † After collecting this
dataset, we were able to optimize the rule generation step to score bonus the first time they are hit from below, a start tile
just a few seconds. 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
must be one of the metatiles that was seen neighboring it rules: the turtle’s state has an x and y position and an x
in the same direction in the training level. This is based and y velocity. For simplicity, we used integers for position
on the WFC (Gumin 2016) neighbor constraints. and velocity. Jumping sets the y velocity to its maximum
• Border tiles: The outer edge tiles are assigned to be bor- upward value, and gravity constantly accelerates the turtle
der tiles. Interior tiles must not be border tiles. This en- downward in y. Moving left or right happens at a constant
sures that all 8 neighbors exist for all interior tiles. x velocity. In addition to position and velocity, each state in
• Transition destination: If a source state and transition out TLP has a flag for being a start, a goal, resting on the ground,
of that state exist, the transition’s destination state must or dead. Each state also has an indicator for being in contact
also exist. This is based on the tile reachability rule from with a bonus tile that can be collected in its local tile neigh-
Nelson and Smith (2016). (Note that this does not re- borhood, if any; the indicator specifies the cardinal direction
quire the destination state to have had a corresponding of the bonus tile relative to the turtle. Thus, each state can
incoming transition in the training level). be considered a tuple of (xpos, ypos, xvel, yvel, isstart,
• Goal reachability: All goal states must be reachable. isgoal, isdead, isonground, whichbonus).
This ensures playability. In order to have interesting input levels, we used lev-
We used the Potassco (Gebser et al. 2011) tools to run an els from Super Mario Bros. (SMB) from the VGLC (Sum-
ASP solver to find a placement of metatiles that satisfies the merville et al. 2016). Note that, although we used SMB lev-
defined constraints. Other games may apply additional con- els, we used TLP player movement rules; these are differ-
straints, as we did in this work (discussed below). With this ent from Mario’s but ensure that the levels are still playable.
approach, we can generate new levels that satisfy defined To prepare SMB levels for TLP we made several modifica-
reachability and design constraints from a small training set tions, including mapping SMB tile types to TLP tile types;
and elementary ML technique (Karth and Smith 2018). adding an additional bottom row of hazard tiles where there
were pits in SMB so that the player would be classified as
Application dead after falling into a pit; adding border tiles around the
To explore our approach, we implemented a tile-based plat- perimeter of the level; defining start and goal tiles, and mak-
former called Turtle Loves Pizza (TLP). The player con- ing minute tile placement adjustments as needed for playa-
trols a turtle that can move left and right and jump. The tur- bility (e.g. removing a tile that Mario can pass through with
tle’s (x, y) position is based on its center. The turtle moves a special power-up but the turtle cannot).
smoothly within tiles and can occupy many possible posi- In addition to the generic constraints discussed above, we
tions within them due to the physics-based movement rules. used the following constraints to generate levels:
Its goal is to traverse the level to collect the pizza at the end. • Start and goal tiles: There must be exactly one start tile
There are several tile types that can be used in the game: within the first 10 columns and one goal tile within the
empty tiles that the turtle can move though, block tiles that last 10 columns.
block the turtle from moving, hazard tiles that kill the turtle • Other tile counts: The number of block, hazard, and
when touched, bonus tiles that behave like blocks but give a 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-----------------------!------
XXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXX@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
---------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------?-----------XXXXXXXXXXXXX---XXX?----------------------------------XX-------------- -------------XXX----X??X--------------------------------XXXXXXXXX---XXX?----------------------?-----------XXXXX---XXX?---------------XXX----X??X----------------------------------------------------------
-----------------------------------------------------------------------------------XXX-------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------XXXX-------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--*------------------------------------------------------------------------------XXXXX-------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------!-------
XXXXXX---------?--?--?-----X?X-------------------X-----XXXXXXXXXXX?X------------XXXXXX-------------- ----------X----------XX------X--X------------XX?X----X?X---------------X-----XXX?X---------?--?--?-----X-------------X-----XXX----X----------XX------X--X------------XXXXXXXXX?X---------XXXXXXXXXXXXXXXXX
XXXXXX-------------------------------------------------------------------------XXXXXXX-------------- ----------------------------XX--XX------------------------------------------------------------------------------------------------------------------XX--XX-------------------------------XXXXXXXXXXXXXXXXX
XXXXXX---------------------------------------------------------------------XX-XXXXXXXX-------------- ---------------------------XXX--XXX-----XX---------------------------------------------------------------------------------------------------------XXX--XXX-----XX-----------------------XXXXXXXXXXXXXXXXX
XXXXXX---------------------------------------------------------------------XXXXXXXXXXX----------!--- --*-----------------------XXXX--XXXX----XX--------------------------------------------------------------------------------------------------------XXXX--XXXX----XX-----------------------XXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------?-----------XXXXXXXXXXXXXXXXXXXXX----X??X------------------------------------XXXXXXXX---XXX?----------------------------------------?--------------------------------------XXXXXXXXXXXXXXX---XXX?-----------------XXXXXX----X??X-----------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------!----
------------------?--?--?-----X?X--------------------------XX------X--X------------XXXXXX?X----X?X--------------X-----XX?X---------XXXXXXX---------?---X?X?X---------------------XXX---------X?X---------------------X-----XXX?X----X?X-----------XX------X--X----------XX--X------------XXXX?X---------XXXXXXXX
------------------------------------------------------------------XX--XX-----------------------------------------------------------XXXXXXX-------------------------------XX------XXX---------------------------------------------------------------------XX--XX--------XXX--XX--------------------------XXXXXXXX
-----------------------------------------------------------------XXX--XXX-----XX---------------------------------------------------XXXXXXX---------------------XX--------XX------XXX--------------------------------------------------------------------XXX--XXX------XXXX--XXX-----XX------------------XXXXXXXX
--------*-------------------------------------------------------XXXX--XXXX----XX---------------------------------------------------XXXXXXX---------------------XX--------XX------XXX-------------------------------------------------------------------XXXX--XXXX----XXXXX--XXXX----XX------------------XXXXXXXX
XXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXX@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------?-------------------------------------------------?---------------------------------------?-----------?-----------XXXX---XXX?------------------------?--------------------------------------XXXX---XXX?-----------------------------XX-------------------------------XX----------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXX------------------------------XXX----------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXX-----------------------------XXXX----------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXXX----------------------------XXXXX----------------
-------------------?---X?X?X---------------------XXXXXXXXXXX---------?---X?X?X---------------------XXXX---------?--?--?-----?--?--?-----X------------X-----XX?X---------?---X?X?X---------------------XXX---------X------------X-----XXXXXXXX------------XXXXXX-------------XX------------XXXXXX----------------
-----------------------------------------XX------XXXXXXXXXXX-------------------------------XX------XXXX---------------------------------------------------------------------------------------XX------XXX-----------------------------------------------XXXXXXX-------------XX-----------XXXXXXX----------------
-------------------------------XX--------XX------XXXXXXXXXXX---------------------XX--------XX------XXXX-----------------------------------------------------------------------------XX--------XX------XXX-------------------------------------------XX-XXXXXXXX-------------XX-------XX-XXXXXXXX----------------
----*--------------------------XX--------XX------XXXXXXXXXXX---------------------XX--------XX------XXXX-----------------------------------------------------------------------------XX--------XX------XXX-------------------------------------------XXXXXXXXXXX-------------XX-------XXXXXXXXXXX--------!-------
XXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXX@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
-------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------------------------------------------- -XXX-XX-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XX--------
X-----XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX------------------ X--X-X----XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---------------------
-X-------------------------------X--XXX-X------------X-X-XX-------------XX-X-X-XXX-X--X-XXX-X--XX-X--X-XXX--------------XXX---X--X--X------------------------- --X--X-------------------------------XXX-XXXX-----------XXX-XXX------------XX---X---------------XXXXXX-----------XX--XXX-------------X-X-X-------XX---X-X-XXXXXX-------X---------X-X-X-------------X--X---XX-X-X-X----------------------------
XX-----------------------------------X-XX-----------XXX--XX------------XXXXXXXX--X-XXX--X--XXXXX-X--------------------------------------------XXX-----------!- XXXXX------------------------------------X-XX------------XXX-XX------------XX--XX---------------XXX-XX------------X---XX------------X--X--X-XX-XX-XX-XXX----X-XXXXX--XX--X---X-X-------------------------------------------XXX--------------!-
XX------------------------------------X-------------X---X-------------XX-X-XXX-X-X-X--X--XX----XX-XX-------------------------------------------------------XXX --XX--------------------------------------X-------------X-X-X----------------XX----------------X-X-X-------------XXX-X--------------XXX---X--X--XX---X-XXX-XX------XXXXX--X--XX-X----------------------------------------------------------XXX
--------------------------------------X-----------------X--------------X---X-X-----XXX--X---X-XXX-X----------------------------------------------------------X -XXX--------------------------------------X--------------X--X--------------XX-X-----------------XX-X--------------XX-X--------------X----X-X-XXX-X-XXXXXX-XXX--X--XX-X---X-XXX--X-----------------------------------------------------------XX
X-------------------------------------X------XXX--------X------XXX--------X-XXXXXXXXXX-XXXXXXXXXX------------------------------------------------------------- --X-X-------------------------------------X------XXX--------X------XXX--------X------XXXXXX--------X------XXX--------X------XXX---------XXXXXX-XXXXXXXX-----XX-XXXXXXXXXXXXX------------------------------------------------------------------
X---------------------------X---------X------XXX--------X------XXX--------X-X--X--X--XXX--X--X--X--------------------------------------------------XXX??------ XX-XX---------------------------X---------X------XXX--------X------XXX--------X------XXXXXX--------X------XXX--------X------XXX---------XX--X-X-X--X--X-----X-XX--X--X--X--X----------------------------------------------------XXXXXX??------
X---------????--------X-X-------------XXX---------------XXX---------------XXX--XXXX--XXX--X--X--X--------------XX-------------------------XXX----------------- XX--X---------????--------X-X-------------XXX---------------XXX---------------XXX------------------XXX---------------XXX----------------XX--XXXXX--X--X-----XXXX--X--X--X--X----------------XX-------------------------XXX--------------------
X-------------------X-X-X-X---X--------------------------------------------------------------------------XX----XX-----------XX------------X-X-XXX------------- XXX-X-------------------X-X-X-X---X---------------------------------------------------------------------------------------------------------------------------------------------------XX----XX-----------XX------------XXX-XXX----------------
X-----------------X-X-X-X-X---X-X------------------------------------------------------------------------XX----XX----XX-----XX----------XXXXX--X-------------- -XX-X-----------------X-X-X-X-X---X-X-------------------------------------------------------------------------------------------------------------------------------------------------XX----XX----XX-----XX----------XXXXX--X-----------------
X---*-----------X-X-X-X-X-X---X-X------------------------------------------------------------------------XX----XX----XX-----XX---------XX-X-X----------------- -XXXX---*-----------X-X-X-X-X-X---X-X-------------------------------------------------------------------------------------------------------------------------------------------------XX----XX----XX-----XX---------XX-XXX--------------------
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XX--XXXXXXXX-X-X-------XXXXXX--XXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXX---XXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XX--XXXXXXXXX-XX-------XXXXXXXXX--XXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XX@@XXXXXXXXXXXX@@@@@@@XXXXXX@@XXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XX@@XXXXXXXXXXXX@@@@@@@XXXXXXXXX@@XXX
-------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
XX---------------------------------------------------------------------------------------------------------------------------------------------------X-------- XXX---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------X---------
------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-------------------- X-----XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--------------------
-X-------------------------------X-X-XXXX------------XXXX-X-----------XX---XX-X-XXXXX---X--X-X-XX--X--XX--------------X-----XXX-XXX--------------------------- XX-------------------------------XXXX-XXXX-------------XX--XXX-------------XXXX--X------------X----X-----------X---XXX---------------XXXXX-------XX-X-XXX--X-X-X---X-X---------XXXX-XXXX--------------XXXXX-XX-X-X----------------------------
X--------------------------------------XX-----------XX-X-XX-----------XXX-XX--XXX--XXX---XX-X---X-------------------X-------------X---------XXX-------------!- X---------------------------------------XX------------------XX---------------X--XX------------X-X-XX-----------X--X-XX-----------XXXXX-XXX-------XXXXXXXX----X-XX-X--XX---XX-X-X-X------------------X------------XX---------XXX-------------!-
XX------------------------------------X--------------X-XX---------------XXXX-X--X-X-X--------XX-X----------------------------------------------------------XXX XX-------------------------------------X----------------XX-X---------------XX-XX-------------XXX-X----------------XX---------------X--XX----XXX--------X--X-X-X-XXXX-----X-XX--X-X---------------------------------------------------------XXX
--------------------------------------X----------------XX-----------------X-X--X-XX-X--X---X-XXX-------------------------------------------------------------- X-------------------------------------XX-------------------X----------------XX-X----------------XX--------------XXXX---------------XX-XX----X-X--------X----XX-XXX-X-XXXXXXX-X-XX-------------------------------------------------------------
X-------------------------------------X------XXX--------X------XXX--------XXXXX-XXXXXXXXXXXXXXX--------------------------------------------------------------- X-------------------------------------XX------XXXXX--------X------XXXXX--------X------XXX--------X------XXX--------X------XXX--------XXX----X-X--------XXXX--XXXXXX-XXXX---X-X----------------------------------------------------------------
X---------------------------X---------X------XXX--------X------XXX--------XX--XXXX--XX--X--X--X--------------------------------------------------XXXXX??------ X---------------------------X---------XX------XXXXX--------X------XXXXX--------X------XXX--------X------XXX--------X------XXX--------X-X-?--XXX--------X--XXXXX--XX-X--X---X-X---------------------------------------------------XXXXX??------
X---------????--------X-X-------------XXX---------------XXX---------------XX--XXXX--XX--X--X--X--------------XX-------------------------XXX------------------- X---------????--------X-X-------------XXXX-----------------XXX-----------------XXX---------------XXX---------------XXX---------------XXXX---XXX--XXXXXXX--XXXXX--XXXX--X---XXX---------------XX-------------------------XXX-------------------
X-------------------X-X-X-X---X------------------------------------------------------------------------XX----XX-----------XX------------XXX-XXX--------------- X-------------------X-X-X-X---X--------------------------------------------------------------------------------------------------------------------------------------------------------XX----XX-----------XX------------XXX-XXX---------------
X-----------------X-X-X-X-X---X-X----------------------------------------------------------------------XX----XX----XX-----XX----------XXX-X------------------- X-----------------X-X-X-X-X---X-X------------------------------------------------------------------------------------------------------------------------------------------------------XX----XX----XX-----XX----------XXX-X--X----------------
X---*-----------X-X-X-X-X-X---X-X----------------------------------------------------------------------XX----XX----XX-----XX---------XX-X-X------------------- X---*-----------X-X-X-X-X-X---X-X------------------------------------------------------------------------------------------------------------------------------------------------------XX----XX----XX-----XX---------XX---X-------------------
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XX--XXXXXXXX-X-X-------XXXXXXXX--XXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXX---XXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XX--XXXXXXXXXX-X-------XXXXXXXX--XXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XX@@XXXXXXXXXXXX@@@@@@@XXXXXXXX@@XXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XX@@XXXXXXXXXX@X@@@@@@@XXXXXXXX@@XXX
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------XXXXXXX------------------------------------------------------------------------------------------------------- ------------------------------------XXXXXXX---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------XXX----------------------------------------------------------------------------------------------------------XX----------- ------------------------XXX------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XX-----------
------------------------------------------------------------XXXX-----------------------------------------------------------XXX-----------XX----------- --------------------------------------------------------XXXX------------XXXX---------------------------XXX------------XXXXXXXXXXXXXXXXXXXXXXXXXXXX-----------------------------------------------------XXX-----------XX-----------
---------------------------------------------------------------------------------------------------------------------------------------XXXX----------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXXXXXXXXX-------------------------------XXXX-----------
-----------------------------------XXXXX-----------------------------------------------------------------------------------------------XXXX----------- -------------------------------XXXXX------------------------------------------------------------------------------------------------------------------XXXX---------------------------------------------------------XXXX-----------
--------------------------XXXXXX--------------------------------------XXXX--XXXX--XXX--XXXXXXXX--XXXXXX--XXXX--XXXXXXXXXX------------XXXXXX----------- ----------------------XXXXXX--------------------------------------XXXX------------XXXX--XXXXXX--XXXXX-----------XXX--------------------------------------------XXX----------------------XXXX--XXXXXXX------------XXXXXX-----------
-------------------------------------------------------XXXX?-------------------------------------------------------------------------XXXXXX----------- ---------------------------------------------------XXXX?---------------------------------------------------------------------------------------------------------------------------------------------------------XXXXXX-----------
-------------------------------------------------------------------------------------------------------------------------------------XXXXXX----------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXX------------------------------------------XXXXXX-----------
-----*--------------XXXX--------XXX--------------------------------------------------------------------------------------------------XXXXXX--------!-- ------*---------XXXX--------XXX----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXXXX--------!--
XXXXXXXXXXXXXXXXXX--------------------------------XXXX-----XXXXX-XXXXX------------------------------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXX--------------------------------XXXX-----XXXXX-XXXXX-------XXXXXXXXX----------------------XXXXXXXX---------------------------------------------------------------------XXX----------------XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXX@@@@@XXXXX@XXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXX@@@@@XXXXX@XXXXX@@@@@@@XXXXXXXXX@@@@@@@@@@@@@@@@@@@@@@XXXXXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXX@@@@@@@@@@@@@@@@XXXXXXXXXXXXXXXXXXXXXXXXXX
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------XXXXXXX--------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------XXXXXXX------------------------------------------------------------------------------------------------------------------------------------------------
------------------XXXXXXXXXXXXXXXXX------------------------------------------------------------------------------------------------------XX----------- ------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---------------------------------------------------------------------------------------------------------------------------------------------------XX-----------
----------------------------------------------------------------XXXX--------------------------------XXXXXXXX------------XXXXXX-----------XX----------- -----------------------------------------------------------------------------------------------XXXX---------------------XXX------------XXXX--------------------XXXXX-----------------------XXXXXXXXXXXXXXX-----------XX-----------
---------------------------------------------------------------------------------------------------------------------------------------XXXX----------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXX-----------
---------------------------------------XXXXX-------------------------------------------------------------------------------------------XXXX----------- ----------------------------------------------------------------------XXXXX----------------------------------------------------------------------------------------------------------------------------------------XXXX-----------
----------------XXXXXXXXXXXXXXXXXXXX--------------------------------------XXXX--XXXXXXXXX--XXXXXXX----------------XXXX---------------XXXXXX----------- ----------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--------------------------------------XXXX--XXXXXXX-----------XXXX------------XXXX--XXXXXX-------------XXXX--XXX--XXXX------------------------XXXXXX-----------
-----------------------------------------------------------XXXX?---------------------------------------------------------------------XXXXXX----------- ------------------------------------------------------------------------------------------XXXX?------------------------------------------------------------------------------------------------------------------XXXXXX-----------
-------------------------------------------------------------------------------------------------------------------------------------XXXXXX----------- -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------XXXXXX-----------
---*------XXXX----------------------XXX----------------------------------------------------------------------------------------------XXXXXX--------!-- ---*------XXXX-----------------------------------------------------XXX-------------------------------------------------------------------------------------------------------------------------------------------XXXXXX--------!--
XXXXXXXX----------------------------------------------XXXX-----XXXXX-XXXXX---------------------------XXXXXXXXXXXXX-------XXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXX-----------------------------------------------------------------------------XXXX-----XXXXX-XXXXX----------------XXXXXXXX-------XXXXXXXXX---------------XXXXXXXXXX------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXX@@@@@XXXXX@XXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXXXXXXXXXXX@@@@@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXX@@@@@XXXXX@XXXXX@@@@@@@@@@@@@@@@XXXXXXXX@@@@@@@XXXXXXXXX@@@@@@@@@@@@@@@XXXXXXXXXX@@@@@@@@@@@@@@@@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Figure 3: Example levels generated from the size test. From top to bottom, with two rows of each: 1-1, 50% and 100%; 1-1,
150%; 1-2, 100% and 150%; 1-3, 100% and 150%. Tile characters are -: blank, X: block, @: hazard, ?: bonus, *: start, and
!: goal. Border tiles omitted for clarity.
input level, scaled by the relative size of the output level Second, to explore how controllable the generated levels
(e.g. the counts are halved for levels generated at 50% could be, we generated levels requiring exact counts of spe-
size). This constraint helps prevent the solver from gen- cific tile types. For each of the block, hazard, and bonus tile
erating uninteresting levels like rectangles of blocks. types, we tried generating a level that required an exact count
• Platform reachability: All blocks that do not have a for that tile type (while allowing the other two tile types to
block or a goal above them must have a reachable state fall within the ranges previously discussed) for 100% size. A
in the tile above them with isonground true. This pre- summary of the controllability test’s results is given in Table
vents the solver from creating superfluous unreachable 2, and examples of levels generated in Figure 4.
platforms in the air. We did not use this constraint when
using SMB 1-2 for input, as that training level itself had Discussion
many unreachable platforms. Although we only requested five levels to be generated from
• Bonus reachability: All bonuses must have a reachable each training level, we observed a few patterns across the
state in the tile below, with whichbonus set so they can generated levels. The generated levels were largely made up
be collected. of repeated “motifs” that could be found in the training lev-
Processing took place on an AWS r5.4xlarge instance with els, such as stairs, pits, and groupings of platforms. These
16 cores and 128GB RAM, using Python 3 and pypy 3. The motifs are similar to the “scenes” with specific game me-
clingo constraint solver was run with 12 threads, using a dif- chanics that Green et al. (2020) showed could be stitched
ferent random seed for each level generation. together to generate new SMB levels, though it should be
To explore how different levels would impact the genera- noted that our approach ensures playability for all generated
tion process, we used SMB levels 1-1, 1-2, and 1-3 for input. levels. The variety in our generated levels seems to be pri-
We ran two sets of level generation tests: a size test and a marily based on reorganizations of these motifs with vari-
controllability test. To confirm playability, we (1) parsed the ations on their lengths. 1-2 had the least variety of levels
solver output to verify that a reachable path existed from the generated, with generated levels of the same length being
start to goal and (2) manually played all generated levels. made up of the same sequences of motifs and minor rear-
First, to explore the kinds of levels generated, how long rangements of blocks. In fact, 3 of the 5 levels generated
it took, and how size impacted them, we generated levels from 1-2 at 100% size were identical. This may be par-
of varying sizes: we used the input level height, and gener- tially attributable to the relatively closed-off nature of 1-2
ated levels at 50%, 100% and 150% of the input level width. and the lack of the platform reachability constraint, allow-
For each input level and size, we generated five levels. A ing the solver to create unusable platforms to easily satisfy
summary of the size test and the levels generated is given in the adjacency and tile type range constraints. The solver ap-
Table 1, and examples of levels generated in Figure 3. peared more flexible in generating levels from 1-1 and 1-3,
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------?-----------XXXX---XXX?---------------------------?-------------------------------------XXXX---XXX?--------------------------?-----------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------!---
--------------------?--?--?-----X------------X-----XXXXX?X---------?---X?X?X---------------------XX---------X------------X-----XXXXXX---------?---X?X?X---------------------XX---------XXX---------XXXXXXX
Finally, although generated levels are technically
playable, the path from start to goal can be difficult to
-----------------------------------------------------------------------------------------XX------XX-----------------------------------------------------------------XX------XX---------XXX---------XXXXXXX
-------------------------------------------------------------------------------XX--------XX------XX-------------------------------------------------------XX--------XX------XX---------XXX---------XXXXXXX
--------*----------------------------------------------------------------------XX--------XX------XX-------------------------------------------------------XX--------XX------XX---------XXX---------XXXXXXX
XXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXX@@XXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------XX-------------------XXXXXXXXXXXXXXX---XXX?-------------------------XX------------------------------------------------?-----------XXXXXXXXX---XXX?--------------------------------
-----------------------XXX-----------------------------------------------------------------XXX------------------------------------------------------------------------------------------------------------
----------------------XXXX----------------------------------------------------------------XXXX------------------------------------------------------------------------------------------------------------
follow (i.e. require precise timings for specific actions at
exact locations). It may be interesting to be able to express
--*------------------XXXXX---------------------------------------------------------------XXXXX---------------------------------------------------------------------------------------------------!--------
XXXXXXXX------------XXXXXX----------------X?X---------------------X-----XX?X------------XXXXXX---------------------XXX---------XXX---------?--?--?-----X?X---------------X-----XX?X---------XXXXXXXXXXXXXX
XXXXXXXX-----------XXXXXXX-------------------------------------------------------------XXXXXXX---------------------XXX---------XXX----------------------------------------------------------XXXXXXXXXXXXXX
XXXXXXXX-------XX-XXXXXXXX---------------------------------------------------------XX-XXXXXXXX---------------------XXX---------XXX----------------------------------------------------------XXXXXXXXXXXXXX
XXXXXXXX-------XXXXXXXXXXX---------------------------------------------------------XXXXXXXXXXX---------------------XXX---------XXX----------------------------------------------------------XXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
--------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------
------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX----------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------XXX---------------------------------------------------------!-
the difficulty of following a path as a constraint as well.
-----------------------------------------------------------------------------------------------------------------------------------------------------------XXX
--------------------------------------------------------------------------------------------------------------------------------------------------------------
X--------------------------------------X-X--------------------------------------------------------------------------------------------------------------------
X----------------------------X---------X-X-----------------------------------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX??------
X---------?????--------X-X-------------XXX-----------------------XX-------------------------XXX---------------------------------------------------------------
X--------------------X-X-X-X---X---------------------------XX----XX-----------XX------------X-X-XXX-----------------------------------------------------------
X------------------X-X-X-X-X---X-X-------------------------XX----XX----XX-----XX----------XXX-X---------------------------------------------------------------
Future Work Future work can explore games where the
X---*------------X-X-X-X-X-X---X-X-------------------------XX----XX----XX-----XX---------XX---X---------------------------------------------------------------
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XX--XXXXXXXX-----------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XX@@XXXXXXXX@@@@@@@@@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XXX
--------------------------------------------------------------------------------------------------------------------------------------------------------------
character has more complex movement rules, as well as
X-X-----------------------------------------------------------------------------------------------------------------------------------------------------------
-X----XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX?XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX------------------
XX-------------------------------X------X-------------XXX-X------X-XXX-X-XX------X--XXX------X--X-XX--X-X----------------X--X--XX---X-------------------------
------------------------------------X--XX-----------X-XXXXX------XXXXXXXXXX------XXXXXX------XXXX--X------------------X-----------------------XXX-----------!-
X-------------------------------------X--------------X-XX----XX------XX-X----XX-----X----XX-----X-X--------------------------------------------------------XXX
X-------------------------------------X--------------XXXX----XX------XX-X----XX-----X----XX-----XX----------------------------------------------------------XX
more complex levels involving larger local neighborhoods
X-------------------------------------X------XXX--------X----XX------XXXX----XX-----X----XX-----X-------------------------------------------------------------
X---------------------------X---------X------XXX--------X-?--XX------X--X-?--XX-----X-?--XX-----X--------------------------------------------------XXX??------
X---------????--------X-X-------------XXX---------------XX---XX--XXXXX--XX---XX--XXXXX---XX--XXXX--------------XX-------------------------XXX-----------------
X-------------------X-X-X-X---X--------------------------------------------------------------------------XX----XX-----------XX------------XXX-XXX-------------
X-----------------X-X-X-X-X---X-X------------------------------------------------------------------------XX----XX----XX-----XX----------XXXXX-----------------
X---*-----------X-X-X-X-X-X---X-X------------------------------------------------------------------------XX----XX----XX-----XX---------XX--XX-----------------
(which would allow for the incorporation of moving ele-
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX---XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--XX--XXXXXXXX--XX-------XXXXXX--XXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@XX@@XXXXXXXX@XXX@@@@@@@XXXXXX@@XXX
------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------
ments like moving platforms and enemies) and generating
------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------XXXXXXX--------------------------------------------------------------------------------------
---*--------------XX--------------------XXXXXXXX-----------------------------------------------------------------------------------------XX-----------
XXXXXXX-----------XX---------------------------------------------------------XXXX------------------------------------------XXX-----------XX-----------
levels by training on multiple levels at once. We could also
----------------XXXX-------------------------------------------------------------------------------------------------------------------XXXX-----------
----------------XXXX--------------------------------XXXXX------------------------------------------------------------------------------XXXX-----------
--------------XXXXXX------------------XXXXXXXXXXX--------------------------------------XXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXX------------XXXXXX-----------
--------------XXXXXX----------------------------------------------------XXXX?--------------------------------------------------------XXXXXX-----------
--------------XXXXXX-----------------------------------------------------------------------------------------------------------------XXXXXX-----------
--------------XXXXXX------------XXXX-------------XXX---------------------------------------------------------------------------------XXXXXX--------!--
consider other types of level generation primitives: in SMB-
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-------------------------------------XXXX-----XXXXX-XXXXX-------------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXX@@@@@XXXXX@XXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXXXXXXXXXXXXXXXXXXXXXXXX
------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------
style levels, it may make sense to train on columns rather
------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------XXXXXXX---------------------------------------------------------------------------------
---------------------------------------XXXXXXXXXXXXXX------------------------------------------------------------------------------XX-----------------
----------------------------------------------------------------------------------XXXX-------------------------------XXX-----------XX-----------------
---------------------------------------------------------------------------------------------------------------------------------XXXX-----------------
than individual tiles. Optimizations to improve the speed of
---------------------------------------------------------XXXXX-------------------------------------------------------------------XXXX-----------------
-------------------------------------XXXXXXXXXXXXXXXXX--------------------------------------XXXX--XXXXXX--XXXXXXXXX------------XXXXXX-----------------
-----------------------------------------------------------------------------XXXX?---------------------------------------------XXXXXX-----------------
-------------------------------------------------------------------------------------------------------------------------------XXXXXX-----------------
-------*-----------------------XXXX-------------------XXX----------------------------------------------------------------------XXXXXX--------------!--
training and level generation are also areas for future work.
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX-------------------------------------------XXXX-----XXXXX-XXXXX--------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@XXXX@@@@@XXXXX@XXXXX@@@@@@@@@@@@@@@@@@@@@@@@@@XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Ethical Implications This research uses levels authored by
Figure 4: Example levels generated from the controllability humans, and future work based on it must grapple with eth-
test. From top to bottom: 1-1, 500 blocks; 1-1, 10 hazards; ical questions of compensation, privacy, and equity, among
1-2, 500 blocks; 1-2, 10 bonuses; 1-3, 300 blocks; 1-3, 75 others. Due to space constraints, we focus here on compen-
hazards. Tile characters are -: blank, X: block, @: hazard, ?: sation and equity, and refer readers to Metcalf and Craw-
bonus, *: start, and !: goal. Border tiles omitted for clarity. 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. Sloane et al. (2020) point out
the training levels that had more empty space. 1-2 and 1-
that many ML systems are built on uncompensated, unac-
3 failed to generate smaller size levels, possibly due to not
knowledged labor. If misused, this could become one such
having enough room to work with to place metatiles.
system. If it produces profit or increases efficiency by sup-
We found that we needed to add some additional con- planting work previously done by people, the profits or sav-
straints to produce interesting and usable levels. Without the ings should be shared with the people who enabled them.
tile count constraints the solver could produce uninteresting Beyond monetary compensation, Sloane et al. (2020) call
levels such as simple rectangles of blocks. We also found on implementers and researchers to ask whether their use of
that border tiles were needed to prevent the solver from find- data empowers users or exploits them.
ing undesirable solutions like levels with no bottom blocks Moreover, machine learning may amplify harms in de-
to stand on (as it could exploit the fact that the neighbor sign (Phillips et al. 2016; Bennett and Keyes 2019): this
metatile constraints only apply to metatiles that are present). system may create level elements that are harmful or inac-
In terms of controllability, we found mixed results. Levels cessible, or that reproduce intentionally abusive input. Of-
were only generated for about half of the tile count configu- ten, machine learning focuses on removing “bias,” but this
rations we tested. This may be due to the limitations of the is not sufficient: ML systems may reproduce hate symbols
“motifs” discussed above: for example, in 1-1 there was no or add harmful elements, even if they are not “biased” to-
pit with only one hazard in it, and the solver could not gen- wards them (Phillips et al. 2016). An equitable implemen-
erate a level with only one hazard. In practice, using range- tation would carefully vet input and output designs to mini-
based or soft constraints may be helpful to enable the solver mize harm, especially to vulnerable or marginalized groups.
to find valid solutions. If automated review is not capable of this detection, human
Limitations TLP has relatively simple physics-based review may be necessary. We further call for future work to
movement rules. For example, the turtle accelerates when undergo careful design and ethical review, going beyond this
jumping or falling in the y-direction, but moves at a fixed incomplete list of potential risks and engaging with intersec-
constant velocity in the x-direction. We believe the gen- tional analysis (Ciston 2019).
eral technique would work with a more complex movement
physics simulation, but would result in a larger state graph Conclusion
to precompute. The turtle also has no animation state that In this work, we present an approach for constraint-
might influence its movement, and the world itself is static. based platformer level generation that guarantees playabil-
The training and level generation process was memory ity, based on player movement, without the need for post-
and computation intensive, necessitating a powerful ma- generation evaluation and filtering. Our approach also sup-
chine to run on. For example, the average grounding and ports additional constraints to offer designers more creative
solving process to generate a level from 1-1 at 150% width control and allow for flexible level generation. We believe
took nearly an hour. However, we have since been able to up- this controllable, constraint-based PCGML technique can
grade our approach to ground once and solve multiple times aid game designers in elaborating on new ideas, re-mixing
with different random seeds to generate multiple levels, thus and expanding on existing levels, and rapidly iterating, while
reducing the time taken to generate a level. maintaining playability.
References Karth, I., and Smith, A. M. 2017. WaveFunctionCollapse
is constraint solving in the wild. In Proceedings of the
Bauer, A. W., and Popović, Z. 2012. RRT-based game level
12th International Conference on the Foundations of Dig-
analysis, visualization, and visual refinement. In Eighth
ital Games, 68:1–68:10.
AAAI Conference on Artificial Intelligence and Interactive
Digital Entertainment. Karth, I., and Smith, A. M. 2018. Addressing the fun-
damental tension of PCGML with discriminative learning.
Bennett, C. L., and Keyes, O. 2019. What is the Point of arXiv:1809.04432 [cs, stat].
Fairness? Disability, AI and The Complexity of Justice. In
ASSETS 2019 Workshop—AI Fairness for People with Dis- Laskov, A. 2009. Level generation system for platform
abilities. games based on a reinforcement learning approach. Uni-
versity of Edinburgh, Tech. Rep. EDI-INF-IM090699.
Ciston, S. 2019. Imagining Intersectional AI. In 7th Con- Londoño, S., and Missura, O. 2015. Graph Grammars for
ference on Computation, Communication, Aesthetics & X, Super Mario Bros Levels. In Proceedings of the 10th Inter-
39. national Conference on the Foundations of Digital Games.
Compton, K., and Mateas, M. 2006. Procedural Level De- Mawhorter, P., and Mateas, M. 2010. Procedural level gener-
sign for Platform Games. In Second AAAI Conference on ation using occupancy-regulated extension. In Proceedings
Artificial Intelligence and Interactive Digital Entertainment, of the 2010 IEEE Conference on Computational Intelligence
109–111. and Games, 351–358.
Dahlskog, S.; Togelius, J.; and Nelson, M. J. 2014. Linear Merrell, P. C. 2009. Model synthesis. Ph.D. Dissertation,
levels through n-grams. In Proceedings of the 18th Inter- University of North Carolina at Chapel Hill.
national Academic MindTrek Conference: Media Business, Metcalf, J., and Crawford, K. 2016. Where are human sub-
Management, Content & Services, 200–206. jects in big data research? The emerging ethics divide. Big
Gebser, M.; Kaufmann, B.; Kaminski, R.; Ostrowski, M.; Data & Society 3(1).
Schaub, T.; and Schneider, M. 2011. Potassco: The Pots- Nelson, M. J., and Smith, A. M. 2016. ASP with ap-
dam answer set solving collection. AI Communications plications to mazes and levels. In Shaker, N.; Togelius,
24(2):107–124. ISBN: 0921-7126 Publisher: Citeseer. J.; and Nelson, M. J., eds., Procedural Content Generation
Green, M. C.; Mugrai, L.; Khalifa, A.; and Togelius, J. 2020. in Games, Computational Synthesis and Creative Systems.
Mario level generation from mechanics using scene stitch- Cham: Springer International Publishing. 143–157.
ing. arXiv:2002.02992 [cs.AI]. Phillips, A.; Smith, G.; Cook, M.; and Short, T. 2016. Fem-
Gumin, M. 2016. WaveFunctionCollapse. GitHub reposi- inism and procedural content generation: toward a collabo-
tory. https://github.com/mxgmn/WaveFunctionCollapse. rative politics of computational creativity. Digital Creativity
27(1):82–97.
Guzdial, M., and Riedl, M. 2016. Game level generation
from gameplay videos. In Twelfth Artificial Intelligence and Sandhu, A.; Chen, Z.; and McCoy, J. 2019. Enhancing Wave
Interactive Digital Entertainment Conference. Function Collapse with design-level constraints. In Proceed-
ings of the 14th International Conference on the Founda-
Guzdial, M.; Liao, N.; Chen, J.; Chen, S.-Y.; Shah, S.; Shah, tions of Digital Games, 1–9.
V.; Reno, J.; Smith, G.; and Riedl, M. O. 2019. Friend,
collaborator, student, manager: How design of an AI-driven Scurti, H., and Verbrugge, C. 2018. Generating paths with
game level editor affects creators. In Proceedings of the WFC. In Fourteenth AAAI Conference on Artificial Intelli-
2019 CHI Conference on Human Factors in Computing Sys- gence and Interactive Digital Entertainment.
tems, 624:1–624:13. Shaker, N.; Nicolau, M.; Yannakakis, G. N.; Togelius, J.; and
O’Neill, M. 2012. Evolving levels for Super Mario Bros
Guzdial, M.; Liao, N.; and Riedl, M. 2018. Co-creative level
using grammatical evolution. In 2012 IEEE Conference on
design via machine learning. In Experimental AI In Games
Computational Intelligence and Games (CIG), 304–311.
Workshop. arXiv:1809.09420.
Sloane, M.; Moss, E.; Awomolo, O.; and Forlano, L. 2020.
Harrison, P. F. 2005. Image Texture Tools. Ph.D. Disserta- Participation is not a design fix for machine learning. In
tion, Monash University. ICML 2020 Workshop on Participatory Approaches to Ma-
Hoover, A. K.; Togelius, J.; and Yannakis, G. N. 2015. Com- chine Learning.
posing video game levels with music metaphors through Smelik, R.; Tutenel, T.; de Kraker, K. J.; and Bidarra, R.
functional scaffolding. In First Computational Creativity 2010. Integrating procedural generation and manual editing
and Games Workshop. of virtual worlds. In Proceedings of the 2010 Workshop on
Horswill, I. D., and Foged, L. 2012. Fast procedural level Procedural Content Generation in Games, 1–8.
population with playability constraints. In Eighth AAAI Smith, A. M., and Mateas, M. 2011. Answer set program-
Conference on Artificial Intelligence and Interactive Digital ming for procedural content generation: A design space ap-
Entertainment. proach. IEEE Transactions on Computational Intelligence
Hoyt, A.; Guzdial, M.; Kumar, Y.; Smith, G.; and Riedl, and AI in Games 3(3):187–200.
M. O. 2019. Integrating Automated Play in Level Co- Smith, G.; Whitehead, J.; Mateas, M.; Treanor, M.; March,
Creation. In Experimental AI In Games Workshop. J.; and Cha, M. 2011. Launchpad: A rhythm-based level
generator for 2-d platformers. IEEE Transactions on com-
putational intelligence and AI in games 3(1):1–16.
Smith, A. M.; Nelson, M. J.; and Mateas, M. 2010. Lu-
docore: A logical game engine for modeling videogames.
In Proceedings of the 2010 IEEE Conference on Computa-
tional Intelligence and Games, 91–98.
Smith, G.; Whitehead, J.; and Mateas, M. 2010. Tanagra:
A mixed-initiative level design tool. In Proceedings of the
Fifth International Conference on the Foundations of Digital
Games, 209–216.
Snodgrass, S., and Ontañón, S. 2016. Controllable proce-
dural content generation via constrained multi-dimensional
Markov chain sampling. In Proceedings of the Twenty-
Fifth International Joint Conference on Artificial Intelli-
gence, 780–786.
Snodgrass, S., and Ontañón, S. 2017. Learning to generate
video game maps using Markov models. IEEE Transactions
on Computational Intelligence and AI in Games 9(4):410–
422.
Sorenson, N., and Pasquier, P. 2010. The evolution of fun:
Automatic level design through challenge modeling. In In-
ternational Conference on Computational Creativity, 258–
267.
Stanton, M.; Humberston, B.; Kase, B.; O’Brien, J. F.; Fata-
halian, K.; and Treuille, A. 2014. Self-refining games us-
ing player analytics. ACM Transactions on Graphics (SIG-
GRAPH) 33(4):73:1–73:9.
Stanton, M.; Geddert, S.; Blumer, A.; Hormis, P.; Nealen,
A.; Cooper, S.; and Treuille, A. 2016. Large-scale finite state
game engines. In Proceedings of the Eurographics/ACM
SIGGRAPH Symposium on Computer Animation.
Summerville, A., and Mateas, M. 2016. Super Mario
as a string: platformer level generation via LSTMs.
arXiv:1603.00930 [cs].
Summerville, A. J.; Snodgrass, S.; Mateas, M.; and
Ontañón, S. 2016. The VGLC: The Video Game Level Cor-
pus. arXiv:1606.07487 [cs].
Summerville, A.; Snodgrass, S.; Guzdial, M.; Holmgård, C.;
Hoover, A. K.; Isaksen, A.; Nealen, A.; and Togelius, J.
2018. Procedural Content Generation via Machine Learning
(PCGML). IEEE Transactions on Games 10(3):257–270.
Summerville, A. J.; Philip, S.; and Mateas, M. 2015. MCM-
CTS PCG 4 SMB: Monte Carlo tree search to guide plat-
former level generation. Eleventh AAAI Conference on Arti-
ficial 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).