In the previous blog post I described creating polygon island maps. Given random points, Voronoi diagrams with Lloyd relaxation produce a nice set of polygons. The polygons, their edges, and their corners can be represented as two related graphs. Given a random shape, those polygons can be marked as land, ocean, or lake. In this blog post I'll describe how to add elevation, rivers, moisture, and biomes to make the maps interesting.

The full article is here. There's also a demo and source code.

Elevation

The most realistic approach would have been to define elevation first, and then define the coastline to be where the elevation reaches sea level. Instead, I'm starting with the goal, which is a good coastline, and working backwards from there. I set elevation to be the distance from the coast. I originally tried elevations at polygon centers but setting elevations at corners worked out better. Corner-to-corner edges can serve as ridges and valleys. After calculating the elevation of corners, the polygon elevation is the average of the elevation at the corners.

Water polygons don't count towards the distance. This is both because I expect lakes to be flat instead of sloped, and because this tends to build valleys around lakes, which helps guide rivers towards lakes.

Elevation map

One problem with the simple definition is that some islands have too many mountains and others have too few. To fix this, I redistribute the elevations to match a desired distribution, which has more low elevation land (coastline) than high elevation land (mountains).

Elevations always increase from the coast to the mountains. That means that for any location, going downhill will eventually lead to the ocean. This diagram shows the steepest downhill direction from every corner:

Elevation map with arrows pointing downhill

By following the downhill arrows from any location, we eventually reach the ocean. This will be useful for rivers but may also be useful for calculating watersheds and other features.

I had two main goals for elevation:

  1. Biome types: high elevations get snow, rock, tundra; medium elevations get shrubs, deserts, forests, and grassland; low elevations get rain forests, grassland, and beaches.
  2. Rivers flow from high elevations down to the coast. Having elevations that always increase away from the coast means that there's no local minima that complicate river generation.

In addition, games may define their own use of elevation data. For example, Realm of the Mad God uses elevation to distribute monsters.

Rivers

Rivers and lakes are the two fresh water features I wanted. The most realistic approach would be to define moisture with wind, clouds, humidity, and rainfall, and then define the rivers and lakes based on where it rains. Instead, I'm starting with the goal, which is good rivers, and working backwards from there.

The island shape determines which areas are water and which are land. Lakes are water polygons that aren't oceans.

Rivers use the downhill directions shown earlier. I choose random corner locations in the mountains, and then follow a path down to the ocean. The rivers flow from corner to corner:

Elevation map with one river

I tried both polygon centers and corners, but found that the corner graph made for much nicer looking rivers. Also, by keeping lakes flat, elevation tends to be lower near lakes, so rivers naturally flow into and out of lakes. Multiple rivers can share the lower portion of their path, but once they join, they never diverge, so tributary formation comes for free. It's simple and seems to work pretty well.

Moisture

Since I'm working backwards, I don't need moisture to form rivers. However, moisture would be useful for defining biomes (deserts, swamps, forests, etc.). Since rivers and lakes should form in areas with high moisture, I defined moisture based on distance from fresh water:

Moisture map

As with elevation, I redistribute moisture to match a desired distribution. In this case, I want roughly equal numbers of dry and wet regions. In this map generator, moisture is only used for biomes. However, games may find other uses for the moisture data. For example, Realm of the Mad God uses moisture and elevation to distribute vegetation.

Biomes

Together, elevation and moisture provide a good amount of variety to define biome types. I use elevation as a proxy for temperature. Biomes first depend on whether it's water or land:

  • Ocean is any water polygon connected to the map border
  • Lake is any water polygon not connected to the map border
    • Ice lake if the lake is at high elevation (low temperature)
    • Marsh if it's at low elevation
  • Beach is any land polygon next to an ocean

For all land polygons, I started with the Whittaker diagram and adapted it to my needs:

ElevationMoisture
WetDry
HighSnowTundraBare rockScorched
Medium-highTaigaShrublandTemperate desert
Medium-lowTemperate rain forestTemperate deciduous forestGrasslandTemperate desert
LowTropical rain forestTropical seasonal forestGrasslandSubtropical desert

Here's the result:

Biome map

These biomes look good in the map generation demo, but each game will have its own needs. Realm of the Mad God for example ignores these biomes and uses its own (based on elevation and moisture).

In the last blog post I'll describe how I get from this biome map to maps like this: (or even this!)

Goal of the map generation

Update: [2010-09-22] I replaced the last diagram on this page with what I originally wanted but didn't finish in time for the blog post. At the time of posting, I used this image instead.

Labels: , ,

6 comments:

felix wrote at September 06, 2010 12:34 AM

Wow! Fantastic use of Voronoi diagrams. For some reason I prefer the 2nd to last hexagonal shapes over the last more detailed image. Maybe because it looks like a cool boardgame.

Emile wrote at September 06, 2010 1:49 AM

It looks like you switched the axis for moisture - I'm pretty sure deserts don't count as "high moisture" :)

Interesting stuff! I used something like your whittaker diagram for world generation, except that I had a third dimension, temperature.

Amit wrote at September 06, 2010 7:51 AM

Hi Felix — yes, I think the polygons could be very useful for many games, especially when the polygons are directly used by the player, such as in a settlement or territory conquest game. The board game “Risk” is drawn with fancy borders but at its heart is a graph based game, where you can move only from node to node along specific borders. My goal for the next blog post is to have some fancy borders, but still keep the polygon map underneath. In games where the polygons matter, you'd want to draw the borders, as in this image.

Amit wrote at September 06, 2010 8:17 AM

Hi Emile — yes, good catch! Thank you; I have corrected the table.

Temperature, wind, humidity, variable intensity rain, vegetation, rain shadows, flooding, erosion, evaporation, aquifers, soil dampness, soil permeability might all be useful for maps. I played with some of these in previous map projects and decided this time I'm going to keep it simple. :)

BTW there's an absolutely fantastic map generation blog that you may enjoy reading: Dungeon League. They're generating much more sophisticated maps than I am in this project. Also see this discussion on TIGsource about the Dungeon League maps.

Arnaud Couturier (piiichan) wrote at September 18, 2010 1:27 AM

Hey Amit,
very interesting post.

I want to learn more about how you control distribution of features.

For example you said:
"As with elevation, I redistribute moisture to match a desired distribution."

How do you do that?

Thanks

Amit wrote at September 18, 2010 7:57 PM

Hi Piiichan, I did something very simple with moisture: I sorted the corners by moisture, then reassigned the moistures to be from 0.0 to 1.0, evenly. For example if there are 200 corners, then corner i will get moisture i/200. See the redistributeMoisture function in the source.