17 Jul 2017

Table of Contents

Note: the /x/ series of posts on my site are mostly unpolished mini posts. I’m trying out a few different ideas for procedural map generation; this is one of them.

In my previous blog post I experimented with elevation based on river drainage basins. It was cool, but it didn’t match what we needed for our game, so I stepped back a bit and decided to work on something else. We want the game/level designer to have some control over mountains, coastlines, and rivers. The designer should be able to draw a rough sketch, and then the procedural generator will fill in the rest. We’re intentionally making unrealistic terrain (likely something low-poly and cartoony), but that’s something for a future blog post. This week’s experiment is about designer control of mountains and coastlines.

Draw mountain ridges or coastlines:

Noise:

Things to try:

The implementation is surprisingly simple.

#Distance fields

I had tried several approaches, including medial axis, before I found something I like quite a lot. The idea is to use distance fields. For each point on the mesh, calculate the (graph) distance from a set of seed points. Here are the three distance fields for the map you drew above:

A = Mountains
B = Boundary
C = Coastline

The land and water were spilling over the coastlines. To fix that, I made the distance fields for the boundary and mountains not cross the coastline.

Distance fields are easy to calculate on a graph, using breadth first search (around 20 lines of code).

#Combining distance fields

Given A = distance-from-mountain and B = distance-from-boundary, how should I combine them? My first thought was to interpolate the nearest constraint points. Between +1 and 0 I would interpolate linearly. But I draw an enclosed “O” shape for mountains, the interpolation would be between 1 and 1, and it’d end up as a plateau. I’d prefer it to be a crater. So I searched for some useful interpolation functions.

I discovered that B/(A+B) works really well! Near the mountain ridges, A is small, so B/(A+B) is close to B/B = 1. Near the boundary, B is small, so B/(A+B) is close to 0/A = 0. In between, it interpolates.

It’s scale-free: if I replace distances by ten times the distance, I get the same answer. This is an important property. Without it, I have much lower confidence in the results.

2.1Pairwise combination#

The mountains and boundary aren’t enough. I wanted to be able to draw a coastline C as well. I extended the two-point interpolation:

  • If C is furthest away, use the previous interpolation with only A and B but modify it for -1 (boundary) to +1 (mountains): 2*B/(A+B)-1
  • If B is furthest away, interpolate between coastline (0) and mountains (+1): C/(A+C)
  • If A is furthest away, interpolate between coastline (0) and boundary (-1): B/(B+C)-1

There are sometimes weird effects with partially drawn coastlines. The boundary–mountain interpolation doesn’t always match up with the boundary–coastline + coastline–mountain interpolations. The problem is that any time I introduce if-then into the equation, there’s a potential for discontinuity. Are there other functions that don’t lead to discontinuities?

2.2Harmonic mean#

I looked at the weighted geometric mean and the weighted harmonic mean. The weighted geometric mean would return positive elevations only, so it’s not useful here. The weighted harmonic mean though looks nice. For two values with elevation 0.0 and 1.0, it becomes B/(A+B), which is exactly what I had started with. For three values:

(+1 * 1/A + 0 * 1/C + -1 * 1/B) / (1/A + 1/C + 1/B)

  • If there’s no coastline, C is infinity, so 1/C is 0, and this becomes (1/A-1/B)/(1/A+1/B) which turns out to be equivalent to the previous rule of 2*B/(A+B)-1.
  • If the land is surrounded by coastline, in the interior B is infinity, so 1/B is 0, and this becomes (1/A)/(1/A+1/C) which turns out to be equivalent to the previous rule of C/(A+C).
  • If the land is surrounded by coastline, in the exterior A is infinity, so 1/A is 0, and this becomes (-1/B)/(1/C+1/B) which turns out to be equivalent to the previous rule of B/(B+C)-1.

Hey, that’s pretty cool — when there’s no coastline or a complete coastline, it is the same as my previous set of rules! Where it differs is when there’s a partial coastline. I had discontinuities with partial coastlines, but the harmonic mean eliminates all the discontinuities. It’s less code too. Nice!

2.3Weighting functions#

With harmonic means, there’s also the potential to use different weighting other than linear: (+1 * 1/Aⁿ + 0 * 1/Cⁿ + -1 * 1/Bⁿ) / (1/Aⁿ + 1/Cⁿ + 1/Bⁿ).

Linear: n=1Square: n=2Square root: n=sqrt(2)

For the demo on this page I chose harmonic means with sqrt weighting. On land, it should produce more valleys and sharper mountain peaks. In the water, it should produce more shallow water and occasional deep water trenches.

However it doesn’t actually produce that effect for the three-valued harmonic mean. :-( The sqrt weighting puts a lot more of the values in the middle, which is 0 for the -1:+1 range. That’s what I want — a lot of values near 0. But for the three-valued harmonic mean, it’s separately putting a lot of values in the middle of the -1:0 range (lots of -0.5) and the 0:+1 range (lots of +0.5). So it’s a cute trick but it has issues.

#Features

3.1Noise#

One of our goals is to let the designer specify constraints, but then fill in the unconstrained areas procedurally. I tried a little bit of here with elevation. I mixed in simplex noise for unconstrained areas. Try going to the demo at the top and changing the noise slider.

I’m not happy with the results though. It may need higher resolution maps to make it work well.

3.2Resolution#

The lines drawn by the designer are stored as vectors, so it should be possible to apply those same vectors to a more detailed mesh to get similar landscapes. The idea would be to use the low resolution mesh to give interactive speeds for the designer to explore possibilities, then apply a high resolution mesh for the final terrain. However I haven’t implemented this yet.

3.3Non-islands#

In this demo I’ve constrained map boundaries to be deep water (field B), but the algorithm isn’t limited to island shapes. I can generate other types of maps by setting the boundary conditions to include both land and water. Try drawing mountains over the edges of the map.

3.4Different elevation constraints#

Right now the algorithm only works with mountain, boundary, coastline constraints. It would be useful to be able to set any elevation instead of only +1. The algorithm does not support that, and I’m not sure what to do about it.

There are papers listed at the end that do support more complex constraints, not only arbitrary elevations, but also constraints on slopes and second derivatives. There are some pretty cool effects from these types of constraints, but the algorithms to set elevations is much more complicated than what I wanted to implement.

#More

There are other projects that have done far more advanced things than what I’m doing here. Take a look at these:

I’m looking for the simplest thing that could work for our project’s needs. Our maps will be low-poly cartoonish, so realism is not the goal. Previous blog posts in this series:

My current plan is to use the method on this page to generate coarse elevation. I’ll then use the algorithms I developed in the previous blog posts: coarse elevation to generate rivers, then both coarse elevation and rivers to generate detailed elevation. The level designer will sketch out some ideas and the system will procedurally generate a landscape that matches the designer’s input.