Procedural elevation

4 Jul 2017

Note: the /x/ series of posts on my site are mostly unpolished mini posts. The polished version of this will come later, maybe in a few months.

In my polygon map generator from 2010^[1] I built the mountains based on the coastline, then made rivers flow down from the mountaintops. Three weeks ago I grew rivers up from the coastlines; two weeks ago I marked mountains and valleys from the river basin data. My next goal was to build mountains that matched the generated rivers.

I failed. But I got some cool images, and I learned some useful things.

Elevation#

I need to figure out:

how to assign the elevations to blue points given the river drainage system
how to ensure elevations on both sides of a mountain range are consistent
how to assign elevations to red points given the blue points

Algorithm 1

This is the algorithm from the last blog post. Grow elevation upwards using some heuristic involving Strahler numbers.

Looks cool! But ... the ridges don’t match. Where two watersheds meet, the elevations were computed separately, and there’s nothing that makes them match up. This leads to lots of cliffs:

I tweaked this in different ways but fundamentally, there’s nothing that would make the ridges match up. Assigning elevation from the river mouths didn’t work so well. The cliffs were cool but they were accidental. If I make cliffs, I want them to be on purpose.

I spent some time reading papers (see list at the end of the page). There were some great ideas in there but my needs are simpler than what most of them covered. I’m looking for something simple (less than 50 lines of code) and runs in linear time. I know, that’s asking for a lot, but I don’t need realism, only consistency. So I decided to try to construct the simplest the simplest thing that could possibly work^[2], inspired by what I learned from those papers.

Algorithm 2

I struggled with this, trying several different algorithms on paper, before I decided that maybe I should stop fighting the problem and embrace it instead. I had been trying to determine elevations purely from the river drainage basins, but I had built those drainage basins from something somewhat like elevation. Can I reuse that pseudo-elevation to guide the final elevation?

Output elevation cannot exceeed the input pseudo-elevation.
Output elevation must be below the inflowing triangles’ elevations.

That still leaves some leeway in how I set the elevations. If I evenly distribute them across the length of the river I get this:

The problem with this is that it’s carving canyons into the valleys, and I want the carving to be in the mountains. I tried weighting the step sizes to see if I could fix this:

It was interesting to play with but it didn’t really help. I think the real problem is that if there are two tributaries that have different lengths, the assignment of elevation doesn’t match at the confluence, leading to a sudden drop:

Algorithm 1 made confluences match but ridges did not. Algorithm 2 made ridges match but confluences did not. I should combine these somehow.

Algorithm 3

The most straightforward approach is to mix the outputs:

This looks fine in the top-down view but it doesn’t actually solve any of the problems. It makes both ridges and confluences mismatch.

Algorithm 4

To make both ridges and confluences match, I started with algorithm 2, which makes ridges match. Then I looked for the sudden drops at confluences that made them not match:

I then spread the drop out over the length of the river upstream:

This makes confluences match up. It keeps ridges matched. Does it do what I want?

Kind of. It does make the mountains interesting. But it doesn’t flatten out the valleys.

Diagnosis

This was frustrating. I thought I had figured it out, but when I tried it, it didn’t work well. So I took a break for a few days and realized a few things:

The success of my 2010 polygon map generator project was in large part because I did not tweak the results an algorithm gave me, but instead I designed an algorithm that would construct the kinds of maps I wanted. But for this project I have ended up tweaking and tweaking. This “generate and test” approach is frustrating, and I should pause and figure out what my goals are.
Even if I do need to tweak sometimes to find good parameters, the iteration is too slow. Although I took care to make the generation code fast, I have some fairly inefficient rendering code that’s keeping me from exploring more quickly. I’m also editing code and reloading the page, when I should be building a slider UI that lets me adjust parameters directly. I also should have debug information displayed as an overlay.
Part of the poor results are because I grabbed the placeholder pseudo-elevation I implemented for rivers, and used it for elevation. The problem is the pseudo-elevation was only meant for river drainage basins, and doesn’t actually have good mountains and valleys.

As a quick experiment I tried putting in some better pseudo-elevation, and I got this much improved result:

I think I need to make the implementation fast enough to allow more experimentation, but I also need to think about what I actually want the algorithm to produce, and design an algorithm that produces that more directly.

Rendering#

On a separate note, I wanted to write about rendering.

The way I’m generating rivers, I assign an elevation to each blue point. To render them, I drew the triangles using the red points. I made the red points the average values of the blue points. But this isn’t the structure I really want. I want the red points to be above the blue points, like this (side view):

By setting red points to be the average of the blue points, I was missing the peaks and valleys.

And by only drawing the red points I was losing even more detail:

And if it wasn’t bad enough, the normals for each of these triangles was almost always facing the same direction (up), which meant that the lighting didn’t help illuminate the terrain much at all, except for large features.

And to top it off, I was using per-vertex normals, which average out the per-face normals, reducing detail even further.

I hadn’t really been thinking about the rendering properly two weeks ago. I thought “hey, there’s not enough detail … let me increase the number of triangles!” I pushed the number of triangles up from 12.5k to 1.25M to get some detail. Although some of the terrain looked cool, it was at the same time too bland and smooth. With 1M pixels and 1.25M triangles I was wasting my triangles. I should be able to get a lot more detail with far fewer triangles.

Time to think this through…

What I need to do is draw triangles with both the red and blue points. And that means I need to subdivide these big triangles into smaller ones (top view):

How should I divide them? Instead of focusing on how to divide the black-edged triangles, I focused on the quadrilateral formed by the crossing of the black and white edges:

There are two ways to divide this space into triangles. Either I can fold the quad down on the black edge (keep in mind the blue points are lower than the red points, so this is a ridge):

Or I can fold the quad up on the the white edge (the blue points are lower than the red points, so this is a valley):

Some of you may have run into this problem before when trying to decide how to draw quads. Which way should I fold? For this problem, I actually want both! I want to use the black edge when it’s a mountain ridge and the white edge when it’s a river valley. Either way, I need to generate two triangles for each full edge in the original dual mesh, which means one triangle per half edge. If I later add support for cliffs, I will need to generate four triangles for any cliffs that have waterfalls flowing over them.

To illustrate the difference, here’s the version with only the red points:

And here’s the version with subdivided triangles made of both blue and red points:

There’s a lot more detail! It’s the same procedurally generated map, but including both the blue and red points adds a lot of detail that previously was smoothed out.

Next steps

As I mentioned in the elevation section, I’m somewhat unhappy with where I’ve ended up. I’m doing a lot of tweaking and reloading. I’m going to step back and improve both aspects of this:

Less tweaking: figure out what I want as output, and design the algorithms to directly produce that
Faster iteration: optimize the rendering step, and add sliders to control all the parameters for map generation and rendering

The more detailed rendering is implemented but I haven’t switched to it yet. I want to figure out elevation first.

I had been pursuing the “wouldn’t it be cool?” approach of making elevation purely from rivers, but the reality is that the game designer will want to guide the elevation, so I should be designing an algorithm that uses the designer’s input (which I’ve been calling pseudo-elevation) to make the elevation.

If you want to play with what I have here, see this page. It’s a bit rough, as I had only written it for myself. And I’m not planning to use it, so I don’t plan to clean it up.