Here are some notes I wrote and links I found when researching Wave Function Collapse (WFC). -Don Hopkins Wave Function Collapse Maxim Gumin Paul Merrell https://paulmerrell.org/research/ https://paulmerrell.org/model-synthesis/ Liang et al Jia Hui Liang, Vijay Ganesh, Ed Zulkoski, Atulan Zaman, and Krzysztof Czarnecki. 2015. Understanding VSIDS branching heuristics in conflict-driven clauselearning SAT solvers. In Haifa Verification Conference. Springer, 225–241. WaveFunctionCollapse is constraint solving in the wild https://escholarship.org/content/qt1f29235t/qt1f29235t.pdf?t=qwp94i Constraint Satisfaction Problem (CSP) Machine Learning (ML) Constraint Solving Search space of possibilities. Heuristics, domain specific or independent. Aid selection of promising variables to select. Aid decision of promising values to assign to variables. Backtracking search. Some WFC implementations don't use backtracking, and some do. Gumin’s original formulation of WaveFunctionCollapse does not make use of backtrack. Rather than using local backtracking, Gumin’s implementation simply globally restarts when it reaches a contradiction. Constraint propagation. Game AI Pro 2: Rulling Your Own Finite-Domain Constraint Solver When originally released in 2016, Gumin’s code implemented an AC-3 style propagation algorithm that was later improved with an asymptotically more efficient AC-4 style algorithm in 2018. https://en.wikipedia.org/wiki/AC-3_algorithm Constraint Solving in Procedurally Generated Content (PCG). Taxonomy of Procedural Generated Content Search Based Methods [13] WFC is unique in that it is directly constructive, and performs search at the level of completed candidate designs. Works with partial designs, resulting in visually stunning animations, and is easily driven by artists. Horswill and Foged [14] describe a “fast” method for populating a level design with content under strong playability guarantees. Their algorithm is based on backtracking search with (AC3) constraint propagation. Although it makes only modest demand on processor and memory resources, it is expected to be used by programmers who are at least moderately literate in search algorithm design. In G. Smith’s Tanagra system [15], a mixed-initiative platformer level design tool, the Choco [16] solver is invoked to solve a specific geometric layout subproblem in the overall level design process. Answer Set Programming (ASP) is a form of logic programming targeted at modeling combinatorial search and optimization problems. [17] A. M. Smith proposed the use of ASP in PCG [1] within the paradigm of modeling design spaces. Rather than directly aiming to code and algorithm for generating content, this approach suggests we should declaratively model the space of content we want to see and let a domain-independent solver take care of the procedural aspects. Although programmers using ASP need not have or use any knowledge of search algorithm design, they are expected to be familiar with the declarative programming paradigm and Prolog-like syntax. This background is not common amongst technical artists who were recently excited to find WaveFunctionCollapse. Modern answer set solvers (such as Clingo [19]) allow for specification of custom heuristics, externally checked constraints interleaved with the search process, and hooks for scripting languages in the service of integrating solvers with outside environments. These custom extension points in Clingo have been used to replicate the incremental growth behavior of WFC to produce an animated log of the solver’s decisions. One way that WaveFunctionCollapse stands out from many other PCG algorithms is that both the input and the output are images. The implications of using patterns will be examined in more detail below, but for now the important property to note is that they can be interpreted as convolutions that compress the surrounding context into a value associated with a single point. WFC is primarily concerned with grids of these pattern identifiers. The final result of the analysis is a set of patterns and an adjacency matrix that describes which patterns can be validly placed next to one another. WFC is not a monolithic generator, but rather a multi-stage pipeline of generators and data transformations (Fig. 2). Many variations on this pipeline exist in the wild, but all of the members of this family share the core adjacency-learning and constraint solving stages. Breaking the general case down to component steps, the stages in the complete list are: making data input interpretable as tiles, tile classification and grouping, pattern classification and adjacency learning, constraint solving, and rendering the result of the constraint solver into tile data. “Content-agnostic algorithm for placing tiles. Heavily based on the work of @ExUtumno. Basically a Sudoku-solver on steroids.” https://twitter.com/OskSta/status/784847588893814785 https://github.com/lamelizard/GraphWaveFunctionCollapse “last one for tonight, a 3 second loop!” https://twitter.com/MattRix/status/872674537799913472 https://github.com/mewo2/oisin “I can help with the grasp part. WFC is basically a constraint solver. You start with everything unknown and when possible cross out contradictory parts. If you have nothing to cross - then guess a random piece.” "Yeah, as someone else said somewhere, basically a sudoku solver on steroids! :)" https://twitter.com/ExUtumno/status/793601984800624640 Gumin gives an example of an “easy” tileset: “the unrestrained knot tileset (with all 5 tiles being allowed) is not interesting for WFC, because you can’t run into a situation where you can’t place a tile” and without “special heuristics” the length of correlations in the generated image quickly fall [6]. “Procedural generation from a single example by wave function collapse” https://twitter.com/ExUtumno/status/781833475884277760 @MattRix, Jun 8, 2017: “yep exactly! :) it has 3 dimensions, but the trick is that it has 14 edges so it can check forward & backward “diagonally” in time” "I should be clear, by "edges" I mean that each slot connects to 14 other slots (four around it in the present, 5 before it and 5 after it)" https://twitter.com/MattRix/status/872785320445706241 https://twitter.com/MattRix/status/872641331956518914 https://twitter.com/MattRix/status/872645716660891648 https://twitter.com/MattRix/status/872648369625325568 https://twitter.com/MattRix/status/872674537799913472 https://twitter.com/MattRix/status/872884946918150145 https://oskarstalberg.com/game/wave/wave.html https://selfsame.itch.io/unitywfc Comparison of Paul Merrell's Model Synthesis with Maxim Gumin's Wave Function Collapse. https://paulmerrell.org/wp-content/uploads/2021/07/comparison.pdf One game developer who has contributed to the popularization of WFC is Oskar Stalberg. A technical artist who previously worked on Tom Clancy’s The Division, Stalberg was ˚among the first to start generalizing WFC, extending it with other tile shapes, 3D meshes, performance optimizations, and adding backtracking. In May 2017, as part of a talk about his approach to procedural generation, he released a “small browser demo” to illustrate how his version of the algorithm works under the hood. Notably, Stalberg’s WFC started as ˚a clean-room implementation based on the animations rather than on the original code." Stalberg would go on to use his implementation of WFC in the viking invasion game Bad North, released in 2018. One commercially-released indie game that uses WFC is Caves of Qud, which added partially-WFC-generated villages in July 2018. Caves of Qud is a roguelike developed by Freehold Games that is currently in early-access release. One of the developers, Brian Bucklew, started experimenting with using WFC for level generation. Caves of Qud uses WFC as part of a pipeline, adding additional pre-generation constraints, using WFC multiple times with different input images, and making further changes to the map after the generation is run. One of the benefits of WFC that Caves of Qud has demonstrated is that the simple inputs mean that it is much easier for the entire team to experiment with the generator. The Caves of Qud developers noticed two drawbacks of WFC: isotropy and overfitting. While WFC can capture long range correlations, there are limits and large images tend toward isotropy and homogeneity at lower frequencies. Their solution to this was to partition the space with other algorithms and only run WFC on a subset of the level. Likewise, adding more detail to the small training image risked over-constraining the results, as the training overfitted to the image. Their solution was to avoid putting too much detail in the training image and instead add detailing (such as extra doors) using other approaches later in the pipeline. WaveFunctionCollapse in Caves of Qud is an addition to an existing level generator. While Bad North also uses WFC as part of a pipeline, the Bad North island generator would not exist without WFC. Bad North islands are constructed out of 3D modules, designed in Maya and exported into Unity with a process that calculates which modules have matching geometry along their edges. These “profiles” are used to define the adjacencies: modules with matching profiles are allowed to be adjacent. Some larger modules take up multiple spaces. Variation across islands is achieved by changing the set of modules allowed for an island, thereby creating regions of similar islands by having them use similar sets of tiles and allowing a progression to be created from the input to WFC. The islands are constructed on three-dimensional 11 × 11 grids (with some degree of vertical space) and some additional constraints, the most important of which is a connectivity local constraint: the island needs guaranteed paths from the Vikings on the beach to the houses the player is defending. Khokhlov, Koh, and Huang developed a voxel synthesis approach based on WFC and Merrell’s texture synthesis work, taking advantage of WFC’s ability to learn from single-input models. M. Khokhlov, I. Koh, and J. Huang, “Voxel synthesis for generative design,” in Design Computing and Cognition ’18, J. S. Gero, Ed. Cham: Springer International Publishing, 2019, pp. 227–244. https://www.youtube.com/watch?v=2SuvO4Gi7uY Superpositions, Sudoku, the Wave Function Collapse algorithm. Martin Donald In this video I explore the how the wave function collapse algorithm, and explain how I went about implementing it using Blender and Godot. WFC demos on itch: https://bolddunkley.itch.io/wfc-mixed https://bolddunkley.itch.io/wave-function-collapse References: https://marian42.de/article/wfc/ https://oskarstalberg.com/game/wave/wave.html https://github.com/mxgmn/WaveFunctionCollapse https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/ https://rxi.itch.io/tilekit Tilekit is a tilemap editor centered around pattern-based auto tiling. Python code: https://github.com/ikarth/wfc_2019f “Visualizing WaveFunctionCollapse reimplemented in ASP: 46x46 Flowers N=3, using clingo’s default heuristic (VSIDS). Just 3 conflicts.” https://twitter.com/rndmcnlly/status/867605489789489152 https://twitter.com/rndmcnlly Adam M. Smith (史亚当) @rndmcnlly Assistant Professor of Computational Media at @ucsc; applied artificial intelligence & information retrieval for interactive media; languages; cooking; dad; adhd. https://twitter.com/isaackarth Isaac Karth @isaackarth Researching AI and Procedural Generation at UCSC. Raised in the wild by feral graduate students. He/him. http://procedural-generation.tumblr.com isaac@isaackarth.com https://isaackarth.com/ https://twitter.com/ExUtumno/status/1531992699997507586 Maxim Gumin @ExUtumno I published a new project about combining rewrite rules and solving constraint problems made of rewrite rules https://github.com/mxgmn/MarkovJunior