Building a Procedural Hex Map with Wave Function Collapse
felixturner.github.io
felixturner.github.io
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.
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.
[0] https://potassco.org/clingo/
(Dwarf Fortress is the one procedural game I know - besides maybe its more faithful clones - which isn't static. But the procedural generation there is also mostly not incremental, it generates the whole world beforehand and only some of the fill-in details are incrementally generated).
The holy grail has to be a graph-based refinement/embellishment system, where it generates just the nodes, temporally and spatially, which matter for the situation the player is in.
It feels a bit like the graphical equivalent of Markov chain text generation.
Rimworld is interesting here, as it is what I would consider a DF style game. And I would have said the same for it, except that the latest expansion (Oddessy) added space ships that you can build, and fly to another area. While fun this has made the procedural generation show its weaknesses.
(That said, DF world gen is top notch, but probably not quite as good as it may seem due to what I mentioned.)
Remember that wave function collapse focuses on local optimization. The algorithm can’t take a step back and look at the whole map. That’s why you won’t get a sensible road network. Rivers are only slightly better when the follow height gradients.
What you can do, and this is also a general advice for procgen, is to mix in some templates before WCF runs. Often, a bit of post-processing is needed as well.
The templates can be hand-designed, or generated with simpler procgen code. Place a few towns on the map, connect them with roads, and then let WFC fill in the gaps to create a more interesting landscape.
Source: working on a Noita-like so have spent a bit of time looking at prior art. Noita wiki.gg will explain a lot of it though (warning: many spoilers).
The goal of the original algorithm ( https://github.com/mxgmn/WaveFunctionCollapse ) is to infer the constraints from a sample, and then run a constraint solver.
Hard-coding the constraints skips the whole point of the algorithm (which is also badly named by the way).
I think this algorithm is more efficient for generating maps with only local (adjacency) constraints, but setting this up as an integer linear program and plugging it into a constraint solver is more generalizable (say, if you wanted to enforce a constraint that rivers had to flow across the whole map and could not loop).
But I agree "wave function collapse" is not really the best name, for two reasons:
- the original repository mentions "it doesn't do the actual quantum mechanics, but it was inspired by QM", but it implies something QM-related.
- as an ORIE major in college that loved optimization, I think constraint satisfaction problems are really cool and actually somewhat approachable! So calling the heuristic something else like "wave function collapse" might limit people from finding previous work and known improvements (e.g. forward checking).
[0] https://www.cs.cornell.edu/courses/cs4700/2011fa/lectures/05...
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.
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
That said, there's an Apple TV video of a castle on an island where my first thought was "why does this exist?"
"Though hidden from the sea, the castle controls access to Loch Shiel" says Wikipedia. Which is a sensible thing for a castle to do back in the olden times.
Plus it's a tidal island - you can just walk across. Don't even need a drawbridge (although I guess that makes defending attacks from inland a bit tricky.)
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.
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.
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.
It looks to be that the demo has been fixed since I initially looked. Testing today showed much improved performance.
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.
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.
[0] https://store.steampowered.com/app/1455840/Dorfromantik/
https://boardgamegeek.com/boardgame/370591/dorfromantik-the-...
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.
There is, a hexagonal grid is isomorphic to a [skewed] rectangular grid, i.e. it can also be indexed with a coordinate pair (u, v). The neighbours are at offsets (+1, 0), (-1, 0), (0, +1), and (0, -1) - just as in a rectangular grid - and the two additional neighbours are at (+1, -1) and (-1, +1). The coordinates in the plane are (x, y) = (√3(u + v/2), 3v/2) or some variation of this, depending on how exactly one lays out the hexagons and picks axes.
It is surprisingly hard to find a good illustration for this, or maybe I am using the wrong search terms, but here [1] is the best one I could quickly find.
[1] https://www.researchgate.net/figure/Rhomboidal-and-hexagonal...
> 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...
In the level data, the start/goal tiles (approx 10x10 blocks of solid ground under the player and goal) and slopes aren't represented by their tile offset in the level data -- whilst all other "ground" tiles are. Instead, for slopes you're only told the start and end coordinates, and they often overlap.
So to render the slopes correctly I had to work out all the rules for which tiles were allowed next to each other, and solve some ambiguity rules -- I figured out that shallow slopes take precedence over steep ones. Eventually I cracked it, but it took quite a week or so of iteration to figure it out.
For guiding the search, you might want to consider search steps that select only one feature, for example that a pair of adjacent tiles should be connected by a road, and just propagate that information. That could be used as a way to guide the search on high-level features first, and then later realize the plans by doing the normal search.
"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
"Here's the dirty secret of WFC: it fails. A lot. You make a series of random choices, propagate constraints, and eventually back yourself into a corner where some cell has zero valid options left. Congratulations, the puzzle is unsolvable."
I was also wishing I could zoom in to human size and run around HAHAHA