# 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
- 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.
```shell
cargo run --release --example image
```

_Sudoku example_

This example demonstrates usage of a sequential wave function collapse algorithm.
```shell
cargo run --release --example sudoku
```

_Landscape example_

This example demonstrates usage of an accommodating wave function collapse algorithm.
```shell
cargo run --release --example landscape
```

_Sparse example_

This example demonstrates usage of an accommodating wave function collapse algorithm along with more sparse probabilities.
```shell
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.
```shell
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.
```shell
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**