Wave Function Collapse
Procedural Buildings

Anaren sample

Languages, Tools & Keywords


Wave Function Collapse Logic

The Wave Function Collapse algorithm I implemented for procedurally placing tiles—whether in 2D or 3D—is analogous to how humans solve Sudoku or assemble a jigsaw puzzle. In Sudoku, each cell is constrained by rules: numbers 1 through 9 must not repeat in the same row, column, or 3x3 block. Pre-placed numbers limit the options for empty cells, and once a number is placed, it eliminates that possibility for its neighbors. This cascading reduction in possibilities allows for the selection of cells with the least entropy and their subsequent resolution by randomly choosing among the remaining valid options. My algorithm follows a similar principle: starting with a full set of potential tiles for each grid cell, I reduce the possibilities based on adjacency constraints until a consistent structure is achieved. In 3D, I extend the logic to consider connections in all six directions.

Models Used

For my 3D procedural level generator, I utilize a predefined tileset to populate a three-dimensional grid with tiles that connect seamlessly. Although the full tileset includes over 70 prefabs from Kenny, I selected a subset of 19 tiles for the demo to reduce complexity while still demonstrating robust level generation.

Solving Rotation Issue

To address tile rotation challenges, I implemented a programmatic solution that rotates each object in 90-degree increments. Each rotated instance is renamed to reflect its orientation, and its connection rules are updated accordingly. This process effectively creates four variations of each tile, each with valid connections adjusted for the new orientation.

Wave Function Collapse Implementation

The core of my implementation uses the Wave Function Collapse algorithm to construct a 3D grid structure from a set of predefined tiles and their connection rules. The process begins by loading tile data from a JSON file, which outlines each tile's possible connections and rotations. I initialize a dictionary that tracks the entropy—or number of valid tile placements—for each grid cell, starting with a full superposition of possibilities. The algorithm then places a hardcoded tile at the center of the grid and progressively collapses the neighboring cells based on the adjacency constraints defined in the JSON. By iteratively selecting the cell with the lowest entropy and placing a tile from its valid options, I propagate constraints throughout the grid until the desired number of tiles is placed or no valid moves remain.

The Algorithm Visualized

For enhanced clarity and debugging, I developed an alternate version of the Wave Function Collapse script, WaveFunctionCollapseVisualized.cs. This version overlays colored cubes on each grid cell to illustrate the algorithm’s process: red cubes indicate cells being collapsed, blue cubes represent the propagation of constraints to neighboring cells, and yellow cubes denote the tracking of cell entropy.