Notes on WaveFunctionCollapse for 3D

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

Christian Mills

Published

December 28, 2021

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: [..]
    ]
}
  • 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: