[HN Gopher] Building a Procedural Hex Map with Wave Function Col...
___________________________________________________________________
Building a Procedural Hex Map with Wave Function Collapse
Author : imadr
Score : 326 points
Date : 2026-03-09 17:02 UTC (5 hours ago)
(HTM) web link (felixturner.github.io)
(TXT) w3m dump (felixturner.github.io)
| MattDamonSpace wrote:
| Gorgeous
| gedy wrote:
| Real engineering skills, I love it.
| contextfree wrote:
| "Stop playing your AI garbage and get to bed!" "Mooooom! It's not
| AI garbage, it's classical procedurally generated content!"
| xipho wrote:
| 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 wrote:
| 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 wrote:
| This looks amazing man, seriously good job with this.
| jesse__ wrote:
| 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.
| zimpenfish wrote:
| > I did a wfc implementation a while back and moved to
| bitfields after a while.. the speedup was incredible.
|
| Yeah, my WFC bot (which happens to generate Carcassonne maps in
| an amusing coincidence) eventually ended up using
| https://github.com/bits-and-blooms/bitset which improved things
| hugely.
|
| > It became faster to just recompute a chunk from scratch
|
| Kinda what mine does - every now and again[0] it stacks the
| current state and if it gets stuck, just pops the last one and
| continues from there.
|
| [0] Just checked and it's every `tileCount / 20` iterations,
| hilariously in a variable named `tenper`. I hate past me.
| bobek wrote:
| Made me smile. Thank you!
| moi2388 wrote:
| This entire article reads like it was fully written by AI
| unfortunately
| imadr wrote:
| Is it the em dashes? I didn't get the feeling it was AI
| generated at all
| zparky wrote:
| 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
| ArcaneMoose wrote:
| Beautiful work!
| tomtomistaken wrote:
| Reminds me of Dorfromantik[0].
|
| [0] https://store.steampowered.com/app/1455840/Dorfromantik/
| bhaak wrote:
| Which is based on the board game of the same name.
|
| https://boardgamegeek.com/boardgame/370591/dorfromantik-the-...
| the_mitsuhiko wrote:
| The other way around.
| bhaak wrote:
| Oh, wow, TIL. Both were released in 2022 but the video game
| already had an alpha release in 2021.
| kevinsync wrote:
| Super awesome, love the tilt-shift camera effect!
|
| I was also wishing I could zoom in to human size and run around
| HAHAHA
| matthewfcarlson wrote:
| 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
| schemathings wrote:
| 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/
| zparky wrote:
| They link to that site in the post
| schemathings wrote:
| Ah I read it but missed it!
| behnam_amiri wrote:
| This is cool. Curious if you plan on keep it as a map generator
| or turn it into something more interactive too.
| rhdunn wrote:
| Oskar Stalberg 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 Stalberg - Beyond Townscapers).
| jcalx wrote:
| 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 wrote:
| That "Carcassonne" game sounds really fun. I'd never heard of it
| before.
| shoo wrote:
| it's a classic. 2001 Spiel des Jahres Winner.
|
| see https://boardgamegeek.com/boardgame/822/carcassonne
| porphyra wrote:
| 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
| shoo wrote:
| 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.
| porphyra wrote:
| 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/
| westurner wrote:
| 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 wrote:
| This is absolutely beautiful, I could even tell I was going to
| like it from the title. Good job.
| btbuildem wrote:
| 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)!
| OscarCunningham wrote:
| 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?
| teamonkey wrote:
| 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.
| gmueckl wrote:
| Less than perfect solutions can make certain types of video
| games more interesting because the domain of potential
| results is generally larger and can include many more
| variations of challenges to the player.
| jbmsf wrote:
| 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.
| z3t4 wrote:
| "WebGPU is not available on your device or browser.". Other 3d
| demos works fine though. Tried Firefox and Opera on mobile.
| foota wrote:
| 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.
| MattRix wrote:
| 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
| llm_nerd wrote:
| This is fun and neat, and looks fantastic, but the generated maps
| are basically nonsensical, aren't they? Landmasses and waterways
| and roads and buildings and forests and so on that don't make any
| logical sense for their placement.
|
| I say this having had a couple of fun "hex-based strategy game
| hobby projects" over the years (sidenote -- trying to cover a
| sphere in hexes is actually a non-trivial matter). Invariably I
| ended up with "to make a map from scratch, first you create the
| universe" where I'd go through all of the ages, compute
| waterflows and precipitation, and on and on. Maybe I made the
| requirements too unreasonable and that's precisely why I never
| yielded a working game from it.
| zimpenfish wrote:
| > This is fun and neat, and looks fantastic, but the generated
| maps are basically nonsensical, aren't they?
|
| WFC lets you address that though with extra constraints. e.g.
| my bot today generated a church inside a river loop[0] -
| completely useless! But I could add a rule that says "if you
| place the church-above-river tile, the tile above that cannot
| be anything horizontally blocking" (obviously after tagging any
| relevant tiles as "horizontally blocking" in the tileset) and
| that would prevent "church in a river loop" situations.
|
| (I've already been working on some extra rules because, e.g., I
| don't like the one-edge-castle-wall tiles being placed next to
| each other - you get tiny pasty shaped castles and I hate
| them.)
|
| [0]
| https://social.browser.org/fileserver/01E5NFWNPGZWNJ0DS1WE88...
| - bottom 3 rows, just past halfway across
| profer602 wrote:
| Interesting exploration of WFC on a non-square grid. The
| constraint propagation challenges must be significantly more
| complex than the 'canonical' example. Makes me wonder if a
| different constraint solver (e.g., constraint logic programming)
| might offer advantages in terms of expressiveness and performance
| for these more complex topologies.
| djray wrote:
| The demo runs at 5 FPS on my laptop (11th gen Core i5 and Iris Xe
| graphics, Chrome Latest as the browser, with the GPU being the
| bottleneck). I was hoping for something rather more efficient
| given the write-up saying it ran at 60 fps on mobile.
|
| The maps are pretty, but the per-tile build constraints of the
| WFC build approach means that pretty unnatural generations end up
| happening because non-local influence is difficult to take into
| account. I think this may be OK for games where you discover
| tiles one at a time, but for a full map generator it's not great,
| and better solutions exist. Red Blob Games did a writeup of a
| noise-based method which looks superior imo. You can use
| moisture-tracking approaches for rivers, lay roads, bridges and
| other artificial elements in a separate pass, and it will likely
| end up faster and more robust. I think WFC is an interesting
| programming problem, though, so it was likely fun to implement.
|
| Nonetheless, this was an excellent write-up and impressive demo.
___________________________________________________________________
(page generated 2026-03-09 23:00 UTC)