DOCSEARCHbyAlgolia
Submit Docs

WaveFunctionCollapse

repository·master·Indexed 12 days ago

https://github.com/mxgmn/wavefunctioncollapse

A .NET Core implementation of the Wave Function Collapse (WFC) algorithm for generating structures like bitmaps or tilemaps. The algorithm simulates the collapse of a wave function from a state of superposition to a definite state to maintain local similarity to an input source. It supports a simple tiled model with adjacency constraint propagation, symmetry systems for efficient tileset handling, and integration for constrained synthesis.

Tokens
1.3K
Snippets
1
Records
6
Agent score
48%

What's inside WaveFunctionCollapse

  1. What is Wave Function Collapse (WFC)?

    master

    Wave Function Collapse (WFC) is an algorithm used to generate bitmaps (or other structures) that maintain local similarity to an input source. It ensures that the output contains only $N \times N$ patterns present in the input (Condition C1) and that the distribution of these patterns in the output is similar to their density in the input (Condition C2).

    Key concepts:

    • Superposition: The output starts in an 'unobserved' state where every pixel/region exists in a superposition of all possible valid states from the input.
    • Observation: The algorithm selects a region with the lowest Shannon entropy and collapses it into a single definite state based on the input pattern distribution.
    • Propagation: Information from a collapse is propagated to neighboring regions, reducing their possible states.
    • Contradiction: If a region's possible states are reduced to zero, the algorithm has reached a contradiction and cannot continue. This is an NP-hard problem, though contradictions are rare in practice.

  2. Conceptual overview of WFC heuristics and dimensions

    master

    Minimal Entropy Heuristic

    The algorithm utilizes a minimal entropy heuristic during the collapse process. This heuristic mimics human drawing patterns by selecting the cell with the lowest entropy (the fewest possible valid states) to collapse next, making the generation process visually intuitive.

    Dimensionality and Time

    While typically used for 2D tilemaps, WFC can be applied to higher dimensions. One dimension can represent time, meaning a $d$-dimensional WFC implementation can capture the behavior of any $(d-1)$-dimensional cellular automata.

  3. How the Wave Function Collapse algorithm works

    master

    The WFC algorithm follows these steps to generate an output from an input bitmap:

    1. Pattern Counting: Read the input bitmap and count all $N \times N$ patterns. (Optionally, augment this data with rotations and reflections).
    2. Initialization: Create a 'wave' (an array matching the output dimensions). Each element represents the state of an $N \times N$ region as a superposition of input patterns with boolean coefficients. Initialize all coefficients to true (the completely unobserved state).
    3. Observation-Propagation Cycle:
      • Observation: Find a wave element with the minimal non-zero entropy. If no such element exists, stop the cycle.
      • Collapse: Collapse that element into a definite state based on its current coefficients and the input pattern distribution.
      • Propagation: Propagate the information gained from the collapse to update the coefficients of neighboring elements.
    4. Termination:
      • If all elements are in a completely observed state (only one non-zero coefficient), return the output.
      • If any element enters a contradictory state (all coefficients are zero), the algorithm fails without returning a result.

  4. Tilemap generation and the Simple Tiled Model

    master

    A simplified version of WFC is the simple tiled model, where $N \times M = 1 \times 2$. Instead of using full $N \times N$ pattern probabilities, it uses the probabilities of individual tiles and their adjacency constraints.

    Key Features:

    • Adjacency Constraint Propagation: The propagation phase in this model is essentially propagating adjacency rules.
    • Symmetry System: To handle large tilesets efficiently, tiles can be assigned a symmetry type (based on the dihedral group $D4$). This allows the algorithm to enumerate adjacent pairs only up to symmetry, significantly shortening the adjacency lists.
    • Non-Wang Tilesets: Some tilesets (like 'Circuit', 'Summer', or 'Rooms') are non-Wang, meaning their adjacency data cannot be fully represented by edge labels alone (e.g., diagonal connections or specific directional constraints).

  5. Using WFC for Constrained Synthesis

    master

    WFC supports constraints, allowing it to be integrated with manual design or other generative processes:

    • Human-AI Collaboration: WFC can be used to 'autocomplete' a level or pattern started by a human.
    • Hybrid Pipelines:
      • ConvChain + WFC: Use ConvChain to get a well-sampled configuration (satisfying strong C2) and then run WFC to correct local defects (satisfying C1).
      • WFC + Texture Synthesis: Use WFC to generate a perfect 'blueprint' (e.g., a brick wall layout) and then use a faster algorithm like P. F. Harrison's texture synthesis to apply the actual textures.

  6. Build the WaveFunctionCollapse console application

    master

    WaveFunctionCollapse is a .NET Core console application that depends only on the standard library. To build and run the application, you must have .NET Core installed on your Windows, Linux, or macOS system.

    Run the application

    To build and immediately execute the application in Release mode, use:

    dotnet run --configuration Release WaveFunctionCollapse.csproj

    Build a self-contained executable

    To build the application without running it, use the publish command:

    dotnet publish --configuration Release WaveFunctionCollapse.csproj

    After publishing, a self-contained executable will be located in the bin/publish folder. You can run WaveFunctionCollapse.exe to generate artifacts, which will appear in the output folder.

    Configuration

    You can modify the model parameters by editing the samples.xml file.