# Notes on Dungeon Generation via WaveFunctionCollapse

procedural-generation
notes
My notes from Brian Bucklew’s talk on procedurally generating dungeon levels using the WaveFunctionCollapse algorithm.
Author

Christian Mills

Published

December 28, 2021

## Overview

Here are some notes I took while watching Brian Bucklew’s talk covering how to use the WaveFunctionCollapse algorithm to procedurally generate dungeon levels.

## WaveFunctionCollapse

• Developed by Maxim Gumin and released as open source in 2016
• GitHub Repository
• Caves of Qud was the first commercial use, many others quickly followed.

## WaveFunctionCollapse Textures and Tiles

• WFC hast two primary modes of function, tile maps and textures
• The tilemap generation mode creates tile set solutions via propagation of defined tile adjacency constraints.
• Caves of Qud uses Texture Mode

### Texture Mode

• Easy training inputs (small (e.g. 16x16) training images that can be easily created in tools like mspaint)

• Powerful outputs (arbitrarily large output textures that are locally similar to the input)

### How it Works

1. The input texture is divided into $$NxN$$ (e.g. 3x3) subtextures (tiles) and their overlap with other tiles is calculated (e.g. overlap neighboring tiles by 1 on each side).
• Can rotate and reflect the input texture to increase the number of available tiles
2. The output is initialized with each pixel being a full superposition of possible output tiles.
• Imagine placing the stack of subtexture tiles on each pixel in the output image
• The (3x3) tiles overlap at the edges
3. The lowest entropy $$NxN$$ (e.g. 3x3) area is selected from the output and one option is selected at random from the remaining possibilities.
• Pick a random (or lowest entropy) pixel location in the output image
• Pick a random tile from the stack for that pixel location
• That final value for that pixel location in the output image is set to the value at the center of the (3x3) tile that was selected
• All other potential tiles in the stack for that pixel location are discarded (i.e. the stack collapses)
4. New information based on that selection are propagated (like a wave) to adjacent areas, removing possibilities that won’t properly overlap.
• Remove the tiles from the stacks for the neighboring pixel locations that are not compatible with the selected tile for the finalized pixel location
• Select the neighboring pixel location with the smallest remaining tile stack (i.e. lowest entropy)
• Pick a random option from the remaining compatible tiles
• Repeat for the neighboring tiles around that pixel location
5. If any elements are still uncollapsed go to step 2.
• Select the pixel location with the smallest remaining tile stack

### Quick Code Example

// Input: the training image
// N: How large of blocks NxN (e.g. 3x3) to sample from the input as input patterns.
// Note: Higher N leads to rising CPU and memory cost)
// Width: The output width
// Height: The output height
// periodicInput: Whether to sample the input across edges
// perdiodic: Whether the output should be sampled across edges to create edge-wrapping output
// symmetry: A value between 1..8, indicating how many reflection and rotation symmetries should be sampled from the input
var model = new OverlappingModel(input, N:3, width:48, height:48, periodicInput:true, periodic:false, symmetry:8, ground: 0);
model.Run(random.Next, limit:0);
model.Graphics().Save(\$"output.png");

Problem 0 - Scaling

• The execution time scales with the input resolution
• Memory usage scales with tile size

Problem 1 - Homogeneity

• The output just goes on forever in every direction
• There is no inherent large scale structure

Solution

• Perform a preprocess pass for map segmentation
• Partition large scale chunks (shapes) whose interior walls are generated by WFC.
• Fill in the chunks with different WFC pass using new input
• Can use algorithms like A* to find broken connectivity (e.g. find places to put doors)

Problem 2 - Overfitting

• Adding more detail often results in overfitting small details, reducing the variability of the output

Solution:

• Use WFC to create overall architecture
• Create additional detail and connectivity (doors, etc) with follow-up passes