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.
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.
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].
I have a (very slight) beef with the name Algorithm X, as it is more of a data-structure to manage undo-information for the backtracking than an algorithm. It is a very fun, useful, and interesting data-structure, but it doesn't really change what steps are performed in the backtracking search.
It's beautiful. But also pretty unsatisfying in a way. Roads don't make sense. Rivers barely make sense. There's no higher-scale structure - the reason why most games with incremental procedural generation usually feel stale after a while, and always static. Every planet is different, yet feels the same.
(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.
That's a general problem with procedurally generated content.
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.
As I recall, a lot goes into DF's world generation, including erosion simulation and the like to achieve a realistic result. That game is the embodiment of over-engineering, after all.
I think it helps in Dwarf Fortress that you are not really exploring the world (well, unless you play adventurer mode, but that seems far less popular), you pick a site and settle and start building. You see far less of the world than in something like Minecraft. Yes, you get to see more of the world over multiple runs, but it is still far more limited.
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.)
Situation-adaptive generation also gets predictable and boring once you can read it easily. Classic procedural generation is good for perceived variety and breaking small patterns, but it doesn't introduce novelty on its own, it just shifts it from the asset design to the algorithm design.
I didn't want to nitpick terminology, but yes, the tile-placement algorithm here is just a way of solving constraint satisfaction problems with DFS using a "minimum remaining values" heuristic [0]. The original use case for generating textures [1] is different in that the constraints are implicit in the input bitmap, but this project is a more straightforward tile placement with explicit constraints.
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).
Colloquially this is what gamedevs mean when they refer to WaveFunctionCollapse (though the constraints may or may not be inferred from tiles or 3D models, depending on the implementation). It may not match the academic terminology exactly
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.
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)
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.
> 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.
I read an 'i hate myself' post one time where someone encountered a variable named leghands. Obviously, it had once read legendHandles, and had since been helpfully shortened by the author.
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!
Hex math is weird. Since there are 6 directions instead of 4, there's no simple mapping between hex positions and 2D x,y coordinates.
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.
That is one of the first results I found and it is probably a great resource if you want to dive into the topic, but it also lacks an image of the rectangular - or rhombic - grid on top of the hexagonal tiling which I think is visually much clearer than those interactive maps highlighting only the axes of the cell under the cursor. But I understand why they made the choice, other coordinate systems do not admit the same type of visualization while the interactive maps are universal in that sense.
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
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/
[1] https://adamsmith.as/papers/tog-wfc.pdf
[2] https://potassco.org/clingo/run/
(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.
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.
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.)
It feels a bit like the graphical equivalent of Markov chain text generation.
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...
[1] https://github.com/mxgmn/WaveFunctionCollapse
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.
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.
[0] https://catlikecoding.com/unity/tutorials/hex-map/
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...