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

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

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/

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

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?

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/

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

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

Reminds me of Dorfromantik[0].

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