Wave function collapse is an extremely disappointing algorithm

For those who don't know, the WFC is used in procedural generation, especially to generate maps in games. The algorithm is generally explained using concepts from quantum mechanics, because that's how it was named. Think of a tile based map system, which starts out empty, with every cell "possibly" being any tile. Each cell is thus in a "superposition" of being all possible tiles.

You have some rules about which tiles can be next to each other, often conditioned on the different directions. (The rules can be anything you can program, and as complex as you like, but this is the common approach.) For instance, water and grass tiles can't be next to each other, but they can be next to a grass-to-water transition tile (in the correct direction). Or a roof tile can only be above a building/wall tile or similar. The rules may also include a weight value to specify that some tiles are more probable than others in some conditions.

The nice part is that while you do have to program the types of rules you care about, the specific rules can be generated from an example, making it versatile and easy even for non-programmers to "change the rules". You will allow all patterns that exist in the example, and none that don't. And the probabilities will be determined by the frequency of a tile in a given pattern, or rule.

To generate, you start with your empty map. If you then "collapse" the probability space of one cell into a single specific tile, that then limits the possible tiles of other cells (because of your rules). If you continue this, prioritizing the cell with the least possibilities (entropy), it's like a wave propagating the collapse of the superpositions according to some function (the probabilities), and you end up with map generated according to your rules.

This seems very elegant, but it is not. The problem is that this algorithm almost always fails to generate a complete map, because the tiles being "collapsed" one by one (without the regard for anything else) causes a large number of cells to have no valid possibilities at all.

For the algorithm to work, you have to implement the ability to backtrack and try different tiles than were picked originally. Sometimes you have to backtrack quite far. This quickly becomes unfeasible (given the number of combinations), so after some amount of backtracking you'll need a reset mechanism. You can reset "locally" some area around a failure to get a fresh start (hoping for a less restrictive combination of tiles). If you keep failing then reset a larger area, and eventually start over from a completely empty map.

Yes. That is correct. This is the "secret sauce" of the quantum mechanics inspired, fancily named, Wave Function Collapse algorithm. It's a brute-force algorithm which simply tries different combinations in random order until it finds one that works, with the ability to jump to a very different random "location" in case it gets stuck in a poor locality.

Now, I'm not saying this is a bad way to do procedural generation. In fact, in the right conditions it can work really well. Although I think the real value is actually in how you generate the rules and probabilities from an example.

However, instead of trying to make it sound all fancy and amazing with the explanations about superpositions and possibility spaces in quantum mechanics, you can much better explain it simply as "just iteratively add randomly sampled partial solutions, if they don't work together, eliminate some of them and keep iterating", but then you realize how disappointing the algorithm is.