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 2 hours 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].
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!
phi-go 6 hours 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 5 hours 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."
kookamamie 6 hours ago [-]
> Wave Function Collapse
I've always found the name pretty misleading and grandiose, relative to what the algorithm actually does.
b33j0r 4 hours 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.
gavinray 30 minutes ago [-]
> Tile Constraint Pairing
This seems pretty solid to me.
kookamamie 4 hours 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.
b33j0r 4 hours ago [-]
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 4 hours ago [-]
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 3 hours ago [-]
Which is essentially how a basic sudoku solver works (which usually only has one solution, as opposed to many)
IsTom 15 minutes ago [-]
Ad hoc Prolog
Ygg2 48 minutes ago [-]
- Stohastic Sudoku solvers
quantadev 5 hours 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 3 hours ago [-]
It is even funnier when you consider that the entire algorithm is deterministic, assuming a fixed seed for a PRNG.
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
[2] https://www.iwriteiam.nl/ST8x8FixedPalette.html
[3] https://www.iwriteiam.nl/D1606.html#5
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.
> 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.
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.