Wave Function Collapse – Robert Christensen

Wave Function Collapse is a procedural content generation algorithm that uses an extension of constraint solving. For example, a cell’s possible values might be constrained by the cells adjacent to it, or there might be a global limit like only allowing one boss room and 2-4 treasure rooms per floor. This is not to be confused with dynamically adding adjacencies after initial layout generation.

There are three possible solving strategies depending on the size of a cell’s possibility space:

If its possibility space is reduced to a size of 1 it can be trivially solved, since there is only one possible solution. When searching for solvable tiles, this strategy will always be preferred if it is available.
A cell with multiple allowed values can choose one at random, but this is usually a weighted random.
A cell with no allowed values can choose a value that violates the least important or least number of constraints.

If possibility space is synthesized from constraints and local context, it is possible to initialize only the observed regions of an infinite space, as Marian42 demonstrates. It is also possible to treat all non-trivial operations as a node on a digraph. By recording a stack of undo snapshots and backtracking when the second strategy would later require the third strategy, the algorithm will always solve perfectly without violating any constraints, if such a thing is possible. However, this is less realistic due to memory limitations, and much higher time complexity.

Implementation

My implementation uses Spigot, a type of Minecraft server that allows custom plugins. Since this is not a proper engine, I have had to find some lateral solutions. For lack of debug draw calls, I have reused a module I wrote for particle graphics. I also had to find an unusual workaround to show possibilities for each unsolved tile: writing the cell directly would only show one possibility, so I chose Armor Stands since they could also display probability in their nameplates as well as rendering items smaller than one world grid cell. Wave function collapse also relies on a state for unsolved tiles, which Minecraft’s builtin world grid does not support, so I had to write a custom RegionSnapshot data structure.

Currently my implementation is capable of basic pattern recognition and replication. It is consistently able to replicate checkerboards, axial and diagonal strips of varying sizes, and to some extent trees. I initially expected trees to be trivial because leaves track manhattan distance to the nearest log and and this would be considered a separate tile type by the constraint system, but currently leaves only generate in positions where a cube of radius 1 contains a log, and corner leaves generate inconsistently. However, I think this is a problem with the analyzer, since by default distance=2 leaves cannot be generated without leaves on both sides of its distance=1 parent. If so, there is a similar deadlock that prevents logs from being placed on top of more logs.

I suspect its current limits come from the way the solver iterates over each unsolved index, and the isolated nature of the constraints. The original implementation tracks a frontier and updates the most-easily solved cell, but my implementation walks each cell in XZY order first attempting to trivially solve and then using probability as a fallback. This leads to some tiles being evaluated before they should have been, and this causes misses in other areas with constraint solving. The AdjacencyConstraint data structure allows certain offsets to be ignored, but by only recognizing two-way links it either cannot interact with or excessively limits texture complexity, rather than having a full matrix for each potential output.

I also discovered (the hard way) that this algorithm has high time complexity, especially in 3D. To propagate a single set of adjacency constraints in a cube of radius 2 tiles, 5*5*5-1 = 124 tiles are addressed. Most use cases have 2-5 different tile types, and the average grid size I tested with was 12*12*12. This results in up to 429 thousand to 1.1 million sets, each comprised of multiple read, lookup, and multiply operations. Comparatively, the 2D examples I saw most often used 50*50 spaces, so their time complexity would be 50*50*(5*5-1)*{2-5} = 120 to 300 thousand sets.

Possible further development

Typically the wave function collapse algorithm operates on a tilemap or other texture-like space. However, the algorithm could theoretically be abstracted, and this would be capable of generating plot or puzzles, like for detective games.

There is a principle in TTRPGs that the player is always right. If the players wander to the wrong town, move the current narrative to that town. If they accidentally kill an innocent NPC, fabricate a couple skeletons in the closet. Wave function collapse could generate a dungeon based on this concept, putting a certain guaranteed number of encounters between the player and the boss room, no matter where they go.

Guaranteeing the correct path forsakes any need for directing the player through level design, but at the same time may confuse players, especially if they wish to explore side content. Alternatively, instead of making every path the right path, sending the player to a dead end is equally easy, and it may be possible to encourage or discourage exploring side content through strategically creating or not creating these branches. With constraints based on the player’s current attack and defense power, it may also be possible to guarantee a fixed amount of challenge that still can reliably be overcome, by changing the difficulty or number of encounters.

Implementation

Possible further development

Further reading