Using Wave Function Collapse to solve puzzle map generation at scale
sublevelgames.github.io
Using Wave Function Collapse to solve puzzle map generation at scale
1–10 of 29 posts
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#2I 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?
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#3Interesting 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.
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#4> Wave Function Collapse
I've always found the name pretty misleading and grandiose, relative to what the algorithm actually does.
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#5> 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.
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#6Interesting 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.
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."
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#7> Wave Function Collapse I've always found the name pretty misleading and grandiose, relative to what the algorithm actually does.
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.
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#8> Wave Function Collapse I've always found the name pretty misleading and grandiose, relative to what the algorithm actually does.
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…
> 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.
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#9Earlier quoted context omitted.
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…
> 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.
Re: Using Wave Function Collapse to solve puzzle map generation at scale
#10Earlier quoted context omitted.
> 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.