1 Introduction↩︎

The wide range of Procedural Content Generation (PCG) methods in existence contains not only different algorithmic foundations, but also different use cases. For example, the Wave Function Collapse (WFC) algorithm  [1], which can be seen as constraint solving or self-supervised learning, is widely used in indie games. It is self-contained, requires little input, and rapidly generates small levels, although it cannot guarantee solvability and does not scale well to larger levels.

By contrast, search-based PCG sees content generation as an optimization to be solved with evolution, meaning that complex objectives and constraints can be satisfied. While search-based PCG is the subject of hundreds of papers, it is not widely used in actual games, probably because of the long generation time and/or complexity of specifying objectives.

In AI, as in other fields of engineering, the best methods are often hybrid methods that combine the advantages of multiple algorithms. What if we could combine some of the advantages of WFC and search-based PCG? For example, allowing authoring by specifying objectives. In this paper, we investigate whether the compact representation of WFC can be combined with the controllability of evolutionary search. Specifically, we evolve the inputs provided to WFC rather than directly evolving complete levels. This can be seen as using WFC as a genotype-to-phenotype mapping for the evolutionary algorithm.

We evaluate this approach in two game domains with different relationships between local and global structure. In the Maze domain, where desired properties such as connectivity come out of local spatial relationships, evolutionary optimization successfully utilizes WFC toward higher-quality outputs. In the Zelda domain, where the game depends on global constraints such as exactly one player, key, and door, the limitations of local patterns become more apparent. Our results suggest that evolutionary optimization over WFC genotypes is most effective when target objectives are compatible with local structural regularities.

2 Background↩︎

Procedural content generation [2] is getting a lot of attention from the game industry in the past couple of years¹. The problem is that most of the techniques that are used in the industry are based on human knowledge and heuristics, which makes the algorithm not generalizable between games, as each game requires a different algorithm. Wave Function Collapse (WFC) is one of the early methods that can be treated as a black box and used in your game with high controllability of the generated output through using a small example picture.

2.1 Wave Function Collapse↩︎

Wave Function Collapse (WFC) was introduced by Maxim Gumin in 2016². WFC has gained plenty of attention since, from both game developers and academia. WFC is a constraint-solving method [1] that tries to generate bigger patterns based on the input constraints. These constraints can be provided directly through a tile mode or can be learned from a smaller image input in the pixel mode. The pixel mode can be considered as self-supervised learning [3] as the algorithm learns the constraints from the input image.

WFC uses a sliding window to learn local pattern relations without any understanding of global patterns. For example, WFC can’t learn that a certain tile needs to be only available a fixed number of times or that there is a path between two tiles on the map. This simplicity of the input/output of WFC made it at the forefront of PCG methods used in commercial games [4] and ROM hacking communities [5].

Several extensions to WFC have explored methods for improving controllability, scalability, and output quality. Prior work has incorporated global constraints [6], [7], constructive layout generation [8], neural representations [9], hierarchical generation [10], graph-based variants of WFC [11], and modified tile selection heuristics to better preserve input tile distributions [12]. Other work has combined WFC with reinforcement learning or evolutionary approaches to improve generated outputs [13], [14]. These works highlight a broader interest in combining WFC with optimization and controllability methods.

2.2 Search-Based Procedural Content Generation↩︎

Search-based procedural content generation (SBPCG) [15] formulates the generation process as an optimization problem. Evolutionary algorithms and related search methods optimize generated artifacts according to game related metrics such as playability, connectivity, progression structure, or difficulty. Search-based approaches have been applied to levels, rulesets, and music generation [16]–[18].

Compared to constructive approaches such as WFC, search-based methods provide significantly more control over generated content because designers can explicitly optimize toward desired objectives. However, these approaches are often computationally expensive and may require carefully designed fitness functions. Prior work has also explored searching for generators rather than directly searching for levels [19], [20]. Our work follows this direction by evolving compact WFC input examples that act as generators for larger procedurally generated outputs.

3 Methods↩︎

Our method combines Wave Function Collapse (WFC) with evolutionary search by treating WFC inputs as evolvable generators. We directly evolve the small input image (each pixel represent a game tile) that are used by WFC to generate larger outputs. In this method, each input acts as a genotype, while the generated WFC level acts as the phenotype evaluated by the fitness function. WFC in this case serves as a stochastic genotype-to-phenotype mapping within an evolutionary algorithm.

3.1 Representation↩︎

Each individual in the population is represented as a small tile grid. In all the experiments, we use a \(4 \times 4\) genotype representation initialized with random tiles from the target game. The genotype is rendered as an image and passed to WFC, which extracts adjacency patterns and generates a larger output level. This representation allows evolutionary search to optimize on compact examples instead of directly optimizing complete levels that may be larger and more computationally expensive.

3.2 Wave Function Collapse Generation↩︎

For each genotype, WFC generates an output level by extracting all the 2x2 patterns in the input image and use them as constraints for the generation. Generation is stochastic, meaning that the same genotype can produce different outputs depending on the random seed. In our experiments, each genotype is evaluated using a single WFC generation. We evaluate two game domains:

• Maze: generates \(8 \times 8\) maze-like maps focused on connectivity and navigable path structure.

• Zelda: generates \(16 \times 16\) dungeon-like layouts containing players, keys, doors, and enemies.

3.3 Fitness Evaluation↩︎

Generated levels are evaluated using domain-specific fitness functions from the PCG Benchmark [21]. For the Maze domain, fitness rewards levels that contain a single connected traversable region and long navigable paths. For the Zelda domain, fitness is a weighted sum of an entity-count term and a playability term: \(\text{fitness} = 0.7 \cdot R_{\text{entity}} + 0.3 \cdot R_{\text{play}}\). The \(R_{\text{entity}}\) term rewards count close to the target (one player, one key, one door, up to 25 enemies). \(R_{\text{play}}\) is zero unless exactly one player, key, and door are present. Otherwise, it averages reachability between player, key, and door, plus a bonus when the combined path length is near half the level area.

3.4 Evolutionary Search↩︎

We use an evolutionary algorithm with tournament selection, mutation, and elitism. Each run uses a population size of 10 over 100 generations. At each generation:

1. Each genotype is evaluated by generating a WFC output and computing its fitness.

2. Tournament selection (size 3) selects \(N/2 = 5\) parents.

3. Each selected parent contributes two individuals to the next generation: an unmutated copy and a mutated offspring, maintaining a constant population size of \(N = 10\).

4. For each mutated offspring, between 1 and 5 tile positions are independently mutated, depending on the population’s fitness standard deviation. Each candidate mutation is applied with probability \(p\), and replaces the selected tile with a value drawn uniformly at random from the tileset. The mutation probability \(p\) starts at 0.5 and adapts each generation based on whether the fitness has improved to balance exploration and exploitation.

5. The best individual of the generation is preserved into the next generation (elitism).

3.5 Random Search Baseline↩︎

We compare the evolutionary algorithm against a random search baseline. In random search, each generation consists of a newly sampled random population and keep the best chromosomes. Both methods use the same evaluation of 100 generations with a population size of 10, resulting in 1000 WFC genotype evaluations per run.

4 Results↩︎

Figure 1 shows the outputs generated using evolutionary and random search in both the Maze and Zelda domains. The two domains showcase different relationships between local and global structure. This allows us to evaluate how effectively evolutionary search can guide WFC generation.

4.1 Maze Domain↩︎

In the Maze domain, evolutionary search consistently produced more coherent and connected layouts than random search. Evolved outputs typically contained longer continuous paths and fewer disconnected regions, while random search frequently generated fragmented layouts with large and isolated components.

Figure 2 shows the fitness progression in the Maze domain. Evolutionary search rapidly converges toward high-performing generators within the first 40 generations before stabilizing near a local optimum. In contrast, random search exhibits large variance throughout the generations and fails to showcase consistent improvement over time.

Although random search occasionally discovers strong outputs through random luck or chance, these generators are not typically preserved between generations. In contrast, evolutionary search retains and mutates successful WFC inputs, allowing local spatial patterns to compound over time. The Maze domain appears particularly compatible with the local pattern representation used by WFC. Desired gameplay properties such as connectivity emerge naturally from repeated local adjacency relationships. These results suggest that evolving WFC inputs behave similarly to searching for local construction rules. The evolutionary algorithm discovers compact examples that allow WFC to tend toward generating desired larger structures.

4.2 Zelda Domain↩︎

The Zelda domain proved significantly more difficult. Although evolutionary search generated more structured outputs than random search, many generated levels still failed to satisfy all gameplay requirements at the same time. The evolved outputs frequently showed recognizable room-like regions, traversable corridors, and more meaningful placement of enemies and gameplay entities, and wall and maze-like structures. However, making sure of the existence of exactly one player, one key, and one door remained challenging.

Figure 3 shows the fitness progression in the Zelda domain. Evolutionary search improves rapidly during the early generations before stabilizing near generation 30. In contrast, random search slowly improves or even stagnates throughout the run because the best successful generators are not utilized overall towards improvement.

Quantitatively, evolutionary search also achieved higher fitness values than random search in the Zelda domain. However, the performance gap is smaller than in the Maze domain. This highlights the difficulty of optimizing on gameplay properties that depend on global structure. This limitation follows from the local nature of WFC. The algorithm learns adjacency relationships between nearby patterns but does not explicitly model global gameplay dependencies. Consequently, evolutionary search is constrained by the representational limits of the underlying WFC model.

Despite these limitations, evolutionary search still improved the overall organization of generated Zelda layouts relative to random search. The evolved examples appeared to shift WFC toward producing more playable spatial arrangements, even when complete gameplay validity was not achieved.

4.3 Discussion↩︎

The contrast between the Maze and Zelda domains highlights an important property of Evolutionary Wave Function Collapse. The approach performs best when the objectives follow local spatial regularities. In such domains, evolution can successfully search for compact WFC inputs that expand into coherent outputs reliably. Domains requiring stronger global constraints remain more challenging. Even in situations where evolution discovers useful local patterns, WFC itself cannot directly enforce global requirements such as uniqueness constraints or progression ordering.

Another important limitation is the stochastic nature of WFC generation. Because each genotype can generate different outputs depending on the random seed, fitness evaluation introduces noise into the evolutionary process. In this work, each genotype was evaluated using a single WFC generation. Evaluating each genotype multiple times may improve stability and reduce variance in future work.

5 Conclusion & Future Work↩︎

This paper explored combining Wave Function Collapse with evolutionary search by evolving compact WFC input examples rather than directly evolving complete levels. Our results show that evolutionary optimization can effectively guide WFC generation in domains where gameplay properties emerge from local structure. In the Maze domain, evolution successfully discovered compact WFC inputs that consistently generated connected and navigable layouts. In the Zelda domain, evolutionary search improved the organization of gameplay entities and traversable structure, but satisfying global gameplay constraints remained significantly more challenging due to the local nature of WFC pattern learning.

These results suggest that Evolutionary Wave Function Collapse is particularly effective in domains where global properties can emerge indirectly from repeated local relationships. However, domains that depend on explicit and specific symbolic constraints expose important limitations of purely local pattern models.

Future work should explore integrating explicit global constraint solving [6], [7] into the evolutionary WFC pipeline. Instead of relying entirely on local adjacency relationships, future systems could incorporate constraint-matching methods that directly enforce gameplay requirements such as uniqueness constraints, progression ordering, reachability, or key-door dependencies during or after generation.

References↩︎