5 ms·

Using Wave Function Collapse to solve puzzle map generation at scale

92 points by greentec 1y ago

greentec 1y ago
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?
- fjfaase 1y ago
  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 https://www.iwriteiam.nl/D1801.html#4 [2] https://www.iwriteiam.nl/ST8x8FixedPalette.html https://www.iwriteiam.nl/ST8x8FixedPalette.html [3] https://www.iwriteiam.nl/D1606.html#5 https://www.iwriteiam.nl/D1606.html#5
  - greentec 1y ago
    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!
    - fjfaase 1y ago
      I was just wondering this for myself, not something for you to figure out.
phi-go 1y ago
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.
- quantadev 1y ago
  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."
- jerf 1y ago
  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.
  - phi-go 1y ago
    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.
    - jerf 1y ago
kookamamie 1y ago
> Wave Function Collapse I've always found the name pretty misleading and grandiose, relative to what the algorithm actually does.
- quantadev 1y ago
  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.
  - kookamamie 1y ago
    It is even funnier when you consider that the entire algorithm is deterministic, assuming a fixed seed for a PRNG.
    - quantadev 1y ago
      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.
- b33j0r 1y ago
  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.
  - kookamamie 1y ago
    > 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.
zenoengine 1y ago
Great article! The idea of applying WFC to puzzle generation is really clever. Thanks for sharing!
- greentec 1y ago
  Thank you for your kind words.

92 points by greentec 1y ago

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?

fjfaase 1y ago
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 https://www.iwriteiam.nl/D1801.html#4 [2] https://www.iwriteiam.nl/ST8x8FixedPalette.html https://www.iwriteiam.nl/ST8x8FixedPalette.html [3] https://www.iwriteiam.nl/D1606.html#5 https://www.iwriteiam.nl/D1606.html#5
- greentec 1y ago
  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!
  - fjfaase 1y ago
    I was just wondering this for myself, not something for you to figure out.

phi-go 1y ago

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.

quantadev 1y ago
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."
jerf 1y ago
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.
- phi-go 1y ago
  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.
  - jerf 1y ago

kookamamie 1y ago

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

quantadev 1y ago
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.
- kookamamie 1y ago
  It is even funnier when you consider that the entire algorithm is deterministic, assuming a fixed seed for a PRNG.
  - quantadev 1y ago
    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.
b33j0r 1y ago
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.
- kookamamie 1y ago
  > 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.

zenoengine 1y ago

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

greentec 1y ago
Thank you for your kind words.