2d implementation of the Wave Function Collapse algorithm

Two versions:

• JavaScript: running live on the web
• Rust - a multi-processed cli tool
• GitHub: https://github.com/LelsersLasers/WFC

What is Wave Function Collapse?

In quantum mechanics, wave function collapse occurs when a wave function—initially in a superposition of several eigenstates—reduces to a single eigenstate due to interaction with the external world. This interaction is called an observation, and is the essence of a measurement in quantum mechanics, which connects the wave function with classical observables such as position and momentum.
— Wikipedia

How does Wave Function Collapse work?

WFC initializes output bitmap in a completely unobserved state, where each pixel value is in superposition of colors of the input bitmap (so if the input was black & white then the unobserved states are shown in different shades of grey). The coefficients in these superpositions are real numbers, not complex numbers, so it doesn't do the actual quantum mechanics, but it was inspired by QM. Then the program goes into the observation-propagation cycle:

• On each observation step an NxN region is chosen among the unobserved which has the lowest Shannon entropy. This region's state then collapses into a definite state according to its coefficients and the distribution of NxN patterns in the input.
• On each propagation step new information gained from the collapse on the previous step propagates through the output.

On each step the number of non-zero coefficients decreases and in the end we have a completely observed state, the wave function has collapsed.
It may happen that during propagation all the coefficients for a certain pixel become zero. That means that the algorithm has run into a contradiction and can not continue. The problem of determining whether a certain bitmap allows other nontrivial bitmaps satisfying condition (C1) [(C1): the output should contain only those NxN patterns of pixels that are present in the input] is NP-hard, so it's impossible to create a fast solution that always finishes. In practice, however, the algorithm runs into contradictions surprisingly rarely.
— mxgmn
More information: https://github.com/mxgmn/WaveFunctionCollapse#algorithm

(Note: My implementation approximately follows this)

Main Resources Used

• Gumin, M. (2016). Wave Function Collapse Algorithm (Version 1.0) [Computer software]. https://github.com/mxgmn/WaveFunctionCollapse
• solub's Python Processing implementation: https://discourse.processing.org/t/wave-collapse-function-algorithm-in-processing/12983
• Wikipedia: https://en.wikipedia.org/wiki/Wave_function_collapse
• The Coding Train's video: 
• Martin Donald's video:
  
  

Image Sources

• https://www.youtube.com/watch?v=TO0Tx3w5abQ
• https://github.com/mxgmn/WaveFunctionCollapse