Game dev
Saved & recent

Wave function collapse

Also called: WFC

Related terms: constraint solving, tile rules

An algorithm that fills a grid with tiles so that every tile fits its neighbors. The rules come from a list of which edges may touch, or are learned from a small example.

Every cell starts able to be any tile. Pick the cell with the fewest options left and choose one at random. Then remove every option in the neighboring cells that no longer fits, and repeat. Small tile sets grow into coherent towns, pipes and dungeons. Sometimes it paints itself into a corner and has to back up.

Further reading
Maxim Gumin: Wave Function Collapse
2 4 4 2 4 7 7 4 4 7 7 4 2 4 4 2 possible tiles 2 4 2 2 7 7 4 4 7 7 4 2 4 4 2 neighbor constraints chosen bend
The numbers count possible tiles. Choosing a corner bend in a cell with two options requires compatible pipe edges in its neighbors.

View in the full Game dev collection