Wave function collapse is the popular name for a constraint-solving algorithm commonly used in procedural generation, especially in the videogame industry. An earlier name for the algorithm is 'model synthesis'.
The algorithm was popularised in a 2016 release on GitHub by Maxim Gumin, in a repository containing his initial implementation. Since then, WFC as an algorithm has been widely adopted, adapted, and used by technical artists and game developers.[1]
Gunim's WFC implementation was inspired by some other similar concepts, including discrete synthesis, Markov chains, quantum mechanics, and convolutional neural network style transfer.[2] Its name, 'wave function collapse' stems from an analogy drawn by Gumin between the algorithm and the concept of superposition in quantum mechanics.[3][4] Whilst inspired by quantum physics, it does not rely on concepts from that field.
Prior to WFC's popularisation, a conceptually identical algorithm was developed in 2007 by Paul Merrell and Dinesh Moncha which they named 'Model Synthesis'.[5] Merrell & Moncha's implementation didn't catch on in popularity to the same degree that WFC did, possibly due to lower accessibility, its 3D focus, or computing constraints at the time.[6]
Developments
In April 2023 Shaad Alaka and Rafael Bidarra of Delft University proposed 'Hierarchical Semantic wave function collapse'. Essentially, the algorithm is modified to work beyond simple, unstructured sets of tiles. Prior to their work, all WFC algorithm variants operated on a flat set of tile choices per cell.[7]
Their generalised approach organizes tile-sets into a hierarchy, consisting of abstract nodes called 'meta-tiles', and terminating nodes called 'leaf tiles'.[8] For example, on the first pass, WFC might make a certain tile a meta-tile of 'castle' type; which on a second pass will be collapsed into other tiles based on a rule, e.g. a 'wall' or 'grass' tile.
References
- ^ Alaka, 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).
- ^ "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.
- ^ https://paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf
- ^ 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.
- ^ Alaka, Shaad; Bidarra, Rafael (April 2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. pp. 1–10. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8.
To the best of our knowledge, however, all such WFC algorithm variants operate on a flat set of tile choices per cell.
{{cite book}}:|journal=ignored (help) - ^ Alaka, Shaad; Bidarra, Rafael (April 2023). "Hierarchical Semantic Wave Function Collapse". Proceedings of the 18th International Conference on the Foundations of Digital Games. pp. 1–10. doi:10.1145/3582437.3587209. ISBN 978-1-4503-9855-8.
We propose a solution to these shortcomings by introducing (i) the notion of meta-tile, an abstract tile that represents a semantic group of tiles, along with (ii) a graph-like structure that is able to represent the hierarchy among them and the constraints between them.
{{cite book}}:|journal=ignored (help)
 | This software article is a stub. You can help Wikipedia by expanding it. |
 | This video game–related article is a stub. You can help Wikipedia by expanding it. |
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |