alt.hn

3/9/2026 at 5:02:22 PM

Building a Procedural Hex Map with Wave Function Collapse

 https://felixturner.github.io/hex-map-wfc/article/

by imadr

3/9/2026 at 6:43:21 PM

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

by porphyra

3/9/2026 at 8:59:51 PM

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.

by shoo

3/9/2026 at 10:53:16 PM

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.

by djray

3/9/2026 at 11:13:07 PM

I’m stunned - works fine on mobile for me. I’m curious how you determine FPS, I was hoping the site had an indicator, but either I’m missing it, or it’s Chrome Dev Tools (and thus it’s presumably impossible for me to get on iOS/Android)

by refulgentis

3/9/2026 at 6:31:29 PM

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/

by jcalx

3/9/2026 at 5:58:43 PM

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.

by jesse__

3/9/2026 at 10:15:03 PM

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

by zimpenfish

3/9/2026 at 10:57:57 PM

AI;DR. Can the author please just post the prompt?

by hananova

3/9/2026 at 11:12:55 PM

This sentiment is quickly becoming the most annoying low-effort comment on HN. If you don't want to read it, don't read it. If something about the writing offends you, then describe it, so we can talk about it.

by iamjs

3/9/2026 at 7:26:20 PM

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?

by OscarCunningham

3/9/2026 at 7:45:34 PM

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.

by teamonkey

3/9/2026 at 10:35:33 PM

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.

by gmueckl

3/9/2026 at 10:27:43 PM

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.

by profer602

3/9/2026 at 5:48:17 PM

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

by xipho

3/9/2026 at 9:08:42 PM

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.

by foota

3/9/2026 at 6:15:47 PM

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/

by schemathings

3/9/2026 at 6:25:42 PM

They link to that site in the post

by zparky

3/9/2026 at 6:36:28 PM

Ah I read it but missed it!

by schemathings

3/9/2026 at 8:41:18 PM

"WebGPU is not available on your device or browser.". Other 3d demos works fine though. Tried Firefox and Opera on mobile.

by z3t4

3/9/2026 at 7:07:50 PM

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

by ionwake

3/9/2026 at 9:14:13 PM

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

by MattRix

3/9/2026 at 7:18:26 PM

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

by btbuildem

3/9/2026 at 10:06:15 PM

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.

by llm_nerd

3/9/2026 at 10:21:23 PM

> 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

by zimpenfish

3/9/2026 at 8:31:12 PM

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.

by jbmsf

3/9/2026 at 5:44:43 PM

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

by contextfree

3/9/2026 at 5:55:17 PM

This looks amazing man, seriously good job with this.

by nickandbro

3/9/2026 at 6:14:12 PM

Super awesome, love the tilt-shift camera effect!

I was also wishing I could zoom in to human size and run around HAHAHA

by kevinsync

3/9/2026 at 8:39:06 PM

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

by matthewfcarlson

3/9/2026 at 6:16:14 PM

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

by behnam_amiri

3/9/2026 at 5:48:52 PM

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.

by verdverm

3/9/2026 at 5:59:16 PM

Made me smile. Thank you!

by bobek

3/9/2026 at 5:21:01 PM

Gorgeous

by MattDamonSpace

3/9/2026 at 6:04:34 PM

Beautiful work!

by ArcaneMoose

3/9/2026 at 6:46:59 PM

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

by westurner

3/9/2026 at 5:41:58 PM

Real engineering skills, I love it.

by gedy

3/9/2026 at 6:01:27 PM

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

by moi2388

3/9/2026 at 6:29:20 PM

Is it the em dashes? I didn't get the feeling it was AI generated at all

by imadr

3/9/2026 at 6:38:22 PM

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

by zparky