Model synthesis a.k.a. wave function collapse or 'wfc' are names for a family of constraint-solving algorithms commonly used in procedural generation, especially in the video game industry.
Some video games known to have utilized variants of the algorithm include Bad North, Townscaper, and Caves of Qud.
The first example of this type of algorithm was described by Paul Merrell, who termed it 'model synthesis' first in his 2007 i3D paper [1] and also presented at the 2008 SIGGRAPH conference and his 2009 PhD thesis.[2] The name 'wave function collapse' later became the popular name for a variant of that algorithm, after an implementation by Maxim Gumin was published in 2016 on a GitHub repository with that name.[3] Gumin's implementation significantly popularised this style of algorithm, with it becoming widely adopted and adapted by technical artists and game developers over the following years.[3]
There were a number of inspirations to Gumin's implementation, including Merrell's PhD dissertation, ideas from quantum mechanics, and convolutional neural network style transfer.[4][5] The popular name for the algorithm, 'wave function collapse', is from an analogy drawn between the algorithm's method and the concept of superposition and observation in quantum mechanics.[6][7] Some innovations present in Gumin's implementation included the usage of overlapping patterns, allowing a single image to be used as an input to the algorithm.[8]
Some have speculated that the reason Gumin's implementation proved more popular than Merrell's, may have been due to the 'model synthesis' implementation's lower accessibility, its 3D focus, or perhaps the general public's computing constraints at the time.[9]
One of the differences between Merrell & Gumin's implementation and 'wave function collapse' lies in the decision of which cell to 'collapse' next. Merrell's implementation uses a scanline approach, whereas Gumin's always selects as next cell the one with the lowest number of possible outcomes.[10]
^Merrell, Paul (April 2007). "Example-based model synthesis" (PDF). I3D '07: Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games: 105–112. doi:10.1145/1230100.1230119. ISBN 978-1-59593-628-8.
^Merrell, Paul (2009). Model Synthesis(PDF). Chapel Hill.{{cite book}}: CS1 maint: location missing publisher (link)
^ abAlaka, Shaad; Bidarra, Rafael (2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. Foundations of Digital Games 2023 (FDG 2023). p. 2. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8. In 2016, Maxim Gumin unleashed the WFC algorithm, publishing a repository containing his initial implementation. Since then, WFC has had a profound impact on technical artists and game developers, getting adopted, adapted and used in commercially published and upcoming projects (Caves of Qud, Townscaper, Matrix Awakens).
^Merrell, Paul (Aug 6, 2023). Procedural Modeling Using Graph Grammars (Video). Event occurs at 3:13.
^"Implementing Wave Function Collapse & Binary Space Partitioning for Procedural Dungeon Generation". Shaan Khan. 2021-03-21. Retrieved 2024-03-24. In the case of WFC it is inspired off three distinctive but functionally similar algorithms& concepts; Texture Synthesis (Specifically Discrete Synthesis), Markov Chains & Quantum Mechanics. WFC was also additionally inspired by convolution neural network style transfer (CNN Style Transfer).
^Gumin, Maxim (September 2016), Wave Function Collapse Algorithm, retrieved 2024-03-24
^"The Wavefunction Collapse Algorithm explained very clearly". Robert Heaton. Retrieved 2024-03-24.
^Gumin, Maxim (September 2016), Wave Function Collapse Algorithm, retrieved 2024-03-25
^Alaka, Shaad (2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. Foundations of Digital Games 2023 (FDG 2023). p. 2. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8. Years before, Merrel had published the conceptually identical Model Synthesis algorithm, though it did not catch on as much as WFC did, possibly due to its lower accessibility, main 3D focus and computing requirements at the time.
^Merrell, Paul (28 July 2021). "Comparing Model Synthesis and Wave Function Collapse" (PDF). The first difference is in the step where we choose a cell and pick a label. The cells are chosen in a different order. Model synthesis sweeps through the grid in scanline order. WFC chooses the lowest entropy cell.
Modelsynthesis a.k.a. wave function collapse or 'wfc' are names for a family of constraint-solving algorithms commonly used in procedural generation...
Physical modellingsynthesis refers to sound synthesis methods in which the waveform of the sound to be generated is computed using a mathematical model, a...
Spectral modelingsynthesis (SMS) is an acoustic modeling approach for speech and other signals. SMS considers sounds as a combination of harmonic content...
arriving train in Sweden. Problems playing this file? See media help. Speech synthesis is the artificial production of human speech. A computer system used for...
The neoclassical synthesis (NCS), neoclassical–Keynesian synthesis, or just neo-Keynesianism was a neoclassical economics academic movement and paradigm...
Additive synthesis example A bell-like sound generated by additive synthesis of 21 inharmonic partials Problems playing this file? See media help. Additive...
Frequency modulation synthesis (or FM synthesis) is a form of sound synthesis whereby the frequency of a waveform is changed by modulating its frequency...
corrin-ring closure being attained between rings A and B. The second modelsynthesis, published 1969, explored a novel photochemical cycloisomerization...
waveforms through methods including subtractive synthesis, additive synthesis and frequency modulation synthesis. These sounds may be altered by components...
leading to a novel texture synthesis method. Another recent development is the use of generative models for texture synthesis. The Spatial GAN method showed...
this, in a model that used the Calvo pricing model. Goodfriend and King proposed a list of four elements that are central to the new synthesis: intertemporal...
Three routes dominate, but many other methods exist. The Hantzsch pyrrole synthesis is the reaction of β-ketoesters (1) with ammonia (or primary amines) and...
High-Resolution Image Synthesis with Latent Diffusion Models (2021, updated in 2022). This paper describes the latent diffusion model (LDM). This is the...
asymmetrical gamma subunit. According to the current model of ATP synthesis (known as the alternating catalytic model), the transmembrane potential created by (H+)...
Articulatory synthesis refers to computational techniques for synthesizing speech based on models of the human vocal tract and the articulation processes...
[bare URL PDF] Kypuros, Javier A.; Longoria, Raul G. (2004-01-29). "ModelSynthesis for Design of Switched Systems Using a Variable Structure System Formulation"...
the program was released in August 2006. The software's physically modeledsynthesis create sound from scratch using several megabytes of mathematical...
In organic chemistry, peptide synthesis is the production of peptides, compounds where multiple amino acids are linked via amide bonds, also known as...
2002). "Neural and Mechanical Contributions to the Stretch Reflex: A ModelSynthesis". Annals of Biomedical Engineering. 30 (1): 54–67. doi:10.1114/1.1432692...
the business model is a simplified representation of how we do business, we still have to decide which elements to describe. A synthesis of literature...
Enantioselective synthesis, also called asymmetric synthesis, is a form of chemical synthesis. It is defined by IUPAC as "a chemical reaction (or reaction...
Digital waveguide synthesis is the synthesis of audio using a digital waveguide. Digital waveguides are efficient computational models for physical media...