Seeded noise lets games generate any region of an unbounded world on demand. We ask what such a generator needs when every small window must come from one example, the constraint behind Wave Function Collapse. The difficulty is that local constraints can require agreement over arbitrary distances: in a brick wall, each row keeps its place between the mortar lines. We study local generators, each cell a fixed function of the randomness near it. When the constraints carry a quantity that varies across the example, no generator that applies one rule, ignoring position, to independent randomness at every cell can be both exactly valid and faithful to the example's statistics, however far each cell reads. At radius r, staying faithful forces forbidden windows at a density of at least order 1/r, and a construction attains this order. To vary the quantity between exactly valid worlds, a generator needs randomness shared along its direction. We give a finitely checkable condition under which row types drawn from the seed and the position modulo a fixed period suffice for exact validity without learning. A search over the example's patches certifies these quantities and names the input each needs. Across 52 public examples of Wave Function Collapse and 27 from other implementations, it certifies only examples where a learned generator on independent randomness stays far from valid after repair. Given that input, a neural cellular automaton and a diffusion model become valid on 10 and 8 of the 12 certified examples that receive one, and on none from independent randomness. Valid means at most one forbidden window in a thousand after repair. With octaves of seeded noise elsewhere, the automaton is valid on 45 of the 52 public examples and 21 of the 27 from other implementations, and repair keeps random access.
Figures & tables
Figure 1: Worlds from one example. Each column shows a public example and the central 64×64 cells of a 256×256 canvas from shifted replay (the example tiled from a random offset), the block reference (a block solver on blocks placed at random), the rule on independent coins and the method (the learned rule given the input of Section 4 ), both mended, with the share of forbidden windows on the whole canvas. On the first five examples validity carries a quantity over any distance, an invariant along rows or a phase. Independent coins leave forbidden windows on all five; given the quantity, the method leaves none, and on Fabric and RedMaze its world is the tiled example. Cave carries no such quantity, and both rules are valid on it.
Figure 2: The row type on Wall, a row’s place relative to the horizontal mortar lines, which validity keeps constant along every row. (a) The example and the row type of each of its rows. (b) The rule on independent coins after repair and mending, each cell tinted by the row type of the window centered on it: the type changes along rows, and the forbidden windows sit where it changes. (c) The method, given row types drawn from the seed, at the same coin seed: every row keeps its type, and no window is forbidden. (d) A mending instance with no completion (Appendix S4.1): of the cells freed around a forbidden window (hatched), two frozen patches on one row carry row types that validity cannot join, a witness (Appendix B.11 ).
Figure 3: The min-coin copy’s share ε of forbidden windows before mending against its radius r : gray lines for the other certified examples with a transported quantity, the purple line for Wall, open circles for Wall after mending. Every line stays below the bound qr of Proposition 2 (dash-dotted) and falls as 1/r , on Wall at about ten times the floor that Theorem 1 sets for a generator with the example’s statistics (dashed); the dotted line is the threshold of validity. Squares mark the independent-coin rule before repair and mending, at its own radius r=32 . Triangles mark the diffusion model of Section 6.5 from noise alone and diamonds the same model given the certificate’s input, at its radius r=300 , filled before mending and open after (purple for Wall, brown for SimpleWall; an arrow means that mending left no forbidden window). Of the model’s markers only the triangles come from a generator on independent coins, which the floor binds; the diamonds read an input shared along whole rows.
generator
role
the min-coin copy
on each cell’s own coins, the floor’s order (Proposition 2 )
shifted replay
the tiled example at one offset drawn from the seed: valid and faithful, one world up to translation
the i.i.d. draw
each cell drawn from its own coins: copies nothing; what mending makes from noise
block-shifted tiles
one offset per block of a fixed lattice: copies with defects on block boundaries
the copier
the row types filled with the example’s rows, one coin per stretch: the input alone
the Metropolis filler
written by hand, on the row types and hashed coins: composition on the input
Table 1: The generators without learning that the text names (Appendix S2.2 defines every generator). All but the block reference and Wave Function Collapse are random access, after mending too by the margin of Section 6.4 . Shifted replay, the block reference, the random-access block solver and Wave Function Collapse skip the mender.
Figure 4: Every public example after mending: the share of forbidden windows on the worst of three canvases for the independent-coin rule (square), the octave rule (pentagon) and the method (circle); on Town and the uncertified examples the method is the octave rule, and only its circle is drawn. The dotted line marks validity, one forbidden window in a thousand; exact zeros sit below the break in the axis. The lower row gives the share of the method’s cells that mending rewrites, and the dashed line its median over the examples the method makes valid. The examples are grouped by class (Section 5 ) and ordered within each by the independent-coin rule; names in bold carry a certificate.
Figure 5: Wall and SimpleWall against the bounds. Each point is one canvas mended within radius 24, at the total variation δ of its 3×3 window statistics from the example’s and its share ε of forbidden windows; exact zeros sit below the break in the axis, and the dotted line is the threshold of validity. Inequality ( 1 ) excludes the light region for every generator on independent coins at the pipeline’s reach, r=804 , and Theorem 2 the dark band at any depth: the zero level left of δ=κf on SimpleWall, and all of it on Wall, where the program of Section 3 stays positive at every δ . On Wall the method’s canvases sit in the dark band, as do those of both copiers, the Metropolis filler and shifted replay, which read inputs shared along whole rows or over the plane, and of Wave Function Collapse, a global solver; the independent-coin and octave rules lie above the threshold. On SimpleWall the octave rule, whose octaves include coins shared along whole rows, has no forbidden window either.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
example
P
L
anchor
alphabet
glue
configu- rations
most at one row
largest set
Wall
3
32
most frequent pair
all shifts
yes
174
7
18
SimpleWall
3
48
start of a free run
shift 0
yes
2,970
120
3
3Bricks
4
48
end of a free run
all shifts
no
64
3
992
Flowers
3
112
end of a free run
shift 0
yes
2,116
36
22
MoreFlowers
3
112
end of a free run
shift 0
yes
2,116
36
21
Platformer
3
1,040
end of a free run
shift 0
yes
17,425
33
80
Appendix
Table 2: The gluing check on the eight examples with a row invariant, run after the copier’s results were known. For each example: the patch size P of the row types, and the band length L and the anchor of the row-type sampler, as in Table 3 ; the alphabet on which the check was decided, the example’s rows at shift zero where they glue there, which implies that they glue over all shifts, and otherwise the rows at every horizontal shift; whether the rows glue; and the size of the computation, namely the configurations reached over the band, the most at any one row, and the largest set of states of the realization automaton in one configuration, each the largest over the candidate strips Z . The last row is Wall with its shifts restricted to multiples of three, where every strip of three rows that the check explores is a strip of the tiled example. On 3Bricks the sizes are those of the run from the candidates, and the negative answer rests on the run from the set of all strips at once (see the text).
example
P
row types
pair states
anchor
free run (rows)
L
log2 of walks per band
spacing in the example
sampled spacing
Wall
3
4
5
most frequent pair
–
32
5.2
4, 5
5 (4–5)
SimpleWall
3
4
5
start of a free run
2–31
48
16.5
5, 6
5 (5–14)
3Bricks
4
2
3
end of a free run
7–31
48
10.8
8
12 (8–32)
Flowers
3
5
6
end of a free run
20–31
112
9.7
24
28 (24–35)
MoreFlowers
3
5
6
end of a free run
20–31
112
9.7
24
28 (24–35)
Platformer
3
3
4
end of a free run
30–31
1,040
29.2
32
33 (32–33)
Appendix
Table 3: The row-type sampler on the examples the procedure gives it: the patch size P at which the row types are read, the number of row types and of states, where the anchor sits, the limits of a free run in rows, the band length L , the base-2 logarithm of the number of walks a band can take, and the anchor’s spacing in the example and in sampled bands (median, with the smallest and largest, over 200 bands on each of five seeds). Wall has no free type.
example
type
direction
P
d
values
example’s marginal of φ
κ(0)
κ(0.05)
floor r=32
indep.-coin rule’s δ
constant valid
Wall
invariant
horizontal
3
1
4
(0.33, 3×0.22 )
0.67
0.65
9.8⋅10−3
0.10–0.19
n
SimpleWall
invariant
horizontal
3
1
4
(0.47, 3×0.18 )
0.53
0.48
7.8⋅10−3
0.06–0.11
y
Flowers
invariant
horizontal
3
1
5
(0.83, 4×0.04 )
0.17
0.12
2.5⋅10−3
0.19–0.25 †
y
MoreFlowers
invariant
horizontal
3
1
5
(0.83, 4×0.04 )
0.17
0.12
2.5⋅10−3
0.23–0.29 †
y
3Bricks
invariant
horizontal
4
1
2
(0.88, 0.12)
0.12
0.11
4.5⋅10−4
0.33–0.40
y
Skyline
invariant
horizontal
3
1
4
(0.89, 3×0.04 )
0.11
0.08
1.6⋅10−3
0.27–0.35 †
y
Appendix
Table 4: The certificate on the certified public examples and on Chess and Stripes, two controls whose only valid colorings are the two phases of a period-two pattern (Appendix S2.4). Rows with an invariant or a phase use the full labeling of Section 3 ; Town’s row uses its one-way quantity, whose constant is κf=1−∑s⇝tfsft over pairs of components with t reachable from s , and its κ(δ) is the linear program’s lower bound on 1−∑s⇝tpspt (Appendix B.5 ). Columns: the kind of quantity, its direction, the patch size P at which the search found it, the period d of the phase (1 for an invariant, a dash for the one-way quantity), the number of values the example visits and their marginal in the example, largest first, where k×m stands for k values of share m each, κ(δ) at δ=0 and δ=0.05 , the floor of Theorem 1 at radius 32 for a generator whose window statistics match the example’s, the independent-coin rule’s own distance δ from those statistics (raw, on one 10242 canvas; an interval, since the run stored only the L1 distance over allowed windows and the rate of forbidden windows, printed as one value where its ends agree to two digits), and whether a constant coloring is valid.
Figure 6: The thirteen certified examples in the order of Table 4 , each scaled to fill its panel, with its size in cells and the kind of quantity its certificate finds: an invariant along rows, the row type of Section 3 ; a phase of period d along rows or along columns; or, on Town, a one-way quantity along rows. Under each example, the central 64×64 cells of one world of the method, mended within radius 24 and drawn at one scale for every example, with the share of forbidden windows on the whole canvas. The method is invalid on two of them: on SmileCity its faces come in mixed widths, and on 3Bricks the canvas shown is the one of its three that keeps more than one window in a thousand forbidden.
example
quantity
P
δ
κ(δmax)
δ∗
maxsps
expected at the reach
forbidden windows
clean
Wall
invariant
3
0.35–0.38
0.60
–
0.35
26.2
0
11/11
SimpleWall
invariant
3
0.21–0.23
0.30
0.53
0.47
21.1
0
8/8
Flowers
invariant
3
0.20–0.22
0
0.17
0.85
6.1
0
8/8
MoreFlowers
invariant
3
0.18–0.20
0
0.17
0.85
6.1
0
8/8
3Bricks
invariant
4
0.34–0.44
0.034
0.77
0.92
0.8
1069
1/8
Skyline
invariant
3
0.26–0.35
0
0.25
0.89
4.3
0
8/8
Appendix
Table 5: The method’s worlds against the theorems on the certified examples, in the order of Table 4 , on the eight canvases of the development and robustness seeds (on Wall also the fresh seeds), mended within radius 24. Columns: the kind of quantity and its patch size P ; the total variation δ of the canvases’ 3×3 window statistics from the example’s, smallest to largest; the program of Appendix B.5 at the largest δ ; δ∗ , the least δ at which the program reaches zero, a dash where it stays positive at every δ , so that no generator on independent coins is free of forbidden windows on that example at all; the share maxsps of the most common value of the quantity in the method’s worlds; the floor of Theorem 1 at the reach of the whole pipeline, r=804 , for a generator on independent coins with that share, as forbidden windows per canvas in expectation; the largest number of forbidden windows on one mended canvas; and the canvases with none. On Town, whose quantity is one-way, the program is the one-way program’s lower bound, the share is the largest component’s and the floor is the one-way bound of Appendix B.2 .
class (mending at radius 8)
examples
certified
constant coloring valid
mendable within radius 8
21
0
20
partial
10
0
9
resistant
21
13
15
all public examples
52
13
44
Appendix
Table 6: Certified public examples and examples a constant coloring satisfies, by how far mending within radius 8 gets under independent coins (the classes of Table S3). Chess and Stripes are not counted.
group
example
direction
D16
D64
persists along
certified
3Bricks ∗
rows
1.13
1.05
rows
Fabric
columns
2.42
2.42
all four
Flowers
rows
0.10
0.09
rows
MoreFlowers
rows
0.12
0.11
rows
Platformer
rows
0.84
0.54
rows
RedMaze
rows
2.51
2.51
all four
Appendix
Table 7: Dependence between 3×3 windows at a distance in 32 worlds of Wave Function Collapse, in nats above the pairings across worlds, at 16 cells ( D16 ) and 64 ( D64 ). The direction is the certified one on a certified example and, on the others, the one in which D16 is largest. The last column lists the directions along which the dependence persists: at 64 cells it exceeds all 20 pairings and keeps at least half its value at 16. An asterisk marks a canvas of 96×96 , read at 12 and 48 cells, and a dagger the one-way quantity of Town. Of the 31 examples that do not resist, only Maze shows a persistent dependence, along the antidiagonal, and Cats is not measured.
Constraint-based game content generators that learn local constraints from existing content, such as Wave Function Collapse (WFC), can generate visually satisfying game levels but face challenges in optimizing global properties, such as playability. On the other hand, reinforcement-learning-trained generators can optimize global properties---because such properties can easily be included in reward functions---but the results can be visually dissatisfying. In this paper, we explore ways to combine these methods. Specifically, we constrain the action space of a PCGRL generator with constraints learned by WFC, effectively allowing the PCGRL generator to achieve global properties while being forced to adhere to local constraints. To better analyze how this hybrid content generation method operates, we vary the number and type of inputs, and we test whether to randomly collapse the starting state and exclude rare patterns. While the method is sensitive to hyperparameter tuning, the best of our trained generators produce visually satisfying and playable puzzle-platform game levels---such as Lode Runner levels---with desired global properties.
Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis +1
Institute of Digital Games, Msida, Malta · Game Innovation Lab, New York, New York, USA
Although conventional world models - auto-regressive or diffusion models based on transformers or convolutional networks - may learn surface statistics of world dynamics, can they learn the exact world dynamics from its observed history? Leveraging cellular automata as a simple testbed, we find the answer to be no in many cases. Conventional architectures predict most pixels correctly yet rarely complete a rollout: a CNN predicts 96.3% of cells but completes 18.9% of rollouts; a joint diffusion model completes none. We trace the gap to three failure modes of these world models - namely, they fail to exactly capture spatial locality, temporal locality or temporal stability. Simple changes repair each: (1) for spatial locality, two-dimensional rotary positions lift a transformer from 39.1% to 100% on the Game of Life; (2) for temporal locality, handing each token its cell's previous-frame neighbourhood lifts the same transformer from 25.8% to 99.9% on unseen rules; (3) for temporal stability, causal freezing lifts the same diffusion weights from 42.2% to 99.9%. None of the three changes touches the architectural backbone; each only modifies the information flow within it. We also compare joint and ordered sampling on billiards and, in an exploratory study, on a simulated Burgers equation.
Shaoyang Guo, Ziming Liu
Meta Circle(元环智能) · Peking University · Tsinghua University
Context. Random seed selection in deep learning is often arbitrary -- conventionally fixed to values such as 42, a number with no known feline endorsement. Aims. We propose that cats, as liminal beings with a historically ambiguous relationship to quantum mechanics, are better suited to this task than random integers. Methods. We construct a cat-driven seed generator inspired by the first Friedmann equation, and test it by mapping 21 domestic cats' physical properties -- mass, coat pattern, eye colour, and name entropy -- via a Monte ``Catlo'' sampling procedure. Results. Cat-driven seeds achieve a mean accuracy of 92.58%, outperforming the baseline seed of 42 by ∼2.5%. Cats from astrophysicist households perform marginally better, suggesting cosmic insight may be contagious. Conclusions. The Universe responds better to cats than to arbitrary integers. Whether cats are aware of this remains unknown.
Mi chen, Renhao Ye
Kapteyn Astronomical Institute, University of Groningen, Postbus 800, 9700 AV Groningen, The Netherlands · School of Astronomy and Space Science, University of Chinese Academy of Sciences, 1 East Yanqi Lake Rd., Beijing 100049, P.R. China · Shanghai Astronomical Observatory, Chinese Academy of Sciences, 80 Nandan Rd., Shanghai 200030, China