Infinite Worlds from One Example: What Local Generators Must Share

Amin Najafgholizadeh; Mohsen Afsharchi

cs.LGOct 31, 2026

Infinite Worlds from One Example: What Local Generators Must Share

Authors: Amin Najafgholizadeh, Mohsen Afsharchi

Organizations: Department of Computer Engineering, University of Zanjan.

Abstract

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\times 64$ cells of a $256\times 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

\varepsilon

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

q_{r}

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

\delta

of its

3\times 3

window statistics from the example’s and its share

\varepsilon

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

\delta=\kappa_{f}

on SimpleWall, and all of it on Wall, where the program of Section 3 stays positive at every

\delta

. 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$	$\log_{2}$ 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 $\varphi$	$\kappa(0)$	$\kappa(0.05)$	floor $r{=}32$	indep.-coin rule’s $\delta$	constant valid
Wall	invariant	horizontal	3	1	4	(0.33, $3{\times}0.22$ )	0.67	0.65	$9.8\cdot 10^{-3}$	0.10–0.19	n
SimpleWall	invariant	horizontal	3	1	4	(0.47, $3{\times}0.18$ )	0.53	0.48	$7.8\cdot 10^{-3}$	0.06–0.11	y
Flowers	invariant	horizontal	3	1	5	(0.83, $4{\times}0.04$ )	0.17	0.12	$2.5\cdot 10^{-3}$	0.19–0.25 †	y
MoreFlowers	invariant	horizontal	3	1	5	(0.83, $4{\times}0.04$ )	0.17	0.12	$2.5\cdot 10^{-3}$	0.23–0.29 †	y
3Bricks	invariant	horizontal	4	1	2	(0.88, 0.12)	0.12	0.11	$4.5\cdot 10^{-4}$	0.33–0.40	y
Skyline	invariant	horizontal	3	1	4	(0.89, $3{\times}0.04$ )	0.11	0.08	$1.6\cdot 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

\kappa_{f}=1-\sum_{s\leadsto t}f_{s}f_{t}

over pairs of components with

t

reachable from

s

, and its

\kappa(\delta)

is the linear program’s lower bound on

1-\sum_{s\leadsto t}p_{s}p_{t}

(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{\times}m

stands for

k

values of share

m

each,

\kappa(\delta)

\delta=0

and

\delta=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

\delta

from those statistics (raw, on one

1024^{2}

canvas; an interval, since the run stored only the

L_{1}

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\times 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$	$\delta$	$\kappa(\delta_{\max})$	$\delta^{*}$	$\max_{s}p_{s}$	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

\delta

of the canvases’

3\times 3

window statistics from the example’s, smallest to largest; the program of Appendix B.5 at the largest

\delta

;

\delta^{*}

, the least

\delta

at which the program reaches zero, a dash where it stays positive at every

\delta

, so that no generator on independent coins is free of forbidden windows on that example at all; the share

\max_{s}p_{s}

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	$D_{16}$	$D_{64}$	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\times 3

windows at a distance in 32 worlds of Wave Function Collapse, in nats above the pairings across worlds, at 16 cells (

D_{16}

) and 64 (

D_{64}

). The direction is the certified one on a certified example and, on the others, the one in which

D_{16}

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\times 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.

Implicit Generative Modeling

See all 8 papers

Learning Local Constraints for Reinforcement-Learned Content Generators
May 13, 2026Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis +1Constrained Generative Modeling Constrained RL
Institute of Digital Games, Msida, Malta · Game Innovation Lab, New York, New York, USA
Why Do Conventional World Models Fail to Learn Cellular Automata?
Sep 30, 2026Shaoyang Guo, Ziming LiuWorld Model Learning Spatiotemporal Reasoning
Meta Circle(元环智能) · Peking University · Tsinghua University
Schrödinger's Seed: Purr-fect Initialization for an Impurr-fect Universe
Mar 31, 2026Mi chen, Renhao YeNeural Network Initialization ML Reproducibility
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

May 13, 2026J/K move · Enter open · S save

Learning Local Constraints for Reinforcement-Learned Content Generators

Debosmita Bhaumik, Julian Togelius, Georgios N. Yannakakis, Ahmed Khalifa

Institute of Digital Games, Msida, Malta · Game Innovation Lab, New York, New York, USA

Constrained Generative Modeling Constrained RL Generative Modeling Procedural Content Generation RL for Generative Models

Open paper AskPDF arXiv

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.

Abstract

Implicit Generative Modeling

Explore similar work

Learning Local Constraints for Reinforcement-Learned Content Generators

Why Do Conventional World Models Fail to Learn Cellular Automata?

Schrödinger's Seed: Purr-fect Initialization for an Impurr-fect Universe