Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Using Wave Function Collapse to solve puzzle map generation at scale

sublevelgames.github.io

Post reply on HN
Print view View original

11–20 of 29 posts

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#11

Post by kookamamie »

quantadev wrote: post #5
kookamamie wrote: post #4

> 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.

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

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#12

Post by rcxdude »

kookamamie wrote: post #10
b33j0r wrote: post #9

Earlier quoted context omitted.

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 compati…

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

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#13

Post by fjfaase »

greentec wrote: post #2

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: th…

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

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#14

Post by greentec »

fjfaase wrote: post #13
greentec wrote: post #2

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: th…

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.iwriteia…

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!

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#15

Post by Ygg2 »

b33j0r wrote: post #7
kookamamie wrote: post #4

> 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…

- Stohastic Sudoku solvers

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#16

Post by gavinray »

b33j0r wrote: post #7
kookamamie wrote: post #4

> 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…

  > Tile Constraint Pairing
This seems pretty solid to me.

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#17

Post by IsTom »

b33j0r wrote: post #7
kookamamie wrote: post #4

> 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…

Ad hoc Prolog

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#19

Post by furyofantares »

kookamamie wrote: post #10
b33j0r wrote: post #9

Earlier quoted context omitted.

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 compati…

That's a very long name.

Re: Using Wave Function Collapse to solve puzzle map generation at scale

#20

Post by jerf »

phi-go wrote: post #3

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.

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.

Post reply on HN