# Notes on WaveFunctionCollapse for 3D

procedural-generation

notes

My notes from Martin Donald’s video on using the WaveFunctionCollapse algorithm for 3D modules.

## Overview

Here are some notes I took while watching Martin Donald’s video providing an overview of the WaveFunctionCollapse algorithm as well as implementation considerations when using it with 3D modules.

## Sudoku

- Solitaire game played on a 9x9 grid
- The 81 cells are grouped into 3x3 boxes

- Goal: Fill each space with a single number in range \([1,9]\)
- Constraints
- Every row, column and box must contain all numbers 1-9
- No number may ever appear twice in the same row, column or box

- Each cell in an empty board could potentially any number in the range \([1,9]\)
- Each cell is in a superposition (occupying all nine possible states at once)

- Typically, there are a few cells already with numbers
- Their superpositions are already collapsed to a single possibility
- This reduces the number of possible values for the other cells in the relevant row, column, and square
- Example: If a cell contains the number 5, no other cell in that row, column, or square can be a 5

- After reducing the possible values for each cell in the board based on the initial cell values, select a cell with the lowest number of remaining possible values (i.e. lowest entropy)
- Randomly select one of the remaining possible values for that cell
- This again reduces the number of possible values for the other cells in the relevant row, column, and square

- Eventually each cell will only contain one possible value

## WaveFunctionCollapse Algorithm

- A procedural solver that takes a procedural solver that takes a grid of cells, each occupying a super position containing all possible states for that cell
- Each tile (potential state) comes with its own set of adjacency rules
- Only certain tiles can be above it
- Only certain tiles can be below it
- Only certain tiles can be left of it
- Only certain tiles can be right of it

- The algorithm looks for the cell with the lowest number of possible tiles
- It will randomly pick a cell with the lowest number, if there is more than one

- The algorithm then randomly picks one the possible tiles for that cell
- The algorithm then updates the list of possible tiles for the surrounding cells based on the selected tile
- The algorithm repeats until each cell contains only one possible tile

### Adjacency Constraints

- Tells the algorithm which tiles or modules can slot together for each side (e.g. 4 for 2D square tiles and 6 for 3D cube modules)
- Can have the model determine the adjacency constraints by looking at a hand crafted output
- The model breaks the example down into tiles and keeps track of which tiles are placed next to each other and considers those combinations valid

- Can use a socket system
- Mark each side of a tile or module with an identifier (e.g. a number)
- Tiles and modules can only slot together if the connecting sides both have the same identifier value
- Could increase granularity by having three identifiers for each side, so that the outer edges and middle of each side are considered rather than the side as a whole

### 3D Modules

- Each cube module needs to have six lists of valid neighbors, one for each side of the cube.
- Whenever a cell is collapsed to one potential module, we remove modules from neighboring cells that are incompatible that are not present in the list of valid neighbors for the selected module
- To create the lists of valid neighbors, label the side of each module with socket identifiers
- Loop over each module in the set of available modules
- Store the positions of each vertex the sits along the edges of each of the six boundaries
- Store and label the boundaries
- This will build a dictionary of socket identifiers and side profiles
- Add a tag to indicate symmetrical sockets
- Check for symmetry by mirroring the vertex positions of each socket and check if it is still the same
- If a socket is not symmetrical, store the mirrored and unmirrored versions as two different sockets,
- Indicate mirrored socket with a specific tag

- For top and bottom boundaries, store four rotated versions of each socket, indicating the which rotation index with a tag
- Vertical sockets will be considered valid if they have the same socket name and rotation index

**Prototypes**

- The metadata for modules
- The associated 3D mesh object
- The rotation value
- The six lists of valid neighbors

- Allows us to get around needing to export four different meshes for each module
- Create four prototypes that reference the same mesh with different rotation index

- Store prototypes in a JSON file and load in game engine as a dictionary

**Building Prototypes**

- Create four prototype entries for each module, one for each rotation
- Will start with the mesh name, rotation index, and list of socket identifiers

`"proto_0" = { mesh: "myMesh.obj", rotation: 0, sockets: [ posX: "0", negX: "1s", posY: "1s" negY: "0f" posZ: "-1" negZ: "v0_0" ] }`

- Compare each prototype six times, one for each side of the module cube
- For each side check if the connecting socket identifiers are valid
- Check for special conditions for symmetrical, asymmetrical, and vertrical

- Add relevant prototypes to the neighbor list for the valid side for the current prototype

`"proto_0" = { mesh: "myMesh.obj", rotation: 0, sockets: [ posX: "0" negX: "1s" posY: "1s" negY: "0f" posZ: "-1" negZ: "v0_0" ], neighbor_list = [ posX: [..], negX: [..], posY: [..], negY: [..], posZ: [..], negZ: [..] ] }`

- For each side check if the connecting socket identifiers are valid
- Note: A module might not contain vertices along every face
Store the socket identifier as -1

Add a blank prototype with no mesh reference where all socket identifiers are set to -1 to represent empty space

`"p-1" = { "mesh_name: "-1", "mesh_rotation": 0, "posX": "-1f", "negX": "-1f", "posY": "-1f", "negY": "-1f", "posZ": "-1f", "negZ": "-1f", "constrain_to": "-1" "constrain_from": "-1", "weight": 1, "valid_neighbors": [...] }`

### WFC Demos on Itch:

Wave Function Collapse - Mixed Initiative Demo

Wave Function Collapse - Simple Tiled Model

**References:**