Polygon map generation, part 2

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.

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:

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:

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:

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:

Elevation	Moisture
	Wet					Dry
High	Snow			Tundra	Bare rock	Scorched
Medium-high	Taiga		Shrubland		Temperate desert
Medium-low	Temperate rain forest	Temperate deciduous forest		Grassland		Temperate desert
Low	Tropical rain forest		Tropical seasonal forest		Grassland	Subtropical desert

Here's the result:

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

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.