Using Wave Function Collapse to solve puzzle map generation at scale

I hit an interesting problem with my puzzle game Logic Islands - 3 out of 6 rulesets would hang forever trying to generate maps larger than 7x7.

The trick that worked? Using Wave Function Collapse, but choosing what to generate based on each ruleset - islands for some, walls for others. This flexibility made complex constraints (like "no 2x2 blocks") trivial to express as tile connection rules.

My favorite result: the "Minimal" ruleset enforces "all wall regions must be exactly 3 cells" using just 11 tiles and local WFC constraints. No post-processing needed.

Now generates 12x12 maps instantly instead of hanging forever.

Anyone else using WFC for logic puzzles beyond typical texture synthesis?

Interesting algorithm, thanks for sharing. I was wondering what the connection of Wave Function Collapse is to constraint solving, since it seems to do very similar things. Looks like there was a paper written on this topic: "WaveFunctionCollapse is Constraint Solving in the Wild". Still need to read it, though.

> Wave Function Collapse

I've always found the name pretty misleading and grandiose, relative to what the algorithm actually does.

They say "On each step...[yadda yadda] we have a completely observed state, the wave function has collapsed."

So they're trying justify calling a "state" a "collapse". That's a bad metaphor to start with, but then they try to use that metaphor to justify calling lots of other stuff "waves" that are unrelated to waves, and continue to shove that square peg thru a round hole. Hilarious.

Every time you locate something in space and/or time, it means a wave has collapsed. So that statement is as trivial as saying "constraints are about positions of things in space time." It's about as enlightening as saying "clocks tick" or "rulers have numbers on them."

I think the metaphor is great.

Each tile has a superposition of possible states that collapse into one observed state. That’s all the metaphor is meant to mean, I think.

What are better names?

- Lego Simplices

- Tile Constraint Pairing

- Pipe Fitting

- Cartesian Convolution (nah)

- Finite automata (ok that’s fair, but subthings need names)

I dunno, I think the WFC metaphor works for me. The “wavefunction” is just the finite set of states that have a non-zero probability of being observed.

> Each tile has a superposition of possible states

This is like saying an uninitialized integer has a superposition of all possible values. I find it a very convoluted way of saying "each tile has a set of possible next states" - dragging quantum terms to this is just confusing, in my opinion.

You’re not wrong. I think I initially had higher expectations myself. But as a person who names things, I don’t really find this one to be a huge stretch.

> This is like saying an uninitialized integer has a superposition of all possible values.

Well? Yeah! And I personally like that way of thinking about sets. It maps pretty directly to my understandings of other things in math and physics.

Here's the algorithm described without the quantum nonsense:

1. Analyze Rules: Extract valid patterns (modules) and their compatibility rules (adjacency constraints) from input or define them.

2. Initialize Grid: Create an output grid where each cell initially contains all possible modules (maximum uncertainty).

3. Choose and Assign: Select the cell with the fewest valid modules remaining. Randomly assign one compatible module to it.

4. Propagate Constraints: Update neighboring cells by removing modules incompatible with the newly assigned one. If a cell loses all options, a contradiction occurs.

5. Handle Contradiction: If a contradiction arises, either backtrack to a previous choice or restart the process.

6. Repeat: Continue from step 3 until all cells are assigned a module or an unresolvable contradiction occurs.

It is even funnier when you consider that the entire algorithm is deterministic, assuming a fixed seed for a PRNG.

Which is essentially how a basic sudoku solver works (which usually only has one solution, as opposed to many)

I wonder how well it will work for generating certain street tile patterns, where tiles of different sizes are used and where it is not allowed to have four tiles meeting at one point and where there are no H-patterns. See [1] for a large pattern and [2] for an animation using patterns within an 8 by 8 square. I did figure out a set of Wang tiles [3].

[1] https://www.iwriteiam.nl/D1801.html#4

[2] https://www.iwriteiam.nl/ST8x8FixedPalette.html

[3] https://www.iwriteiam.nl/D1606.html#5

Nice to meet you. It seems that you have been researching this topic in depth. Since you have been researching this topic for a long time, I don't have any immediate thoughts on it, but I think I need to think about it a little more.

While working on Simple-Tiled WFC this time, I kept wondering whether I should reference neighbours in more than four directions, but in the end, I'm glad I finished without referencing them. I hope this Random Street Tile Pattern can also be solved in such an elegant way!

- Stohastic Sudoku solvers

  > Tile Constraint Pairing

This seems pretty solid to me.

Ad hoc Prolog

They should at least use a QRNG, then it would be somewhat justified.

That's a very long name.

There's no "connection". This is constraint solving. The supposed connection to quantum theory in the name is spurious, as that is not what superpositions are, nor is it how nature resolves them, nor is it even particularly defendable as an "approximation". It's something else entirely.

It is what it is now, but when you see people like me grumbling about the name, this is basically why.

It's like all those "I built a monad library!" posts that in fact haven't even come close, they're missing half-a-dozen critical properties of monads, all they can do is "Maybe" or "Either", and then someone else sees that library and thinks that's what "monads" are and pass the confusion down even farther in the next generation of "monad" libraries. Words mean what people use them to mean in the end, but there are still some meanings sometimes worth at least trying to defend.

It's a bad name because you can only measure in 1 basis.

Real wave functions collapse based on the measurement apparatus.

There isn't any interference phenomena. It's just bad.

I was just wondering this for myself, not something for you to figure out.

Constraint Collapse would be good

I know. It's hard to tell if they're trying to be jokingly "cringe" about all the "wave" stuff, or simply that non-conversant about wave theory and QM.

The first definition of this type of procedural generation algorithm was called Model Synthesis by Paul Merrell [1] which built upon texture synthesis. You can even read Merrell's later comparison of the two algorithms [2].

[1] https://paulmerrell.org//thesis.pdf [2] https://paulmerrell.org/wp-content/uploads/2021/07/compariso...

Thank you, I was kind of expected this. I can understand your frustration, the name is definitely misleading.

Sorry for another ignorant question. Does WFC have a corresponding algorithm name in constraint solving literature? The paper I mentioned partially reimplements it using answer set programming which seems to be closely related to SAT solving.

I don't know if it has an official name; in that space it would just be a trivial variant of searching the tree (or graph, depending on how you look at it) defined by the constraints by taking random paths through it and backtracking if you get stuck.

Perhaps another angle of frustration with the name is that people apply the Quantum WooWoo to the algorithm and go all "whooaaaa" when it fact it's basically the first thing you might think of when solving a constraint problem.

Which is not to say that is a bad thing. Putting the "simplest solution to this class of problems" into your toolbelt is a good thing. That's why a lot of schools cover things like A* search and linked lists; in the real world you often need some elaborations but there's also plenty of problems you can solve with them as-is and it's a good starting point. It's just the conceptual interference from the name that is a bit annoying.

Great article! The idea of applying WFC to puzzle generation is really clever. Thanks for sharing!

Thank you for your kind words.