People seem to go ga-ga over this algorithm with some frequency on HN, and I think it is only because of its in-name-only connection to quantum mechanics, because I have to say that as procedural generation algorithm I find it very lacking. It works on the cases I saw for something like a 10x10 grid decently enough but for any large-scale work it just produces endless seas of structureless repetition. Even the long-in-the-tooth "just fire Perlin noise at varying levels of detail at the problem" at least produces some overarching structure even if it is itself just random because the low-frequency, high-amplitude components you use will produce some sort of higher-level variation.
Literally anything with any hierarchy in it would be better, unless you're really leaning into that SCP-esque, liminal-space creepiness. But if that isn't your explicit goal I would definitely not recommend this for large-scale usage because in most projects that creepy liminal-space-ness is probably actively fighting your artistic goals.
It wouldn't even take that much; lay down some sort of street network with some other algorithm, a bit of "zoning" to switch some tile sets between "residential" and some other zone or even just a couple different types of "residental", perlin noise it up if you've got no better ideas, then use "wave function collapse" (I really dislike the in-name-only "quantumness" of the name, can hardly call the algorithm that with a straight face) to fill in the blocks. A straightforward implementation of that would still be pretty same-y but it would at least have some sort of structure.
I was working some time ago on a 4X with an hexagonal map (not only made of hex tiles, but the overall shape was an hexagon rather than a rectangle, no wrap-around).
Using a noise function alone does not let you choose how many landmass you want to generate.
Using "wave function collapse"/constraint solvers is too slow for large maps when the amount of constraints increase (please don't put a mountain in the middle of the ocean, or a snow tile in the middle of a desert). My implementation took almost 8h to generate a single map, and the result was not even good.
In the end, I used a combination of multiple techniques:
- voronoi to split the map into regions
- use a noise function to make the regions boundaries a bit more natural
- fill the map with water tiles, place randomly some island seeds
- grow the islands from their seeds using a cellular automata
- to create continents, simply put a lot of island seeds in the same area, to generate a bigger one
- place mountains or rifts on region boundaries to simulate "tectonic plates"
- generate a heat map (influenced by position of the north/south poles and equator of the map), a humidity map (influenced by leftover ocean tiles), a height map (which is influenced by the already placed mountains/rifts) using a noise function
- using the previous heat/humidity/height maps, generate a wind map
- using the wind map, modify the humidity map (wind carries humidity over the land)
Then, choose randomly some tiles that fit some criteria to place biomes:
- desert on hot/dry land
- forest on temperate land
- swamp on temperate/wet land
- jungle on hot/wet land
- ...
Then a bunch of different cellular automata to grow the biomes naturally.
The result was quite nice, but it still wasn't on par to the map gen in Civilization games. I still want to continue this project, but I think in my heart I gave up.
EDIT: Some formatting because i always forget HN does not support markdown lists
I first came across Amit's page in middle school 20 years ago, and studied it religiously until I built a hexagonal grid with A* in Game Maker (which taught me programming from the ground up by studying Mark Overmars' amazing manual).
Today I'm directing an indie game with a team of 10 under me.
The code is not opensource but I've written a few articles about it:
- Part 1: https://david-delassus.medium.com/procedural-map-generation-in-c-part-1-the-slow-the-bad-and-the-ugly-4445fb15e43a?sk=2ff2c19dc5fe4c706092e83c79c72f56 (perlin noise, then wfc = fail)
- Part 2: https://david-delassus.medium.com/procedural-map-generation-in-c-part-2-a-new-hope-with-cellular-automata-and-gpt4-6b3b52c6b357?sk=96ab3bb234c28d9f5dc2dca8f2f19f97 (cellular automata, and let's try to use GPT to write the code = GPT is nice, but not perfect I had to refactor the code a lot)
- My own noise function: https://david-delassus.medium.com/i-made-my-own-noise-function-9e6ce4b95a9c?sk=26c5bdd7687445016216cc0b7cb10fa7
NB: Yes it's on medium, my bad :p The `sk` token in the URL is the friend link to bypass the paywall.
I think people went gaga over it due to the sample generations on the original repository (and the simplicity of implementation for arbitrary bitmaps), not so much the name.
https://github.com/mxgmn/WaveFunctionCollapse
As for global repetition, the original repo did have this to say, that selecting tiles is important.
"Note that the unrestrained knot tileset (with all 5 tiles being allowed) is not interesting for WFC, because you can't run into a situation where you can't place a tile. We call tilesets with this property "easy". Without special heuristics easy tilesets don't produce interesting global arrangements, because correlations of tiles in easy tilesets quickly fall off with a distance. "
> I have to say that as procedural generation algorithm I find it very lacking.
Per-pixel 2D generation like what's used in Caves of Qud produces stranger results which I like.
> I really dislike the in-name-only "quantumness" of the name, can hardly call the algorithm that with a straight face
It caught on because it portrays an air of sophistication (read: sophistry). There are no wave functions, it's a sudoku solver. I would also argue "sudoku solver" better conveys the underlying mechanics.
> I would also argue "sudoku solver" better conveys the underlying mechanics.
It really does. I glanced over the WFC algorithm and didn't really get it, but reading your comment that it's a "sudoku solver" helped click things into place in my head.
Speaking for myself I can't say I remember "going ga ga" as such, but I was certainly intrigued when I first discovered it because it produces cool results with a form of machine learning that is under-utilised, based on combinatorial optimisation (at least the initial version as far as I remember extracts constraints automatically from an image, so it learns a model of how parts of the image can combine).
The "wave function collapse" name is ... a little grandiloquent, to be fair.
I personally haven't used it for procedural generation and I don't expect to but it has been used in at least two games I know of: Townscaper and Bad North. Combinatorial optimisation is not cheap but if it's good enough to generate game levels for simple games then it's not that bad.
(Bad North does take a bit of time to generate a level, to be fair).
Ha ha, great comment! You're right, WFC's name just refers to quantum mechanics because it sounds cool, not because the algorithm has anything to do with physics, waves, or collapsing functions (it's more just a constraint based Sudoko solver). But I perceive it more as a playful buzzword for a useful algorithm, and not as maliciously deceptive like Deepak Chopra, who I was just commenting on recently (Quantum was cool until Deepak Chopra ruined it for everybody):
I do think it's useful combined with other techniques like procedural programming, cellular automata, Voronoi diagrams / jump flooding, noise, etc, to steer the higher and lower level structures. Check out Maxim Gumin's work on Markov Junior!
I think the really nice property of WFC is that it's very naturally and easily artist-driven. It doesn't require programming skills to use, you just supply it with a bunch of concrete before and after examples. (Like "Programming by Example".) That makes it much easier for a wide range of people to use, which is an important feature for democratizing custom world generation. Especially when you can construct or discover the examples in-world, and have it operate kind of like a 2-d tile or 3-d cube auto-complete, that looks at the rest of the stuff you've built or seen, like Canvas does with 1-d code.
Literally anything with any hierarchy in it would be better, unless you're really leaning into that SCP-esque, liminal-space creepiness. But if that isn't your explicit goal I would definitely not recommend this for large-scale usage because in most projects that creepy liminal-space-ness is probably actively fighting your artistic goals.
It wouldn't even take that much; lay down some sort of street network with some other algorithm, a bit of "zoning" to switch some tile sets between "residential" and some other zone or even just a couple different types of "residental", perlin noise it up if you've got no better ideas, then use "wave function collapse" (I really dislike the in-name-only "quantumness" of the name, can hardly call the algorithm that with a straight face) to fill in the blocks. A straightforward implementation of that would still be pretty same-y but it would at least have some sort of structure.