=Paper=
{{Paper
|id=Vol-3926/paper5
|storemode=property
|title=Punch Out Model Synthesis: A Stochastic Algorithm for Constraint Based Tiling Generation
|pdfUrl=https://ceur-ws.org/Vol-3926/paper5.pdf
|volume=Vol-3926
|authors=Zzyv Zzyzek
|dblpUrl=https://dblp.org/rec/conf/exag/Zzyzek24
}}
==Punch Out Model Synthesis: A Stochastic Algorithm for Constraint Based Tiling Generation==
https://ceur-ws.org/Vol-3926/paper5.pdf
Punch Out Model Synthesis: A Stochastic Algorithm for
Constraint Based Tiling Generation
Zzyv Zzyzek1
Abstract
As an artistic aid in tiled level design, Constraint Based Tiling Generation (CBTG) algorithms can help to automatically create level
realizations from a set of tiles and placement constraints. Merrell’s Modify in Blocks Model Synthesis (MMS) and Gumin’s Wave Function
Collapse (WFC) have been proposed as Constraint Based Tiling Generation (CBTG) algorithms that work well for many scenarios but
have limitations in problem size, problem setup and solution biasing. We present Punch Out Model Synthesis (POMS), a Constraint
Based Tiling Generation algorithm, that can handle large problem sizes, requires minimal assumptions for setup and can help mitigate
solution biasing. POMS attempts to resolve indeterminate grid regions by trying to progressively realize sub-blocks, performing a
stochastic boundary erosion on previously resolved regions should sub-block resolution fail. We highlight the results of running a
reference implementation on different tile sets and discuss a tile correlation length, implied by the tile constraints, and its role in
choosing an appropriate block size to aid POMS in successfully finding grid realizations.
1. Introduction previous state and all realized region boundaries within the
grid are considered for erosion by probabilistically setting
1.1. Overview them to an indeterminate state.
POMS is a stochastic algorithm because of the reversion
We present Punch Out Model Synthesis (POMS), an algo-
step. Undoing previous cell realizations, via block region
rithm that works on a regular 2D or 3D grid to find a tile
reversion or erosion, are done in the hopes of removing
placement realization subject to pairwise tile constraints in
a localized contradiction. Any expectation of progress for
each grid direction (±𝑋, ±𝑌, ±𝑍).
POMS primarily comes from choosing an appropriate block
POMS is a grid level stochastic Constraint Based Tiling
size. Conceptually, correlation length is the influence that
Generation (CBTG) algorithm whose primary benefits are:
a cell tile choice has over other cell tile options at distant
locations. In this paper, we attempt to quantify an aspect of
• Requires minimal assumptions on initial setup state
correlation length and use it to inform the block size choice.
• Has resources that scale primarily with block size
If there is a finite length of correlation that one cell’s tile
and not grid size
choice has with another, any contradiction that might ap-
• Can reliably find realizations on arbitrarily sized pear during the course of resolution are localized to a region.
grids with tile constraints that have finite correlation Reverting the region around the contradiction allows for
length another attempt at finding a realization without destroying
the bulk of pre-existing realizations elsewhere in the grid.
and primary drawbacks that:
Under some conditions of configuration randomness, and
• Has limited success for tile constraints that have for many tile constraints, resolved cells located far enough
long range correlation length away from each other have little or no influence over one an-
other. The correlation distance informs the block size choice
Further, we: as block sizes chosen large enough allow for the tile values
in the middle cells of a block to be chosen independent of
• Provide the results of running a reference implemen- any tiles fixed on the boundary.
tation on a variety of tile sets (Section 4) Expecting center tile choices to be independent of bound-
• Explore the Tile Arc Consistent Correlation Length ary tile values is, in general, unreasonable as the CBTG
(TACCL), a heuristic for tile correlation length, that problem is known to be NP-Complete. Even under random
is used to inform the block size choice and solution configuration assumptions, the issue can be further compli-
strategies for a variety of tile sets (Section 4) cated if the correlation length is not finite, or finite but large.
Even though the general problem is likely intractable, or the
Here, a grid realization is a single tile assignment per grid finite correlation length assumption is violated, many tile
cell that respects the tile constraints. constraints are under constrained and the ability of POMS
POMS works by initially setting the grid to an indetermi- to overcome local constraints provides enough capability to
nate state and progressively realizing sub blocks of the grid. find realizations.
Block boundary edges that fall within the larger grid body Unfortunately, for many tile sets, simple global con-
are pinned so that, should a block realization succeed, the straints, tile distribution or sparse initial configuration re-
block can be re-integrated back into the larger grid. Should strictions are enough to confound POMS into failing to find
block level realization fail, depending on the type of block a realization. Different choices for block scheduling policies,
realization failure, either the failed block region is set to different block resolution algorithms and other parameter
an indeterminate state or the block region is restored to its choices can help mitigate these shortcomings and will be
briefly addressed (Section 4).
11th Experimental Artificial Intelligence in Games Workshop, November
19, 2024, Lexington, Kentucky, USA.
$ zzyzek@thumpernet.com (Z. Zzyzek)
1.2. Definitions
https://zzyzek.github.io/ (Z. Zzyzek) We discuss some preliminary ideas before describing details
0009-0005-2175-1166 (Z. Zzyzek)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License of the Punch Out Model Synthesis (POMS) algorithm.
Attribution 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Figure 1: Examples outputs of Punch Out Model Synthesis (POMS) run on different tile sets. From left to right, the Pill Mortal
tile set, the Forest Micro tile set, the Overhead Action RPG Overworld tile set and the Brutal Plum tile set
A grid is a collection of cells in the shape of a rectangular block it is trying to solve by propagating constraints and
cuboid, of size 𝑁𝑥 · 𝑁𝑦 · 𝑁𝑧 , (𝑁𝑥 , 𝑁𝑦 , 𝑁𝑧 ∈ N). maintaining arc consistency throughout its run. A grid level
Each cell in the grid is a variable whose domain is 𝐷 tiles solver need not keep full state of the grid and often will
(𝐷 ∈ N). Values in neighboring cells are subject to a set of only keep minimal information about whether a grid cell is
provided tile constraints. Here, the set of tile constraints is resolved or is in an indeterminate state. A block level solver
pairwise, and only nearest neighbor in each of the major typically needs more resources as, for example, it might
grid dimensions (±𝑋, ±𝑌, ±𝑍). maintain a memory intensive data structure associated with
A tile at a grid cell location is said to have support from a maintaining arc consistency.
direction if there is at least one tile in the neighboring grid POMS is a grid level solver with one of its input param-
cell direction that respects the tile constraints. A tile, at a eters designated to specify which underlying block level
grid cell location, has support or is supported if a tile has solver to use. In this paper we use Breakout Model Synthesis
support in each direction. (BMS), a stochastic block level solver introduced in Hoet-
A cell is said to be resolved if there is only one tile present zlein’s just_math project [1]. For completeness, pseudo-
and the tile has support from its neighbors. Should every code for Breakout Model Synthesis is given in Appendix A.
cell in the grid be resolved, the grid is said to be resolved. Note that since POMS is a grid level solver, the grid can be
Should a cell hold no tiles, the grid is then said to be in a in an arc inconsistent state during the course of the algorithm.
contradictory state. This poses no problem in and of itself as the block level
The set of 𝐷 tiles is called the tile domain. The set of solver will attempt to put the block in an arc consistent
available tile options at a cell is called the cell’s tile domain state while trying to make progress towards a fully resolved
and represents the available tiles that can be placed at a grid.
given cell location.
The problem of Constraint Based Tiling Generation
(CBTG) is to find a single tile assignment to each grid cell 2. Related Work
location subject to the tile constraints. That is, resolve every
To our knowledge, Merrell was the first to introduce the
cell in the grid.
modern formulation of Constraint Based Tiling Generation
It is sometimes desirable to pick out a sub region from a
(CBTG) 1 [3, 4]. Merrell introduced a Modify in Blocks Model
grid for special consideration. Here we identify a block as a
Synthesis (MMS) algorithm that starts with a fully resolved
sub region of cells from the grid. Our concern is with blocks
grid and applies a one shot block level constraint solver on
that are rectangular cuboid in shape, of size 𝑀𝑥 , 𝑀𝑦 , 𝑀𝑧 ∈
sub-blocks within the grid.
N, and that can be smaller than the grid size (1 ≤ 𝑀𝑥 ≤
Merrell noticed that the block level algorithm undergoes
𝑁𝑥 , 1 ≤ 𝑀𝑦 ≤ 𝑁𝑦 , 1 ≤ 𝑀𝑧 ≤ 𝑁𝑧 ).
a phase transition of solvability 2 , with a decreasing proba-
If every tile in every cell in a block is supported, the block
bility for successful block resolution as block size increases.
of cells is said to be in an Arc Consistent (AC) state. That is,
Instead of attempting to resolve a large grid in one try, the
subject to the tile constraints, if every tile in every cell in
MMS algorithm progressively resolves sub-blocks and re-
a block region has at least one valid neighboring tile, the
integrates them back into the grid. If a block level resolution
block region is said to be in an arc consistent state.
fails, the block is discarded without altering the grid and
One method of attempting to put a block region into an
another block is chosen.
arc consistent state is to remove tiles that have no support
For many problems, MMS is ideal as it always keeps a full
from the list of permissible tiles at a cell location. Each tile
resolution of the grid throughout its run. Merrell introduced
removed can have a cascading effect by potentially causing
a sequential overlapping schedule for block choice and, for
a tile in a neighboring cell to be unsupported. The repeated
some suitable assumptions on block size and underlying
process of removing unsupported tiles throughout a block
distribution, the mixing time can be quick, requiring only a
region until a contradiction is encountered or the block
few passes through the grid.
region is in an arc consistent state is called constraint propa-
gation. Constraint propagation can be used as the basis for 1
The term Constraint Based Tile Generators was coined by Adam Newgas
a Constraint Based Tiling Generation (CBTG) solver. [2] and has been adopted in this paper, with slightly different wording,
In this paper, we define two distinct classes of solvers that as the name for the specialization of the more general Constraint
Satisfaction Problem.
we call block level solvers and grid level solvers. We define a 2
Note that the phase transition is only for fallible models. Infallible
block level solver as an algorithm that keeps full state of the models will be discussed briefly later in this section.
Unfortunately, MMS has two major drawbacks, the sec- WFC BMS MMS POMS
Solver Type Block Block Grid Grid
ond of which Merrell noticed and discussed in his thesis:
Contradiction
No Yes Yes Yes
Resilience
• The requirement of an initially resolved state to start
Block Step
MMS might be difficult to achieve, either in a practi- Consistent
n/a n/a Yes No
cal or theoretical sense. Indeterminate
• Features bigger than the chosen block size will be Yes Yes No Yes
Initial State
missed by MMS as there is no way to realize larger Ergodic Yes Yes No Yes
features through a single block level alteration.
Table 1
WFC: Gumin’s Wave Function Collapse
Many of the tile sets and tile constraints that Merrell
BMS : Breakout Model Synthesis
provides in [3, 4] have an “empty” tile that has itself as an MMS: Merrell’s Modify in Blocks Model Synthesis
admissible neighbor, creating a situation where the initial POMS: Punch Out Model Synthesis (our algorithm)
fully resolved grid can be easily created by populating each
cell with an “empty” tile. All 2D tile sets and tile constraints
presented in this paper do not have a valid resolution with
in general, all solution states are possibly to reach. Note that
a single replicated tile and require some amount of knowl-
an assertion of being ergodic in this context only means solu-
edge about the tile constraints to create a fully resolved
tions are possible and does not mean unbiased as, depending
configuration.
on the tile constraints or configuration, solution biasing may
In general, for some tile constraints, finding a class of
occur. The features of Punch Out Model Synthesis (POMS)
fully resolved initial configurations might be done through
in Table 1 are highlighted for ease of comparison.
engineering effort. For example, it might be possible to
In terms of algorithms to ensure arc consistency, Merrell’s
find a small tileable block that is then able to be replicated
implementation of MMS [7] and Gumin’s implementation of
through to the whole grid 3 .
WFC [5] have used AC3 and AC4. AC3 is easy to understand
The inability to handle certain types of unbounded con-
and can be performant if tile count is low but quickly suffers
straints, such as the implicit top and bottom equal river
as tile count increases [8]. AC4 is optimal, in general, but
count constraint that appear in Woźniak’s Forest Micro tile
requires large amounts of auxiliary space [9]. The reference
set (section 4), is the deeper issue with MMS. Choosing a
implementation of POMS uses AC4 exclusively as tile count
small block size for MMS could miss novel features whereas
is often large (1,000 or more).
too large of a block size either decreases the likelihood of
CBTGs are a specialization of a more general Constraint
block resolution or turns MMS into a block level solver.
Satisfaction Problem (CSP). Karth and Smith offer some
Gumin introduced the Wave Function Collapse (WFC)
history of CSPs, some common concepts and algorithms
project which improved the block level solver used in MMS
in [10, 11]. Of note is Karth and Smith’s observation that
and added facilities for automatic tile constraint deduction
shallow backtracking does little to help resolve conflicts.
from exemplar scenes [5]. WFC uses a principle of maximum
Two areas of research activity for CBTGs are attempts
entropy heuristic 4 to choose which cells to resolve. Though
to make infinite CBTG algorithms and attempts at giving
extensions are possible, WFC as presented by Gumin is a
more control over created output. Kleinberg provides an
one-shot block level solver, giving up should a contradiction
algorithm for infinite WFC by chaining blocks together [12].
be encountered.
While this can produce large scenes, the tile constraints are
Since MMS is a grid level solver, other block level solvers
conditioned so that failure probability is low and Kleinberg
can be used, such as WFC, to resolve underlying blocks,
admits that block resolution can fail without any recourse
with modifications added to allow for constraints, boundary
on how to continue.
conditions and other relevant features. Merrell provides a
Of note is Merrell’s discussion of infallible models [4],
comparison between MMS and WFC in [6].
where the tile constraints are conditioned so as to never
Breakout Model Synthesis (BMS) was introduced in Hoet-
be able to encounter a contradiction. For infallible models,
zlein’s just_math project [1]. Hoetzlein’s just_math
infinite block chaining is always achievable as there is no
project also introduced the Tile Arc Consistent Correlation
possibility of a contradiction occurring. Though infallible
Length (TACCL) after noticing that knowledge of the tile
models represent a case that is always solvable, it’s unclear
correlation length could be used to create algorithms that
how possible or how difficult it is convert tile constraints
took advantage of it. POMS takes the ideas of tile correla-
from exemplar scenes to infallible models. In particular, all
tion and the TACCL to inform its stochastic backtracking
tile sets considered in this paper are fallible models.
strategies when applied to the larger grid without needing
Newgas provides Tessera, a software project that imple-
the resource requirements that BMS, as a block level solver,
ments WFC along with options for a variety of constraints
would require.
[13]. Nie et al. provide an extension to WFC to infinite
Table 1 provides a summary of the differences between
grids but require the tile set to be complete or sub-complete
WFC, BMS, MMS and POMS. Here, contradiction resilience
[14] which may be difficult for tile sets in the wild. Cooper
means that the algorithm can recover should a contradiction
introduces Sturgeon that incorporates a mid level API to
be encountered, block step consistent means the algorithm is
specify more explicit and longer range constraints as an ad-
in an arc consistent state after every block resolution, inde-
dition to WFC [15]. Though Cooper’s Sturgeon program
terminate initial state means the algorithm doesn’t require a
and ideas look promising, the sizes involved are relatively
fully resolved initial configuration and ergodic means that,
small (40x40 and below) and it’s unclear how well the con-
3
This method was suggested through personal communication with P. straints would work on various tile sets, initial conditions
Merrell. or how well the method would scale for larger level sizes.
4
Using a principle of maximum entropy implies picking a cell to resolve Alaka and Bidarra attempt to offer more control over out-
of minimum entropy at each step.
put level design by considering a user interface to group tiles Synthesis (BMS) [1] for the underlying block level resolution
and weight individual tile probabilities into user specified algorithm.
regions [16]. Langendam and Bidarra attempt to offer more Each block chosen has its boundary pinned to the values
control over output levels through a mixed initiative graphic as they appear in the grid, except if the block boundary falls
tool that offers the ability to interact with the underlying on the grid boundary. Here, pinning means setting a cell’s
WFC solver in various ways [17]. tile domain to a certain set of values and not allowing any
Of note is Lucas and Volz’s straight forward application of constraint propagation to be performed on the cell. The
counting tile frequency and measuring the Kullback-Leibler pinned cell’s tile domain can affect a neighboring cell tile
divergence to attempt to get a better understanding of how but is otherwise not considered for constraint propagation.
biased the resulting generated map is [18]. Karth and Smith Pinning ensures that the block can integrate into the larger
use a vector-quantized variational auto encoder (VQ-VAE) grid by guaranteeing the boundary conditions of the block
to create reduced tile domain maps which can then be input match the related regions in the grid.
into WFC to produce novel results [10]. If the block and grid share a boundary, the tiles at the
Though automatic tile constraint creation and constraint cell boundaries are not pinned but are subject to boundary
based tiling generation are distinct ideas, they are often bun- conditions. Here, we only consider boundary conditions
dled together as manually creating tile constraints can be where a fixed tile is used when neighboring constraints
labor intensive and the resulting tile constraints are an input would fall out of grid bounds.
requirement to constraint based tiling generation problems. Block regions are chosen by a Block Choice Scheduler
Gumin’s Wave Function Collapse project highlighted an au- (BCS) as referenced in Algorithm 1. From our experimenta-
tomatic tile constraint creation from exemplar scenes [5]. tion, the BCS is problem specific and will be discussed later
Many resources exist to explain automatic tile constraint (Section 4).
creation in detail but of note are Sherrat’s summary in [19] Once a block is chosen, the block is initialized by adding
and an introduction by Newgas in [20]. We briefly go over the full tile domain of tile values to every cell in the block,
automatic tile constraint generation in more detail later in applying setup restrictions and then running an initial con-
this paper (Section 4). straint propagation that attempts to put the block in an
arc consistent state. The setup restrictions only allow for
tiles to be added, removed or pinned on an individual cell.
3. Algorithm Once setup restrictions are imposed, an attempt is made to
run the constraint propagation and put the block in an arc
3.1. Punch Out Model Synthesis consistent state.
Punch Out Model Synthesis (POMS) works to progressively If the block is successfully put in an initial arc consistent
resolve chosen blocks within a larger grid. Blocks that fully state, the block level resolution algorithm proceeds and
resolve are then saved back into the larger grid. Should attempts to find a fully realized block. If a fully realized
blocks not be able to fully resolve, portions of the grid are block is found, it’s put back into the grid and the algorithm
reverted back to an indeterminate state, depending on the continues on by choosing another block to process.
mode of failure. If the initial block level arc consistency attempt succeeded
but the block level resolution algorithm failed to find a fully
Algorithm 1 Punch Out Model Synthesis realized block, boundary tiles of fully resolved regions in the
whole grid are probabilistically reverted to an indeterminate
Input,Output: Grid 𝐺,
state. The process of probabilistically reverting boundary
Input: Block Choice Scheduler, 𝐵𝐶𝑆,
cell locations to indeterminate states is called erosion, with
Input: Erosion Choice Scheduler, 𝐸𝐶𝑆,
the probability of erosion being a tunable parameter that sets
Input: Block Solver Algorithm, 𝐴
the probability that a cell located on a resolved boundary is
Set 𝐺 to a fully indeterminate state
reverted.
while 𝐺 not fully resolved do
Should the initial attempt to put the block choice into an
Choose block 𝐵 in 𝐺 by querying 𝐵𝐶𝑆
arc consistent state fail, the block region is reverted to an
Initialize 𝐵 to indeterminate state
indeterminate state in the grid. The motivation for reverting
From 𝐺, set and pin 𝐵 edges not on 𝐺 boundary
the whole block region, as opposed to just relying on erosion,
Apply initial setup restrictions to 𝐵
is that if a block cannot be put into an initial arc consistent
Run 𝐴(𝐵) ◁ Attempt to resolve 𝐵 with 𝐴
state, subject to its pinned boundary values, there might be
if initial arc consistency is impossible for 𝐵 then
a strong contradiction that requires an aggressive back-off
Set 𝐵 region to indeterminate state in 𝐺
strategy.
else if 𝐴(𝐵) fails to find a full resolution in 𝐵 then
Algorithm 1 gives pseudo code for the Punch Out Model
Erode boundaries in 𝐺 using 𝐸𝐶𝑆
Synthesis (POMS) algorithm. Figure 2 gives an overview
else ◁ success
of the POMS algorithm, highlighting a single step. Figure
Copy fully resolved tiles from 𝐵 into 𝐺
3 shows a slideshow of POMS being run on the Pill Mortal
end if
tile set for a 64x64 grid size with a 32x32 block size.
end while
The probability of erosion is managed by the Erosion
Choice Scheduler (ECS) as referenced in Algorithm 1. We
POMS retains a copy of the larger grid, keeping either have found that a good choice for ECS is to increase the ero-
the fully resolved tile per cell or an indicator that the cell is sion probability by the number of failed attempts, allowing
in an indeterminate state. Each round consists of choosing for a more aggressive erosion should block resolution be-
a block from some block choice scheduler and doing full come increasingly difficult. Without the erosion, block level
block level resolution from some underlying block level solvers could perpetually attempt resolution on blocks with
algorithm. In this paper, we only consider Breakout Model identical initial state. The erosion provides a backtracking
a) Grid partially realized, b) Initialize block, pinning c) Aempt to run
choose block overlapping boundaries block solver
Legend
boundary
resolved
unresolved (grid)
unresolved (block)
pinned
d) Success e) Resolution failure, ) Setup failure,
incorporate resolved block into grid restore block and erode revert block area in grid to unresolved
resolved area boundaries
Figure 2: a) A block is chosen in the partially resolved grid, based on a block choice scheduler b) Once the block is chosen, the
boundary is pinned if not on the a grid boundary and the center put into an indeterminate state. c) The block level solver
attempts to find a solution for the block, with any pinned boundary restrictions d) If successful, the block is incorporated
back into the grid. e) If the block solver algorithm failed to resolve, after some maximum iteration count, say, then the grid is
restored to its previous state and resolved boundaries are eroded based on an erosion choice scheduler. f) If the block solver
algorithm failed to start because the block could not be put into an arc consistent state given the tiles pinned on the boundary,
the block area in the grid is reverted to an indeterminate state.
Figure 3: A slideshow of POMS run on the Pill Mortal tile set. The block size is 32x32 and the grid size is 64x64 with a block
choice policy that chooses block centers uniformly at random from the available unresolved cell locations in the grid.
mechanism, allowing for a change in initial state of chosen the grid, allowing block sizes to be tuned as resources allow.
blocks and removal of implied contradictions that can occur
from previously resolved regions in the grid. 3.2. Tile Arc Consistent Correlation Length
Maximum iteration counts can be added so that POMS or
the underlying block level resolution algorithm (𝐴) don’t Choosing a block size for POMS is informed by the tile
loop forever. The iteration counts and other checks in Algo- correlation length, as block sizes below the the tile cor-
rithm 1 have been omitted for brevity. relation length run the risk of getting trapped in a local
Since the grid only keeps one value per cell and full con- energy minima without the possibility of escape. As a
straint propagation is done on a block level, only a block heuristic to estimate the tile correlation length, Hoetzlein’s
level’s worth of data need be kept in active memory. Full just_math project [1] proposed a Tile Arc Consistent Cor-
constraint propagation is done on an individual block level relation Length (TACCL).
but the block size can be chosen to be much smaller than The computation of the TACCL is done as a pre-
processing step independent of the POMS algorithm. The
idea is to iterate through each tile in isolation and record the
maximum distance constraint propagation reaches when
resolving a center cell.
Starting from a small test grid set to an indeterminate
state, the center cell is resolved to a tile and constraint prop-
agation is performed to put the grid into an arc consistent
state. The size of a bounding box that minimally encom-
passes every cell whose tile domain was altered during the
constraint propagation is then saved. The grid is then re-
verted to an indeterminate state and the next tile is chosen
to resolve, repeating the process and updating the maximum
distances of the minimum encompassing bounding box for
each tile tested.
The TACCL is the maximum extent of the saved bounding
boxes from iterating through all tiles. Algorithm 2 provides
pseudo-code for the TACCL calculation.
Algorithm 2 Tile Arc Consistent Correlation Length
Output: Tile Arc Consistent Correlation Length 𝐿
Input: Block Size (𝑀𝑥 , 𝑀𝑦 , 𝑀𝑧 )
Create a block 𝐵 of size (𝑀𝑥 , 𝑀𝑦 , 𝑀𝑧 ) Figure 4: a) Exemplar image with a single tile and its neighbors
Put block 𝐵 in a fully indeterminate state highlighted. b) The packed image inferred tile set with the rel-
𝐿=1 evant tile highlighted. c) The catalog of 2x2 super tiles used to
for tile every tile 𝑡 ∈ 𝐷 do create the tile constraints from the 1x2 tile overlap, suitably ro-
𝐵′ = 𝐵 tated. The same tile highlighted in a) and b) has been highlighted
here for comparison.
Apply initial setup restrictions to 𝐵 ′
Resolve center cell, 𝑐, in 𝐵 ′ to 𝑡
Make 𝐵 ′ arc consistent
Find minimum bounding box, 𝑏𝑏𝑜𝑥, 4.1. Automatic Tile Constraint Creation
encompassing altered cells of 𝐵 ′
The four 2D tile sets used in this paper had their tile con-
if max𝑥,𝑦,𝑧 𝑏𝑏𝑜𝑥 > 𝐿 then
straints inferred from an exemplar image using an auto-
𝐿 = max𝑥,𝑦,𝑧 𝑏𝑏𝑜𝑥
mated tile constraint generation method. The exemplar
end if
image is split into tiles and a sliding super tile window, of a
end for
larger size than the tile itself, is moved over the exemplar
Return 𝐿
image. The super tiles are deduplicated and checked for
overlapping bands to other super tiles. For every matching,
For the sake of brevity, no checks are performed in Al- overlapping band, a tile constraint is added, allowing an
gorithm 2 to determine if the calculated value is as large as admissible pairing for the tiles in the appropriate dimension
the input block size (𝑀𝑥 , 𝑀𝑦 , 𝑀𝑧 ). In such a case, either direction.
the TACCL is unbounded or the test block size is smaller Figure 4 shows the exemplar image (a), the inferred tile
than the TACCL and the test block size would need to be set (b) and the complete list of super tiles for Woźniak’s
increased. Forest Micro tile set (c). A single tile is highlighted in red
The TACCL is meant to estimate the correlation length and its neighbors are highlighted in yellow with red edges
of an underlying tile constraint set but can be misleading as corresponding to their neighboring direction.
some tile constraints will have a finite TACCL even though Figure 4 uses a tile size of 8x8 pixels, with a 2x2 super
correlation lengths can be unbounded. An unbounded tile size. The upper left hand tile is used as the displayed
TACCL implies an unbounded correlation length but the representative tile, which can be seen by comparing the non
converse is not true and a finite TACCL does not neces- dimmed tiles in the super tile list from Figure 4 (c) to the
sarily imply a finite correlation length. The Brutal Plum packed tile set image (b). A 1x2 overlapping band is tested
tile set, that has an unbounded correlation length but finite for equality in each direction, suitably rotated, to find which
TACCL, displays this phenomenon and will be discussed super tiles neighbor other super tiles. An interested reader
later (Section 4). can confirm that there is a 1x2 overlap to the highlighted
red super tile to each of its highlighted yellow neighbors in
4. Results Figure 4.
Boundary constraints need special consideration. One
In this section, we highlight five tile sets that represent option is to only allow a special “zero” tile at grid boundaries,
different aspects of the benefits and pitfalls of the Punch ensuring “zero” tile constraints are added for tile pairs that
Out Model Synthesis (POMS) algorithm. fall across the edge boundaries of the exemplar image. This
We start with a brief review of the automatic tile con- is the option chosen for Woźniak’s Forest Micro tile set and
straint creation. Though automatic tile constraint creation can be seen in the “zero” (gray) tiles present for the super
is a distinct topic from Constraint Based Tiling Generation tiles listed in Figure 4 (c). Another option is to have wrap
(CBTG), the two are closely related as any CBTG algorithm around boundary conditions, with a sliding window that
requires a tile constraint set to run. wraps right or up to left or down directions, respectively,
and is the method chosen when creating the tile constraints 4.2. Tile Constraints with Bounded TACCL
for LUNARSIGNALS’ Overhead Action RPG Overworld tile
The first two tile sets that appear in Figure 5, Pill Mor-
set.
tal and LUNARSIGNALS’ Overhead Action RPG Overworld
If the tile constraints include the “zero” tile at the grid
(OARPGO) tile set, have bounded Tile Arc Consistent Cor-
boundaries, this will be denoted as hard boundary conditions.
relation lengths (TACCL).
For the automatic tile constraint creation from exemplar
The Pill Mortal tile constraints were generated from the
images, some artistic input is needed in choosing tile size,
exemplar image shown (Figure 5, label b), using an 8x8px
window size and boundary conditions. The tile sizes, win-
tile size, hard boundary conditions with a 2x2 super tile
dow sizes and boundary conditions for the 2D tile sets used
window, a 1x2 tile overlap and the upper left hand corner tile
in this paper were chosen through inspection and experi-
as the representative display tile. The generated realization
mentation. An in depth explanation of automatic tile con-
in Figure 5 (label c) was created from a POMS run with
straint creation is beyond the scope of this paper and readers
block size 32x32 on a 128x128 grid. A uniform block choice
are referred to [5, 19, 20] for further details.
scheduler policy was chosen that selected block centers
PM OARPGO FM 2BMMV BP uniformly at random from the set all unresolved grid cells.
Dimension 2D 2D 2D 2D 3D LUNARSIGNALS’ OARPGO tile constraints were gener-
Tile Size (px) 8px 16px 16px 24px n/a ated from the exemplar image shown (Figure 5, label e),
Super Tile using an 16x16px tile size, wrap around conditions with a
Window 2x2 3x3 2x2 2x2 n/a 3x3 super tile window, 2x3 tile overlap and the middle tile
Overlap 1x2 2x3 1x2 1x2 n/a as the representative display tile. In this case, a 3x3 window
Tile Count 190 3031 159 1807 90 was chosen as a smaller 2x2 window was observed to not
Boundary give good aesthetic results.
Conditions When generating outputs using the OARPGO tile set, the
Hard ✓ ✓ ✓ ✓
outer frame of the grid is pinned to an unresolved state. This
Wrap ✓
is necessary as the tile constraint set was created with wrap
Block Choice
Scheduler around conditions and has no valid constraints that match
Uniform ✓ ✓ ✓ the “zero” tile to the rest of the tile domain.
Diagonal ✓ The example 256x256 output (Figure 5, label f ) was cre-
Center Out ✓ ated with a block size of 50x70. A block choice strategy
TACCL (x/y) 24 50/70 ∞ ∞ 16 was used that preferentially chose block centers from unre-
Soften Size 8 12-24 8 8-24 1-8 solved grid cells nearer to the center. This has the effect of
Block Size 32 50x70 48 48 22 resolving regions from the center out, never creating isolated
Table 2 regions that need to be joined and effectively ensuring a
Pill Mortal (PM) tile set large contiguous region during the course of the algorithm.
Overhead Action RPG Overworld (OARPGO) tile set [21] From observation, other block choice strategies were not as
Forest Micro (FM) tile set [22] successful as choosing block centers with a grid center bias.
Two Bit Micro Metroidvania (2BMMV) tile set [23] It should be noted that without wrap around boundary
Brutal Plum (BP) tile set conditions, the OARPGO tile set would have unbounded
TACCL. Further, without wrap around boundary condi-
Table 2 provides summary information for five tile sets, tions POMS has trouble finding solutions as the grid bound-
Pill Mortal, Overhead Action RPG Overworld, Forest Micro, ary region is non trivial for this tile set. The success of
Two Bit Micro Metroidvania and Brutal Plum, highlighted the center out block choice strategy, the failure of other
in this paper. The tile size, super tile window size, super block choice strategies and the unbounded TACCL of non
tile window overlap parameter and boundary conditions are wrap around boundary conditions, could suggest that the
provided as they are used in the automatic tile constraint bounded TACCL does not capture some longer range or
generation for the resulting tile counts listed. Also provided unbounded constraints embedded within the wrap around
are the Block Choice Scheduler (BCS), soften size and blocks OARPGO tile set constraints.
sizes that were used to generate the example outputs in Of note is the “stuttering” effect that happens with many
Figure 5 and Figure 6. features being repeated in a linear direction. For example,
Here, the uniform BCS denotes a block choice schedule there are long regions of vertical rocks surrounded by water
that randomly chooses a block center uniformly from inde- tiles that continue on downward until the pinned boundary
terminate cells in the grid. A diagonal BCS denotes block is hit. This effect becomes even more pronounced when
center choices weighted preferentially to the upper left other tile weightings are used. We suspect this is because
corner and center out BCS denotes block center choices of a certain pattern preference that then gets re-enforced
weighted preferentially towards the center of the grid. by a surrounding structure. We make note of this effect but
The soften size is specific to the Breakout Model Synthe- otherwise don’t investigate further in this paper.
sis (BMS) block level solver and the values shown in Table
2 were chosen through experimentation. We document the 4.3. Tile Constraints with Unbounded
soften size for completeness but a more thorough investiga- TACCL
tion of the soften size’s impact on solvability is beyond the
scope of this paper. The last two tile sets in Figure 5, Woźniak’s Forest Micro
We group the 2D tile sets into bounded and unbounded tile set and 0x72’s Two Bit Micro Metroidvania tile set, both
TACCL, with special consideration for the Brutal Plum tile have unbounded Tile Arc Consistent Correlation Lengths
set. (TACCL).
a) d)
c) f)
b) e)
g) j)
i) l)
h)
k)
Figure 5: Tile Arc Consistent Correlation Length (TACCL) plots, source exemplar image and example output for four 2D tile
sets as listed in Table 2. The TACCL, exemplar image and example 64x64 output using a block size of 8x8 for the Pill Mortal tile
set are shown in a), b) and c) respectively. The TACCL, exemplar image and an example 256x256 output using a block size of
50x70 for LUNARSIGNALS’ Overhead Action RPG Overworld are shown in d), e) and f) respectively. The TACCL, exemplar
image and an example 128x128 output using a block size of 48x48 for Woźniak’s Forest Micro tile set are shown in g), h) and i)
respectively. The TACCL, exemplar image and an example 128x128 output using a block size of 48x48 for 0x72’s Two Bit Micro
Metroidvania tile set are shown in j), k), l) respectively.
The tile constraints for Woźniak’s Forest Micro tile set The diagonal weighting has the effect of keeping a growing
were generated from the exemplar image shown (Figure 5, contiguous region that locally keeps the top and bottom
label h), using an 16x16px tile size, hard boundary condi- river counts the same. Contradictions that do occur tend to
tions with a 2x2 super tile window, a 1x2 tile overlap and be localized and their resolution keeps the river counts the
taking the upper left hand corner tile as the representative same
display tile. The generated realization in Figure 5 (label i) Though the Forest Micro tile set has an unbounded cor-
was created from a POMS run with block size 48x48 on a relation length, the global constraint is weak enough to be
128x128 grid. A diagonal weighted block choice scheduler overcome by this simple weighted diagonal heuristic.
policy was chosen that selected block centers from the set all The tile constraint set for 0x72’s Two Bit Micro Metroid-
unresolved grid cells weighted by their Euclidean distance vania (2BMMV) tile set was generated from the exemplar
to the upper left corner of the grid. image shown (Figure 5, label k) with a 24x24 pixel tile size,
From the local, nearest neighbor pairwise tile constraints, a 2x2 super tile window using a 1x2 tile overlap and taking
the Forest Micro tile set has an implied global constraint the upper left hand corner tile as the representative display
that the river count from the top row of the realized grid tile.
must match the river count on the bottom row. This global As can be seen by Figure 5 (label j), the 2BMMV tile set has
constraint is not explicitly present or specified but is a by- unbounded correlation length, but the constraint is weak
product of the local constraints. enough to be overcome by running POMS with a block size
For large grid sizes, POMS fails to find realizations for of 48x48 and a block choice scheduler that chooses block
the Forest Micro tile set when a block choice policy chooses centers from unresolved grid cell positions uniformly. An
block centers at random. Under these conditions, POMS example output for the 2BMMV for a 128x128 grid using
effectively makes a random choice for the number of rivers a 48x48 block size and uniform block choice schedule can
on the top and bottom row. One can expect, with enough be seen in Figure 5 (label l). The unbounded correlation
random sampling, the river count to be identical, but the length comes from the boundary restrictions which might
problem becomes increasingly less likely as grid size grows. disappear if care were taken to create wrap around tile
To guide POMS in finding solutions for the Forest Micro constraints.
tile set, a block choice policy was chosen that preferentially
weights cell positions starting from the upper left and de-
creases as cells are considered going down and to the right.
a) b) tile constraints that have finite correlation length. We have
also shown that POMS is able to find realizations for some
problems that have weak implied global constraints. If the
tile set and configuration are not conditioned well, POMS
may fail to find a solution or provide biased results.
Tile constraints that have unbounded or long range cor-
relations are more difficult and sometimes intractable. Con-
straint Based Tiling Generation problems are, in general,
NP-Complete, so there is likely no comprehensive strategy
c) that leads to efficient methods of solution but the worst
case complexity results sometimes obscure when problems
are readily solvable. For many CBTG problems that are
NP-Complete, the general complexity result might not ap-
ply to some generic configuration, allowing some problem
ensembles to be easily solvable.
For many real world CBTG problems, we still lack under-
standing of the interplay between how difficult it is to find
realizations given tile constraints and initial configuration.
The Tile Arc Consistent Correlation Length (TACCL) is one
heuristic measure that attempts to quantify how difficult
tile constraints are to resolve. The TACCL has the benefit
of being easy to calculate but its interpretation is easily con-
founded, so should be considered a coarse measure with
limited applicability.
A libre/free reference implementation for Punch Out
Model Synthesis (POMS) has been developed and can be
downloaded from its repository 5 .
Figure 6: The Tile Arc Consistent Correlation Length (TACCL)
plot, source tile set and an example 32x32x32 output for the 3d
References
Brutal Plum tile set listed in a), b) and c) respectively. A block size
[1] R. Hoetzlein, just_math, 2023. URL:
of 22x22x22 was used.
https://github.com/ramakarl/just_math/tree/
3ff9d10c3d170855cef1db970c0278b15e91fa13/math_
belief_prop.
4.4. Unbounded Correlation Length but [2] A. Newgas, Constraint-based tile generators, 2021.
Bounded TACCL URL: https://www.boristhebrave.com/2021/10/31/
constraint-based-tile-generators/.
The 3D Brutal Plum tile set was programmatically generated
[3] P. Merrell, Example-based model synthesis, in: Pro-
from a set of 20 unique tiles that, after rotations and dedupli-
ceedings of the 2007 Symposium on Interactive 3D
cation, grows to 90 tiles. Many of the tiles are aesthetically
Graphics and Games, I3D ’07, Association for Comput-
identical but are logically different to embed desired fea-
ing Machinery, New York, NY, USA, 2007, p. 105–112.
tures, such as requiring certain logical tiles to be above or
URL: https://doi.org/10.1145/1230100.1230119. doi:10.
below other tiles. In particular, non empty tiles must have a
1145/1230100.1230119.
non empty path to the ground base plane, giving an implied
[4] P. Merrell, Model Synthesis, Ph.D. thesis, Chapel Hill,
global constraint. The global constraint is not captured by
NC, USA, 2009.
the Tile Arc Consistent Correlation Length (TACCL) and
[5] M. Gumin, Wave function collapse algo-
highlights the failure of the TACCL heuristic to properly
rithm, 2016. URL: https://github.com/mxgmn/
capture an unbounded correlation length embedded in the
WaveFunctionCollapse.
tile set.
[6] P. Merrell, Comparing model synthesis and wave
Though the correlation length for the Brutal Plum tile
function collapse, 2021. URL: https://paulmerrell.org/
constraints is unbounded, POMS still is able to reliably find
wp-content/uploads/2021/07/comparison.pdf.
realizations with block size 22x22x22, an example output
[7] P. Merrell, Model synthesis, 2021. URL: https://github.
of which is highlighted in Figure 6 (label c). For aesthetic
com/merrell42/model-synthesis.
reasons, a tile weighting that increases the likelihood of the
[8] R. J. Wallace, Why ac-3 is almost always better than
empty tile, the arch tiles and stair tiles was chosen. The
ac4 for establishing arc consistency in csps, in: In-
reader is referred to the reference implementation 5 for
ternational Joint Conference on Artificial Intelligence,
further details.
1993. URL: https://api.semanticscholar.org/CorpusID:
17765393.
5. Conclusion [9] R. Mohr, T. C. Henderson, Arc and path
consistency revisited, Artificial Intelligence 28
Punch Out Model Synthesis (POMS) provides an algorithm (1986) 225–233. URL: https://www.sciencedirect.com/
for the Constraint Based Tiling Generation (CBTG) problem. science/article/pii/0004370286900834. doi:https://
We have shown that POMS can discover realizations from doi.org/10.1016/0004-3702(86)90083-4.
5 [10] I. Karth, A. M. Smith, Wavefunctioncollapse is con-
https://github.com/zzyzek/PunchOutModelSynthesis.
straint solving in the wild, in: Proceedings of 2bitmicrometroidvaniatileset.
the 12th International Conference on the Founda-
tions of Digital Games, FDG ’17, Association for
Computing Machinery, New York, NY, USA, 2017.
URL: https://doi.org/10.1145/3102071.3110566. doi:10.
A. Appendix: Breakout Model
1145/3102071.3110566. Synthesis (BMS)
[11] I. Karth, A. M. Smith, Wavefunctioncollapse: Content
generation via constraint solving and machine learn-
ing, IEEE Transactions on Games 14 (2022) 364–376. Algorithm 3 Breakout Model Synthesis
doi:10.1109/TG.2021.3076368. Input,Output: Block 𝐵,
[12] M. Kleineberg, Infinite procedurally generated city Input: Setup restrictions 𝑆,
with the wave function collapse algorithm, 2019. URL: Input: Tile constraints 𝐶,
https://marian42.de/article/wfc/. Input: Tile Choice Scheduler 𝑇 𝐶𝑆
[13] A. Newgas, Tessera: A practical system for ex- Input: Soften Choice Scheduler 𝑆𝐶𝑆
tended wavefunctioncollapse, in: Proceedings of Put 𝐵 into a fully indeterminate state
the 16th International Conference on the Founda- Apply setup restrictions 𝑆 to 𝐵
tions of Digital Games, FDG ’21, Association for Apply tile constraints 𝐶 until 𝐵 is arc consistent
Computing Machinery, New York, NY, USA, 2021. if unable to create initial arc consistent state then
URL: https://doi.org/10.1145/3472538.3472605. doi:10. return failure
1145/3472538.3472605.
end if
[14] Y. Nie, S. Zheng, Z. Zhuang, X. Song, Extend wave Save copy of 𝐵 to 𝑃
function collapse algorithm to large-scale content while 𝐵 not fully resolved do
generation, in: 2023 IEEE Conference on Games 𝐵′ = 𝐵
(CoG), 2023, pp. 1–8. doi:10.1109/CoG57401.2023. Choose tile and cell to resolve in 𝐵 from 𝑇 𝐶𝑆
10333214.
Propagate resolution until 𝐵 is arc consistent
[15] S. Cooper, Sturgeon: Tile-based procedural level gen- if contradiction encountered then
eration via learned and designed constraints, Proceed- Revert 𝐵 back to 𝐵 ′
ings of the AAAI Conference on Artificial Intelligence Query 𝑆𝐶𝑆 for a sub-region, 𝑅, to soften
and Interactive Digital Entertainment 18 (2022) 26– Revert region 𝑅 in 𝐵 back to 𝑃
36. URL: https://ojs.aaai.org/index.php/AIIDE/article/ Constraint propagate until 𝐵 is arc consistent
view/21944. doi:10.1609/aiide.v18i1.21944. end if
[16] S. Alaka, R. Bidarra, Hierarchical semantic wave func- if iteration count has been exceeded then
tion collapse, in: Proceedings of the 18th International return failure
Conference on the Foundations of Digital Games, FDG end if
’23, Association for Computing Machinery, New York, end while
NY, USA, 2023. URL: https://doi.org/10.1145/3582437. return success
3587209. doi:10.1145/3582437.3587209.
[17] T. S. L. Langendam, R. Bidarra, miwfc - designer em-
powerment through mixed-initiative wave function
collapse, in: Proceedings of the 17th International
Conference on the Foundations of Digital Games, FDG
’22, Association for Computing Machinery, New York,
NY, USA, 2022. URL: https://doi.org/10.1145/3555858.
3563266. doi:10.1145/3555858.3563266.
[18] S. M. Lucas, V. Volz, Tile pattern kl-divergence for
analysing and evolving game levels, in: Proceed-
ings of the Genetic and Evolutionary Computation
Conference, GECCO ’19, Association for Computing
Machinery, New York, NY, USA, 2019, p. 170–178.
URL: https://doi.org/10.1145/3321707.3321781. doi:10.
1145/3321707.3321781.
[19] S. Sherratt, Procedural generation with wave func-
tion collapse, 2019. URL: https://www.gridbugs.org/
wave-function-collapse/.
[20] A. Newgas, Wave function collapse explained,
2021. URL: https://www.boristhebrave.com/2020/04/
13/wave-function-collapse-explained/.
[21] LUNARSIGNALS, Overhead action rpg overworld,
2016. URL: https://opengameart.org/content/
overhead-action-rpg-overworld.
[22] K. Woźniak, Micro tileset - overworld and dun-
geon, 2015. URL: https://opengameart.org/content/
micro-tileset-overworld-and-dungeon.
[23] R. Norenberg, 2bit micro metroidvania
tileset, 2024. URL: https://0x72.itch.io/