[HN Gopher] Using Wave Function Collapse to solve puzzle map gen...
___________________________________________________________________
Using Wave Function Collapse to solve puzzle map generation at
scale
Author : greentec
Score : 81 points
Date : 2025-06-23 00:42 UTC (22 hours ago)
(HTM) web link (sublevelgames.github.io)
(TXT) w3m dump (sublevelgames.github.io)
| greentec wrote:
| 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 wrote:
| 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
| greentec wrote:
| 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 wrote:
| I was just wondering this for myself, not something for you
| to figure out.
| phi-go wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| kookamamie wrote:
| > Wave Function Collapse
|
| I've always found the name pretty misleading and grandiose,
| relative to what the algorithm actually does.
| quantadev wrote:
| 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 wrote:
| It is even funnier when you consider that the entire
| algorithm is deterministic, assuming a fixed seed for a PRNG.
| quantadev wrote:
| 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 wrote:
| 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 wrote:
| > 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.
| b33j0r wrote:
| 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.
| kookamamie wrote:
| 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.
| rcxdude wrote:
| Which is essentially how a basic sudoku solver works
| (which usually only has one solution, as opposed to many)
| furyofantares wrote:
| That's a very long name.
| ca_tech wrote:
| 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...
| Ygg2 wrote:
| - Stohastic Sudoku solvers
| gavinray wrote:
| > Tile Constraint Pairing
|
| This seems pretty solid to me.
| IsTom wrote:
| Ad hoc Prolog
| furyofantares wrote:
| Constraint Collapse would be good
| layer8 wrote:
| They should at least use a QRNG, then it would be somewhat
| justified.
| nh23423fefe wrote:
| 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.
___________________________________________________________________
(page generated 2025-06-23 23:01 UTC)