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!
Building a Procedural Hex Map with Wave Function Collapse
21–30 of 92 posts
Re: Building a Procedural Hex Map with Wave Function Collapse
#22This 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
Re: Building a Procedural Hex Map with Wave Function Collapse
#23Reminds 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-...
Re: Building a Procedural Hex Map with Wave Function Collapse
#24The 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.
Re: Building a Procedural Hex Map with Wave Function Collapse
#25Model 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...
Re: Building a Procedural Hex Map with Wave Function Collapse
#26Re: Building a Procedural Hex Map with Wave Function Collapse
#27This is absolutely beautiful, I could even tell I was going to like it from the title. Good job.
Re: Building a Procedural Hex Map with Wave Function Collapse
#28I 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)!
Re: Building a Procedural Hex Map with Wave Function Collapse
#29It 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?
Re: Building a Procedural Hex Map with Wave Function Collapse
#30It 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…
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.