Building a Procedural Hex Map with Wave Function Collapse

gedy

Real engineering skills, I love it.

contextfree

"Stop playing your AI garbage and get to bed!" "Mooooom! It's not AI garbage, it's classical procedurally generated content!"

xipho

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/ . ;)

verdverm

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.

nickandbro

This looks amazing man, seriously good job with this.

jesse__

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.

bobek

Made me smile. Thank you!

moi2388

This entire article reads like it was fully written by AI unfortunately

ArcaneMoose

Beautiful work!

tomtomistaken

Reminds me of Dorfromantik[0]. [0] https://store.steampowered.com/app/1455840/Dorfromantik/

kevinsync

Super awesome, love the tilt-shift camera effect! I was also wishing I could zoom in to human size and run around HAHAHA

schemathings

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/

behnam_amiri

This is cool. Curious if you plan on keep it as a map generator or turn it into something more interactive too.

rhdunn

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

jcalx

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/

jcul

That "Carcassonne" game sounds really fun. I'd never heard of it before.

porphyra

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

westurner

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

ionwake

This is absolutely beautiful, I could even tell I was going to like it from the title. Good job.