You start with an array where every tile is possible in every location. Then you pick a random cell and assign a tile to it. That tile implies some choices are impossible, so you set those possibilities to false. That further implies some other possibilities are false and so on. You propogate that as far as it goes, and when you are done, pick another random cell and assign a random possible tile to it.
Because you are propogating information as much as possible before making the next choice, the algorithm very rarely needs to backtrack. You can run WFC without any backtracking at all and it'll still find a solution most of the time.
Some animated examples I put together might illustrate things more: https://boristhebrave.github.io/DeBroglie/articles/gallery.h...
It's just constraint propogation, optimized for certain conditions and given a fancy name.
I guess you could call it a markov random field, but I don't think it does unbiased sampling.
You 'measure' one cell, and then all the other ones 'collapse' to values consistent with the result, because they have a hidden relationship with the cell you measured.
That's what happens in quantum mechanics. When you measure one thing, all the other things its entangled with collapse somewhat too - but not necessarily completely, it depends on the entanglement they had with the measured system.
It's a metaphor, I'm just saying it's very apt, not that it's mathematically equivalent.
1) X ? 2) X Y 3) X ? 4) X Y
? ? ? ? Z ? Z ?
The trick is that you must calculate amplitudes, not probabilities. For example, Y may contribute an amplitude of .5 to the bottom right corner , and the probability is (.5)^2=.25. And Z may contribute an amplitude of -.3 to the bottom right corner , and the probability is (-.3)^2=.09. But when both are there the amplitudes must be added and the probability is (.5-.3)^2=.04.
This is a case of destructive interference that reduces the probability of a particular tile when both are present, but if both have the same sign it can be a constructive interference and increase the probability of that tile.
This type of interference is what produce the weird interference lines in the double slit experiment (and even in the single slit experiment).
This project just add probabilities, without squaring the numbers, so it's more difficult to have quantum-like weird things.
Anyway, I like the result very much. Nice project. Nice name.
You're going to tile (say) the plane with a set of tiles you've chosen beforehand. (In this example, it looks like the tiles are 3d.) There are rules for which tiles can go next to each other---the edges must match.
As you go, there are two regions: a region in which you've settled on which tiles to use, and a boundary region in which you haven't. In the boundary region, you keep track of a probability distribution over the tiles. This distribution is influenced by the neighboring tiles (exactly how is probably the most interesting bit of the algorithm; I don't know).
The algorithm proceeds by repeatedly (i) picking a tile on the boundary that has a very skewed probability distribution, and fixing it to be the most likely tile; and (ii) updating the probability distributions of the neighboring tiles in the boundary.
It's possible that you end up making poor tile placements at the beginning that gets you stuck later, so the algorithm must sometimes backtrack to undo past decisions. You want to pick a set of tiles such that the algorithm doesn't need to backtrack too often, or it will take too long.
Note that the distribution is an ordinary probability distribution, not a sum of complex amplitudes like the name "Wave Function Collapse" would make you think.
One might also consider placing the algorithm in the context of a generative adversarial network (GAN) to adapt the tile probability modeling ML component towards a pattern that is less distinguishable from a real city.