Notes on WaveFunctionCollapse for 3D
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 19
 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
"p1" = { "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: