Using Wave Function Collapse to solve puzzle map generation at scale
sublevelgames.github.io
sublevelgames.github.io
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?
[1] https://www.iwriteiam.nl/D1801.html#4
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!
I've always found the name pretty misleading and grandiose, relative to what the algorithm actually does.
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.
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.
[1] https://paulmerrell.org//thesis.pdf [2] https://paulmerrell.org/wp-content/uploads/2021/07/compariso...
> 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.
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.
> Tile Constraint Pairing
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.
Real wave functions collapse based on the measurement apparatus.
There isn't any interference phenomena. It's just bad.
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.
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.
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.