### 4 releases (2 breaking)

0.3.0 | Sep 8, 2024 |
---|---|

0.2.0 | Aug 16, 2023 |

0.1.2 | Dec 7, 2022 |

0.1.0 | Nov 30, 2022 |

#**420** in Algorithms

**217** downloads per month

**MIT/Apache**

395KB

6K
SLoC

# Wave Function Collapse

Converts nodes and their constraints upon other nodes into a fully collapsed node state based on the selected algorithm. This can be used to solve any degree of complexity from dense node graphs to Sudoku to procedurally-generated game elements and more.

## Features

- Basic interface to make usage easy to try out
- The graph does
**not**need to be fully connected - Any missing constraints between two nodes imply that the former node, for that state, has no impact on the neighbor node

- The graph does
- Allows for tailoring the algorithm to the problem
- A full sequential search of all possible solutions when it is known that very few, one, or no solutions are possible
- Can determine if the wave function is not collapsable

- A random search for more heterogenious solutions when many solutions are possible, but may never complete given certain circumstances
- An entropic propagating search that makes for interesting images based on model image data

- A full sequential search of all possible solutions when it is known that very few, one, or no solutions are possible
- Different probabilities per state per node can be suggested to allow for either faster results or different random results (based on the algorithm used)
- Examples showing how different constraint problems can be solved via the different algorithms
- The wave function can be saved and loaded from file
- Abstractions on top of the wave function collapse functionality
- A proximity graph with flexible placement of values into the nodes of that graph

## Usage

To use this framework, you will first want to determine the following:

- What is the type of your node states?
- An enum because there are only specific states?
- A UUID String because it may be unknown at compile time?
- A u64 because it is a reference to an identifier in a database?
- An image fragment struct which contains overlapping image pixel data?

- What does your graph of nodes look like?
- Is it a flat grid like a checkerboard?
- Is it a 3D grid like a voxel game (ex: Minecraft)?
- A binary directed tree?

- What node states, for any specific node, would permit which other node states for its neighbor nodes?
- Can direct neighbors of nodes not have the same state as the current node?
- Are only certain states possible when the node is in this special state?

Once these are answered, you can construct the vector of nodes and the vector of node state collections that those nodes reference for their permissive relationships. Please examine a relevant example to see how the construction of nodes and node state collections occurs.

## Examples

*Image example*

This example demonstrates the same functionality showcased in https://github.com/mxgmn/WaveFunctionCollapse.

`cargo`` run`` --`release` --`example image

*Sudoku example*

This example demonstrates usage of a sequential wave function collapse algorithm.

`cargo`` run`` --`release` --`example sudoku

*Landscape example*

This example demonstrates usage of an accommodating wave function collapse algorithm.

`cargo`` run`` --`release` --`example landscape

*Sparse example*

This example demonstrates usage of an accommodating wave function collapse algorithm along with more sparse probabilities.

`cargo`` run`` --`release` --`example sparse

*Zebra puzzle example*

This example demonstrates usage of a sequential wave function collapse algorithm for word problems like the Zebra Puzzle.

`cargo`` run`` --`release` --`example zebra_puzzle

*Perlin example*

This example demonstrates usage of the proximity graph abstraction that shows how placement of game locations can be done in a dynamically generated environment.

`cargo`` run`` --`release` --`example perlin

## Complex problems

*Shared conditions between nodes*

When you want to say that "when node 1 is in state A and node 2 is in state B then node 3 can only be in state C", you will end up needing to have multiple variations of the same node state such that our previously mentioned state "B" would be equivalent to "B when node 1 is A". This would permit you to specify for node 2 that when it is in the state "B when node 1 is A", then it will only permit node 3 to be in state C.

**Example coming soon**

#### Dependencies

~5–14MB

~182K SLoC