Procedural map generation on a sphere

22 Oct 2018

ProcJam 2018^[1] inspired me to learn how to generate maps on a sphere. The opening weekend of ProcJam, I spent 11 hours on geometry, and wrote it up in a blog post:

place points on a sphere
work with sphere geometry
build a Delaunay triangulation on a sphere
build Voronoi regions on a sphere

After the weekend was over, I wasn’t able to spend as much time the rest of the week on this, and spent only 12 hours over the next 8 days working on:

assign elevation on the sphere
assign moisture/rainfall on the sphere
assign temperature on the sphere
create rivers on the sphere
render mountains, valleys, oceans, rivers on the sphere

In my projects I either limit my scope or limit my time. The big writeups (A*, Hexagons, etc.) are usually based on some scope. This on the other hand was a one-week experiment (/x/ in the URL). I wanted to learn as much as I could during one week. I learned a lot, and there’s plenty more to do, so maybe I’ll tackle more another time.

1 Jitter#

In part 1 I spent some time picking evenly distributed points on a sphere. Once I started working on the maps, the first thing I noticed is that all the time I spent finding evenly distributed points was wasted. Evenly distributed points look boring!

^[2]

I ended up adding random jitter to the points to make them look interesting.

^[3]

2 Noise heightmap#

I often start with noise for heightmaps^[4]. In this case, 3D Simplex Noise gives me an elevation for every point on the sphere. It was reasonable but it didn’t look interesting to me.

^[5]

I decided to look for alternatives.

3 Tectonic plates#

I decided to follow the approach of Andy Gainey and others (see references at the end) and build some tectonic plates. As this was a quick experiment, I wanted to find the simplest thing that could possibly work.

First, pick random tectonic plate locations. I have numRegions Voronoi regions, and picked random regions until I had N of them. Through experimentation I found that setting N between 10 and 50 seemed reasonable.

let chosen_r = new Set();
while (chosen_r.size < N) {
    chosen_r.add(randInt(numRegions));
}

Once I had these plates, I ran flood fill (breadth first search) from them to assign each Voronoi region to a plate:

^[6]

The boundaries were a bit smooth so I changed this to a random fill algorithm. It’s similar to breadth first search but instead of picking the first element (breadth first search) or last element (depth first search), I pick a random element to expand. This code probably won’t make sense out of context but this will give you an idea of how much code is needed to assign the tectonic plates with a random fill:

// plate_r is a set of region ids representing plates
let r_plate = new Int32Array(mesh.numRegions); // region->plate
r_plate.fill(-1);
let queue = Array.from(plate_r);
for (let r of queue) { r_plate[r] = r; }
let out_r = [];
const randInt = makeRandInt(SEED);
for (let queue_out = 0; queue_out < mesh.numRegions; queue_out++) {
    let pos = queue_out + randInt(queue.length - queue_out);
    let current_r = queue[pos];
    queue[pos] = queue[queue_out]; // random swap of queue elements
    mesh.r_circulate_r(out_r, current_r); // neighboring regions
    for (let neighbor_r of out_r) {
        if (r_plate[neighbor_r] === -1) {
            r_plate[neighbor_r] = r_plate[current_r];
            queue.push(neighbor_r);
        }
    }
}

The random fill made the boundaries a little better:

^[7]

Once I had some tectonic plates, I randomly assigned elevation+moisture to each one:

^[8]

With more regions and more plates it still looks reasonable:

^[9]

4 Plate movement#

The next step was to assign elevation within a plate. I assigned random direction vectors to each tectonic plate. This is simpler than what other people did, but I thought it’d be the simplest thing that would produce useful output.

^[10]

another example:

^[11]

Then along the boundaries of the plates, I compared the direction vectors. If the plate movement would cause the adjacent regions to move closer, then I applied a different rule than if they were stationary or moving apart:

Boundary type	distance decreased	distance increased
land + land	mountain	coastline
land + ocean	mountain	ocean
ocean + ocean	coastline	ocean

This assigns elevation to the boundary regions only. For the rest of the regions, I interpolated using three distance fields, as I described on this blog post^[12] (2017).

It didn’t work so well. I think the problem was that any slight movement will trigger full mountain growth, and that means every plate ends up with a land boundary:

^[13]

I tweaked the rules and ended up with a threshold for how the regions are pushing into each other before I trigger mountain growth:

Boundary type	Δdistance < -0.75	otherwise
land + land	mountain	do nothing
land + ocean	mountain	coastline
ocean + ocean	coastline	ocean

(Note: the 0.75 is arbitrary, and I’d like to figure out what values work best.) It looks much better. Notice the mountains forming at plate boundaries:

^[14]

A further tweak helped some more: set the center of each plate to either ocean or coastline before calculating the distance field.

This needs more work, as I’m still mildly unhappy with the results. Since this was a 1 week experiment, I decided I should work on other things, and come back to this if I had time.

Update [2022] It turns out my code for this is buggy, and that’s probably why I had poor results. Unfortunately, the rest of the parameters in the generator are tuned based on the buggy code, so fixing this is not as easy as fixing the bugs.

5 Plate size#

By varying the number of plates, I could have larger or smaller land masses:

^[15]^[16]^[17]^[18]

6 Biomes#

A nice way to assign moisture/rainfall/humidity on a planet is to use atmospheric simulation^[19], but I had spent a lot more time than expected on elevation and was running out of time for other things, so I decided to do the simplest thing that could possibly work: I assigned random moisture to each continental plate, and used that to look up biomes.

7 Rendering#

For mapgen4 I have a nice renderer with outlines^[20] and a custom projection^[21]. None of that worked on the sphere, so I had to go back to basics, including fighting bugs:

^[22]

I implemented something similar to what I described in this blog post^[23] but I don’t like the way it renders mountains. It’s something I need to revisit.

^[24]

I don’t think I would’ve attempted this without regl.js^[25], which wraps all the annoying parts of WebGL while leaving all low level details that matter (memory management, shaders, textures, etc.) to me.

8 Rivers#

Rivers are usually the hardest part but I already had river code for mapgen4^[26], and it worked on graphs not grids. The sphere map is a graph and the river code didn’t require any changes to work on spheres. The river rendering code on the other hand didn’t work at all, and I wrote new rendering code using GL_LINES. Unfortunately in WebGL you can’t use different line widths, so my first version looked like this:

^[27]^[28]

What did work: I got more rivers in wet areas than in dry areas.

Instead of line widths, I used alpha transparency to simulate narrower rivers:

^[29]

There’s a visual glitch where the rivers run into the oceans. I wanted to solve this properly, but as this was a quick experiment, I decided the simplest workaround would be to make the rivers the same color as shallow water, so where they flowed into the ocean, you wouldn’t see the overdraw. I think it ended up looking pretty good. I only drew the bigger rivers here:

^[30]^[31]

and I drew many more rivers here:

^[32]^[33]

I’m pretty happy with the way rivers look!

There’s a small problem where a tiny “ocean” region can get rivers flowing into it. I considered filtering these out, but as this is a time-limited project, that didn’t make the cut.

Another useful trick to compensate for the behavior of GL_LINES: on the sides of the planet, where you wouldn’t see the rivers top-down, decrease transparency.

9 Demo#

Time for an interactive demo! It may be slow when you increase the number of regions. Try switching from flat to quad drawing to get some shading.

Draw:
Plate vectorsPlate boundaries
Number of regions:
Number of plates:
Jitter:
Sphere rotation:

10 More reading#

There’s so much I didn’t have time to implement. Mountains don’t look right. Temperatures should decrease near the poles. The shading is too flat. There are no trees. Rivers should be drawn with variable width. Plate elevation interpolation doesn’t always work right. When you increase the number of plates, it seems to produce too many oceans. Lots and lots of things to improve, but I don’t want to keep working on it right now. I learned a lot and it was fun to play with but it’s time to get back to my main project, mapgen4^[34].

I put the messy code up on github^[35].

Further reading for plate tectonics and region partitioning systems: