The original idea for this algorithm comes from Paul Merrell’s 2007 i3D paper as well as his much longer PhD thesis. Maxim Gumin (alias mxgmn) would take this original idea and slightly modify it as well as give it the now iconic “wave function collapse” name.
Comparison to model synthesis
Merrell wrote a comparison of the two algorithms. He does a fine job of comparing the two but honestly it comes off as hater behavior simply because it was written after WFC was released and it’s hilarious how it became 10× more popular/well known than his “model synthesis.”
- Which tile to collapse next is different. Model synthesis “sweeps through the grid in scanline order” while WFC selects the tile with the lowest entropy (i.e. least number of possible states).
- This greatly affects runtime. Model synthesis is able to handle larger inputs better while WFC may become slower or not finish at all.
- Model synthesis focuses more on generating 3D models than 2D textures (although WFC can also be generalized to any number of dimensions, including apparently the 4th dimension, time).
Algorithm
Overall structure, written in [[C Sharp|C#]].
public class WFC {
public void Iterate() {
var nextCellToCollapse = PickLowestEntropyCell();
Collapse(nextCellToCollapse);
Propagate(nextCellToCollapse);
}
public void Run() {
// Or, we enable the user to step through each iteration via UI
while (!AllCellsCollapsed()) {
Iterate();
}
}
}Propagate(): use a stack to keep track of which tiles we still have to process. Before adding tiles to the stack, check that they’re not already in it.
For PickLowestEntropyCell(), the simplest implementation is to uniformly pick at random a state from the set of possible states in a grid cell. Of course, we can make it more interesting by assigning weights to each cell, considering its neighbors first, etc.