🤖 AI

Evolutionary Wave Function Collapse

This paper proposes an evolutionary search framework that optimizes the small input examples used by Wave Function Collapse (WFC) to generate higher-quality procedural content, demonstrating that this approach effectively improves generation in domains where global properties emerge from local constraints, such as maze connectivity and dungeon layouts.

Original authors: Dipika Rajesh, Ahmed Khalifa, Julian Togelius

Published 2026-07-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dipika Rajesh, Ahmed Khalifa, Julian Togelius

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to draw a map for a video game. You have two different ways to do this, and this paper is about trying to mix them together to get the best of both worlds.

The Two Approaches

1. The "Copycat" Robot (Wave Function Collapse)
Think of the first method, called Wave Function Collapse (WFC), as a very talented but slightly myopic copycat.

How it works: You show the robot a tiny, 4x4 square of a picture (like a tiny patch of a dungeon or a maze). The robot looks at how the tiles in that tiny patch touch each other (e.g., "a wall usually sits next to a floor").
The Result: It uses those tiny local rules to build a huge, complex map.
The Problem: The robot is "short-sighted." It knows that a wall touches a floor, but it doesn't understand the big picture. It doesn't know that the map needs to be one big connected loop, or that there must be exactly one key and one door. It just follows the local rules, which sometimes leads to messy or broken maps.

2. The "Trial-and-Error" Artist (Evolutionary Search)
The second method is like a sculptor who creates thousands of statues, throws away the ugly ones, and keeps the good ones to make slightly better versions.

How it works: You generate many random maps, check which ones are fun to play, and then "breed" the best ones to create new generations.
The Problem: This takes a long time. You have to build the whole huge map, test it, and then start over. It's computationally expensive and slow.

The Big Idea: The "Genotype" and the "Phenotype"

The authors of this paper asked: What if we let the "Trial-and-Error" artist design the tiny 4x4 patch, and let the "Copycat" robot build the big map?

They treated the tiny 4x4 patch as the Genotype (the DNA or the blueprint) and the huge map the robot builds as the Phenotype (the actual living creature or the final product).

Instead of evolving the whole huge map (which is slow), they evolved the tiny 4x4 patch. The "Copycat" robot (WFC) acted as the machine that turned that tiny DNA into a full-sized level.

The Experiment: Two Different Games

They tested this idea in two different video game worlds to see if it worked:

1. The Maze World (The "Local" Success)

The Goal: Create a maze where you can walk from start to finish without getting stuck.
The Result: It worked great!
The Analogy: Imagine you are teaching a robot to build a brick wall. If you tell the robot "every brick must sit on two bricks below it," the wall will naturally be strong and connected. The "Maze" goal (connectivity) is a local rule. If the tiny patch has good local connections, the big map will naturally be a connected maze. The evolutionary search quickly found the perfect tiny patch that made the robot build great mazes.

2. The Zelda World (The "Global" Struggle)

The Goal: Create a dungeon with exactly one player, one key, one door, and some enemies, where the player can actually reach the key and door.
The Result: It was much harder.
The Analogy: Imagine you are telling the robot to build a house, but you only give it rules about how bricks touch each other. The robot might build a beautiful house, but it might accidentally build two front doors or forget to put a roof on. The "Zelda" goal requires global rules (e.g., "There must be exactly one key in the whole building"). The tiny 4x4 patch doesn't "know" about the whole building. Even though the evolutionary search made the maps look more organized, the robot still struggled to get the exact count of keys and doors right because it was only looking at the local neighborhood, not the whole house.

What They Found

When it works: If the thing you want (like a connected path) comes naturally from how small pieces fit together, this hybrid method is fantastic. It finds the perfect "blueprint" quickly.
When it struggles: If the thing you want requires counting things across the whole map or ensuring specific items exist in specific places (global constraints), the method hits a wall. The "Copycat" robot just doesn't have the brainpower to understand the big picture, no matter how good the tiny blueprint is.

The Conclusion

The paper concludes that you can use evolution to teach a "short-sighted" robot to build better maps, but only if the rules of the game are local. If the game needs strict, big-picture rules (like "exactly one key"), this method alone isn't enough. The robot needs a way to look at the whole map, not just the tiny patch it's currently copying.

Technical Summary: Evolutionary Wave Function Collapse

Problem Statement

Procedural Content Generation (PCG) in video games often faces a trade-off between controllability and scalability. Wave Function Collapse (WFC) is a popular method for generating content based on local adjacency constraints learned from small input examples. While WFC is self-contained and rapid, it lacks global understanding; it cannot guarantee solvability or enforce global constraints (e.g., specific entity counts or reachability between distant points). Conversely, Search-Based PCG (SBPCG) allows for explicit optimization toward complex objectives but is often computationally expensive and difficult to specify for designers. The paper investigates whether these approaches can be hybridized: specifically, whether evolutionary search can be used to optimize the inputs (the small example images) provided to WFC, rather than evolving the final levels directly. This treats WFC as a stochastic genotype-to-phenotype mapping.

Methodology

The proposed method, Evolutionary Wave Function Collapse, evolves compact input images (genotypes) that serve as the seed for WFC to generate larger game levels (phenotypes).

Representation: Individuals in the population are represented as small $4 \times 4$ tile grids. These grids are initialized with random tiles from the target game's tileset.
Genotype-to-Phenotype Mapping: The $4 \times 4$ input is passed to the WFC algorithm. WFC extracts all $2 \times 2$ adjacency patterns from this input and uses them as constraints to generate a larger output level. The generation is stochastic; the same genotype can produce different outputs based on the random seed.
Domains Evaluated:
1. Maze Domain: Generates $8 \times 8$ maps. The fitness function rewards a single connected traversable region and long navigable paths.
2. Zelda Domain: Generates $16 \times 16$ dungeon layouts. The fitness function is a weighted sum ( $0.7 \cdot R_{entity} + 0.3 \cdot R_{play}$ ) rewarding specific entity counts (one player, one key, one door, up to 25 enemies) and playability (reachability between player, key, and door).
Evolutionary Search: The system uses an evolutionary algorithm with tournament selection (size 3), mutation, and elitism.
- Population: Size of 10 over 100 generations.
- Mutation: Between 1 and 5 tile positions are mutated per offspring. The mutation probability ( $p$ ) starts at 0.5 and adapts based on fitness improvement to balance exploration and exploitation.
- Baseline: The method is compared against a Random Search baseline where populations are re-sampled randomly each generation, keeping the best chromosomes.

Key Results

The study evaluates the effectiveness of this hybrid approach in domains with varying dependencies between local and global structure.

Maze Domain (Local Structure Dominant):
- Evolutionary search significantly outperformed random search, rapidly converging to high-performing inputs within the first 40 generations.
- Evolved outputs exhibited coherent, connected layouts with long continuous paths.
- The results suggest that desired properties like connectivity emerge naturally from repeated local adjacency relationships, making this domain highly compatible with the WFC representation.
Zelda Domain (Global Structure Required):
- Evolutionary search produced more structured outputs than random search (e.g., recognizable rooms, meaningful entity placement) and achieved higher fitness values.
- However, the performance gap was smaller than in the Maze domain.
- The system struggled to satisfy strict global constraints simultaneously (specifically ensuring exactly one player, one key, and one door).
- Fitness curves showed early rapid improvement followed by stagnation near a local optimum, indicating that WFC's reliance on local patterns limits its ability to model global gameplay dependencies.

Significance and Claims

The paper claims that Evolutionary Wave Function Collapse is an effective strategy for guiding procedural generation when target objectives align with local structural regularities.

Hybrid Advantage: The approach successfully combines the compact representation and speed of WFC with the optimization capabilities of evolutionary search.
Domain Dependency: The method is most effective in domains where global properties (like connectivity) emerge indirectly from local relationships. It is less effective in domains requiring explicit, symbolic global constraints (like specific entity counts or progression ordering) because WFC does not inherently model these global dependencies.
Limitations: The authors acknowledge that the stochastic nature of WFC introduces noise into the fitness evaluation (as each genotype was evaluated only once). Furthermore, the local nature of WFC remains a fundamental constraint; evolutionary search cannot overcome the inability of the underlying model to enforce global rules directly.

The paper concludes that while this method improves generation quality and organization, future work should explore integrating explicit global constraint solving mechanisms into the evolutionary WFC pipeline to address domains requiring strict symbolic constraints.