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
• 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
• 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

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

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