Hacker News Reader

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

> but it still wasn't on par to the map gen in Civilization games.

Which makes me wonder... do we know how map gen in Civilization works so well?

This is pretty cool! As someone with virtually no experience in this area I’d love to read the source code, is it open source?

A fantastic resource for this kind of generation is here:

http://www-cs-students.stanford.edu/~amitp/game-programming/...

This really brought me back.

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.

Thank you!

"You know, Hexagons are the Bestagons!"

https://www.youtube.com/watch?v=thOifuHs6eY

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

https://news.ycombinator.com/item?id=42714477

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!

https://twitter.com/ExUtumno/status/1531992699997507586

Maxim Gumin @ExUtumno: I published a new project about combining rewrite rules and solving constraint problems made of rewrite rules

https://github.com/mxgmn/MarkovJunior

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.