The post glosses over the "backtracking" and says they just limit it to 500 steps but actually constraint programming is an extremely interesting and complicated field with lots of cool algorithms and tricks. In this case we could solve it with Knuth's Algorithm X [1] with dancing links, which is a special kind of backtracking. Algorithm X should, in theory, be able to solve the border region described in the article's "Layer 2" with a higher success rate as opposed to 86%.
Furthermore, various heuristics can speed up the backtracking a lot compared to a brute force approach. As anyone who has implemented a Sudoku solver can attest, a brute force backtracking is easy to implement but will immediately get bogged down with slowness.
there's also a bunch of dedicated constraint programming solvers / high level modelling languages for these kinds of constraint-y combinatorial optimisation problems
e.g. https://www.minizinc.org/ offers a high level modelling language that can target a few different solver backends
might be pretty good results to completely ignore writing a custom algorithm and drop in an existing industrial-grade constraint programming solver, model your procgen problem using a high level language, and use the existing solver to find you random solutions (or exhaustively enumerate them). then more time to iterate on changing the problem definition to produce more interesting maps rather than getting bogged down writing a solver.
Yeah, you can also use Clingo [0] which is pretty popular and people have tried it specifically with WFC content generation [1]. You can even run it in the browser easily [2].
Reminds me of Jasper Flick's Unity tutorial on hex terrain [0] which is similarly wonderfully detailed. Interesting contrast: this project uses premade tiles and constraint solving to match tile boundaries, while that one dynamically generates tile boundaries (geometries, blending, etc.) on the fly. Both enjoyable reads!
As an aside, if the author reads this, did you consider using bitfields for the superposition state (ie, what options are available for a tile)? I did a wfc implementation a while back and moved to bitfields after a while.. the speedup was incredible. It became faster to just recompute a chunk from scratch than backtrack because the inner loop was nearly completely branchless. I think my chunks were 100 tiles cubed or something.
It seems like a lot of the difficulty is in finding arrangements that satisfy constraints. I wonder if an alternative approach would be to use a SAT solver. I suppose the problem with that approach would be that the solver might always find an 'easy' solution that doesn't look random. I know that some SAT solvers let you randomly assign the initial assignments of the variables, but that doesn't mean you get a random solution. Has anyone tried a similar approach?
I think the problem with SAT solvers is that they’re complicated, in terms of computation and also how easy it is to understand by someone who didn’t study formal methods.
WFC is brute-force-simple, but because it’s simple it’s quite computationally inexpensive (unless it hits a lot of dead-ends) and I wouldn’t be surprised if it could often find an adequate solution quicker than a SAT solver. At least for games, where a result doesn’t need to be perfect, just good enough.
I realize this comes up every so often, but I was just looking at this the other day :) A related idea is wang tiles, which are a way to construct a tileset such that you can place them without ever running into a contradiction.
Inspirational stuff, with lots of great references to the OGs at the bottom, and source available. Now can it be merged with the look/feel of https://heredragonsabound.blogspot.com/. ;)
Years and years ago (pre-smart phone), I built a mobile map and navigation product. Labeling streets was one of the more interesting side quests and the solution I found took a similar approach of generating a large number of candidates, picking one solution, and iterating. It worked quite well in practice.
I really like the part where you can "reroll" sub-areas of each tile. Consider exposing some of the weight knobs (eg, I'd like to tweak it to favour mountainous terrain)!
Fun fact: because WFC is graph-based, you can do stuff like creating a graph where it uses time as a dimension, so you can create animations that “wrap” in time.
In this rabbit example I made 8 years ago, the WFC solver ensures that the animation must loop, which means you will always end up with an equal number of births and deaths.
I started on a simple coop top-down pirate game yesterday when this popped up. I will probably switch the map generation to be using something like this tbh
Related (?) has anyone else been following the Hytale Worldgen v2? They've built a visual node editor so anyone can create biomes, structures, or complete worlds. I believe there is a competition going on right now.
They are essentially making the entire game based on similar concepts and then using them to develop their core content. Simon is an inspiration and has said they won't be taking investor money so they can stay true to the users and creators.
> Model synthesis (also wave function collapse or 'wfc') is a family of constraint-solving algorithms commonly used in procedural generation, especially in the video game industry.
> [...] One of the differences between Merrell & Gumin's implementation and 'wave function collapse' lies in the decision of which cell to 'collapse' next. Merrell's implementation uses a scanline approach, whereas Gumin's always selects as next cell the one with the lowest number of possible outcomes
The post glosses over the "backtracking" and says they just limit it to 500 steps but actually constraint programming is an extremely interesting and complicated field with lots of cool algorithms and tricks. In this case we could solve it with Knuth's Algorithm X [1] with dancing links, which is a special kind of backtracking. Algorithm X should, in theory, be able to solve the border region described in the article's "Layer 2" with a higher success rate as opposed to 86%.
Furthermore, various heuristics can speed up the backtracking a lot compared to a brute force approach. As anyone who has implemented a Sudoku solver can attest, a brute force backtracking is easy to implement but will immediately get bogged down with slowness.
[1] https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
there's also a bunch of dedicated constraint programming solvers / high level modelling languages for these kinds of constraint-y combinatorial optimisation problems
e.g. https://www.minizinc.org/ offers a high level modelling language that can target a few different solver backends
might be pretty good results to completely ignore writing a custom algorithm and drop in an existing industrial-grade constraint programming solver, model your procgen problem using a high level language, and use the existing solver to find you random solutions (or exhaustively enumerate them). then more time to iterate on changing the problem definition to produce more interesting maps rather than getting bogged down writing a solver.
Yeah, you can also use Clingo [0] which is pretty popular and people have tried it specifically with WFC content generation [1]. You can even run it in the browser easily [2].
[0] https://potassco.org/clingo/
[1] https://adamsmith.as/papers/tog-wfc.pdf
[2] https://potassco.org/clingo/run/
Oskar Stålberg used wave function collapse for various games, including Townscaper. He talks about it here: https://www.youtube.com/watch?v=Uxeo9c-PX-w&pp=ygUhdG93bnNjY... (SGC21- Oskar Stålberg - Beyond Townscapers).
Reminds me of Jasper Flick's Unity tutorial on hex terrain [0] which is similarly wonderfully detailed. Interesting contrast: this project uses premade tiles and constraint solving to match tile boundaries, while that one dynamically generates tile boundaries (geometries, blending, etc.) on the fly. Both enjoyable reads!
[0] https://catlikecoding.com/unity/tutorials/hex-map/
Love this.
As an aside, if the author reads this, did you consider using bitfields for the superposition state (ie, what options are available for a tile)? I did a wfc implementation a while back and moved to bitfields after a while.. the speedup was incredible. It became faster to just recompute a chunk from scratch than backtrack because the inner loop was nearly completely branchless. I think my chunks were 100 tiles cubed or something.
It seems like a lot of the difficulty is in finding arrangements that satisfy constraints. I wonder if an alternative approach would be to use a SAT solver. I suppose the problem with that approach would be that the solver might always find an 'easy' solution that doesn't look random. I know that some SAT solvers let you randomly assign the initial assignments of the variables, but that doesn't mean you get a random solution. Has anyone tried a similar approach?
I think the problem with SAT solvers is that they’re complicated, in terms of computation and also how easy it is to understand by someone who didn’t study formal methods.
WFC is brute-force-simple, but because it’s simple it’s quite computationally inexpensive (unless it hits a lot of dead-ends) and I wouldn’t be surprised if it could often find an adequate solution quicker than a SAT solver. At least for games, where a result doesn’t need to be perfect, just good enough.
I realize this comes up every so often, but I was just looking at this the other day :) A related idea is wang tiles, which are a way to construct a tileset such that you can place them without ever running into a contradiction.
Inspirational stuff, with lots of great references to the OGs at the bottom, and source available. Now can it be merged with the look/feel of https://heredragonsabound.blogspot.com/. ;)
OP is probably familiar but this site has a lot of good examples of hex math with code examples - https://www.redblobgames.com/grids/hexagons/
They link to that site in the post
Ah I read it but missed it!
Reminds me of Dorfromantik[0].
[0] https://store.steampowered.com/app/1455840/Dorfromantik/
Which is based on the board game of the same name.
https://boardgamegeek.com/boardgame/370591/dorfromantik-the-...
The other way around.
Oh, wow, TIL. Both were released in 2022 but the video game already had an alpha release in 2021.
"WebGPU is not available on your device or browser.". Other 3d demos works fine though. Tried Firefox and Opera on mobile.
This is absolutely beautiful, I could even tell I was going to like it from the title. Good job.
Years and years ago (pre-smart phone), I built a mobile map and navigation product. Labeling streets was one of the more interesting side quests and the solution I found took a similar approach of generating a large number of candidates, picking one solution, and iterating. It worked quite well in practice.
I really like the part where you can "reroll" sub-areas of each tile. Consider exposing some of the weight knobs (eg, I'd like to tweak it to favour mountainous terrain)!
That "Carcassonne" game sounds really fun. I'd never heard of it before.
it's a classic. 2001 Spiel des Jahres Winner.
see https://boardgamegeek.com/boardgame/822/carcassonne
"Stop playing your AI garbage and get to bed!" "Mooooom! It's not AI garbage, it's classical procedurally generated content!"
This looks amazing man, seriously good job with this.
Fun fact: because WFC is graph-based, you can do stuff like creating a graph where it uses time as a dimension, so you can create animations that “wrap” in time.
In this rabbit example I made 8 years ago, the WFC solver ensures that the animation must loop, which means you will always end up with an equal number of births and deaths.
https://xcancel.com/MattRix/status/979020989181890560
Super awesome, love the tilt-shift camera effect!
I was also wishing I could zoom in to human size and run around HAHAHA
I started on a simple coop top-down pirate game yesterday when this popped up. I will probably switch the map generation to be using something like this tbh
This is cool. Curious if you plan on keep it as a map generator or turn it into something more interactive too.
Related (?) has anyone else been following the Hytale Worldgen v2? They've built a visual node editor so anyone can create biomes, structures, or complete worlds. I believe there is a competition going on right now.
They are essentially making the entire game based on similar concepts and then using them to develop their core content. Simon is an inspiration and has said they won't be taking investor money so they can stay true to the users and creators.
Made me smile. Thank you!
Gorgeous
Beautiful work!
Model synthesis: https://en.wikipedia.org/wiki/Model_synthesis :
> Model synthesis (also wave function collapse or 'wfc') is a family of constraint-solving algorithms commonly used in procedural generation, especially in the video game industry.
> [...] One of the differences between Merrell & Gumin's implementation and 'wave function collapse' lies in the decision of which cell to 'collapse' next. Merrell's implementation uses a scanline approach, whereas Gumin's always selects as next cell the one with the lowest number of possible outcomes
And then `## Developments` mentions:
"Hierarchical semantic wave function collapse" (2023) Alaska, Bidarra: .. citations of: https://scholar.google.com/scholar?cites=1671019743611687613...
Real engineering skills, I love it.
This entire article reads like it was fully written by AI unfortunately
Is it the em dashes? I didn't get the feeling it was AI generated at all
It's current year, of course they used AI to help [0], and it does feel like the article was AI assited.
"This map isn't flat — it has 5 levels of elevation."
"The ocean isn't just a blue plane — it has animated caustic sparkles"
"The fundamental issue:" and "The key constraint:"
I still enjoyed the article.
[0] https://github.com/felixturner/hex-map-wfc/commit/1679be