Polygon map generation, part 3

In the previous blog posts (part
1
and part
2),
I described generating random polygonal maps with elevation, moisture,
biomes, and rivers. For some games, those maps are
sufficient. However, in other games I want to hide the polygon
structure. In this blog post I'll describe how to render the polygons
into a game map that doesn't look polygonal, and conclude with the
demo and source code.

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

Noisy Edges

Recall from earlier that there are two graphs: one for Voronoi
corners (1, 2 in the diagram below) and edges (blue lines), and
one for polycon centers (A, B) and Delaunay edges (red
lines) between them:

I wanted to add some “noise” to the the straight lines. I tried making
them move randomly, but sometimes lines would cross, and I realized I
needed to constrain them so that they would never cross each other.
The second thing I wanted was to make sure that the lines had as much
space to wander as possible.

I realized that points A, 1, B, and 2 form a quadrilateral, and
I could constrain the wanderings of the line segment to that quadrilateral:

I further divided the quadrilateral into four quadrilaterals. Two were
usable for the red (Delaunay) edge and two for the blue (Voronoi)
edge. As long as the lines stayed within their allocated space and met
in the center, they'd never cross each other. That takes care of
constraining them.

The entire map can be divided up into these quadrilateral regions,
with no space left over:

That ensures that the noisy lines aren't constrained any more than
necessary. (I wonder if these quadrilaterals would be useful for game
mechanics.)

I can use any noisy line algorithm that fits within these
constraints. I decided to subdivide the quadrilaterals recursively and
stitch line segments together within the small quadrilaterals into a
complete edge. The result is here:

The noisiness is tunable, and I have examples at segment size
7, segment size 4, and
segment size 1. In the map demo I use segment
size 1 for rivers and coastlines, 3 where biomes meet, and 10
elsewhere.

More noise

I'm generally a fan of noise in game
art, and
wanted to add a little bit of noise to these maps as well. In a real
game map the noise might reflect vegetation or small variations in
terrain. In the demo I just filled the screen with a random noise
texture, and smoothed the colors between adjacent polygons:

However, with a bit more random noise, we can generate this (described in the full article):

Here's a rendering with 16,000 polygons, noisy edges, a noise texture
overlay, and simple lighting:

Demo

I wrote a Flash demo to explore the generated maps:

The simplest way to explore the maps is to click Random and the
various View options.

Try the demo!

In a shape number like 85882-3, 85882 chooses the overall island
shape and 3 is the random number seed for the details (random points,
noisy edges, rivers, lava). You can type in a shape number and press
Return to generate that map. The demo also shows some unfinished
features that may be useful for some games: lava, roads, and
watersheds.

Source

I've placed the Actionscript source under the MIT license; it's
available on github. There's an
overview
page
describing what's in these blog posts, along with notes about the
code. I don't expect that the code will be immediately useful to
anyone, but it might be a useful starting point if you'd like to use
these techniques for making your own game maps. The diagrams are
built with 300 polygons, the demo uses 2000, and the code can go much
higher, although I've not tried above 16,000.

If you find the ideas or code useful, I'd love to hear about it!

Update: [2010-09-22] I added a noisier rendering, which is described in the full article.

Read More

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.

Read More

Polygon map generation, part 1

I wanted to generate interesting game maps that weren't constrained to
be realistic, and I wanted to try some techniques I hadn't tried
before. I usually make tile maps but this time I decided to make
polygonal maps. Instead of 1,000,000 tiles, what could I do with 1,000
polygons? I think the distinct player-recognizable areas might be
useful for gameplay: locations of towns, places to quest, territory to
conquer or settle, pathfinding waypoints, difficulty zones, etc.

There were three main things I wanted: good coastlines, mountains and
rivers. For the coastline, I wanted to make island/continent maps that
are surrounded by ocean, so that I don't have to deal with people
walking to the edge of the map. For the mountains, I started with
something simple: mountains are whatever's farthest from the
coastline. For the rivers, I started with something simple: draw
rivers from the coast to the mountains.

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

Polygons

The first step is to generate some polygons. I picked random points
and generated Voronoi
polygons, which are
used for lots of
things,
including maps. Here's an example of random dots (red) and the
polygons that result:

The first problem is that polygon shapes and sizes are a bit irregular. Random numbers are
more “clumpy” than what people expect. What I really want is
semi-random “blue noise”, not random points. I approximate that by
using Lloyd
relaxation, which is
a fairly simple tweak to the random point locations to make them more
evenly distributed. Here's the result after running Lloyd relaxation twice:

Compare it to running once or href="http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/voronoi-50-lloyd.png">fifty times. The more iterations, the
more regular the polygons get. Running it twice gives me good results
but every game will vary in its needs.

[2010-09-22] The second problem with the polygons is that some edges are very short. For games where boundaries between polygons matters, having short edges is a problem. We can adjust the edge lengths by moving corners, but we lose the Voronoi properties. Since I'm using Voronoi only to generate polygons, and do not need to preserve the Voronoi properties, I move the corners to the average of the polygon centers they touch. Note: I added this code after the initial blog post, and did not update diagrams to show this step.

Map Representation

I'm representing the map as two related
graphs: nodes and
edges. The first graph has nodes for each polygon and edges between
adjacent polygons. It represents the Delaunay
triangulation,
which is useful for anything involving adjacency (such as
pathfinding). The second graph has nodes for each polygon corner and
edges between corners. It contains the shapes of the Voronoi
polygons. It's useful for anything involving the shapes (such as
rendering borders).

The two graphs are related. Every triangle in the Delaunay
triangulation corresponds to a polygon corner in the Voronoi
diagram. Every polygon in the Voronoi diagram corresponds to a corner
of a Delaunay triangle. Every edge in the Delaunay graph corresponds
to an edge in the Voronoi graph. You can see this in the following
diagram:

Polygon A and B are adjacent to each other, so there is a (red) edge
between A and B in the adjacency graph. For them to be adjacent there
must be a polygon edge between them. The (blue) polygon edge connects
corners 1 and 2 in the Voronoi shape graph. Every edge in the
adjacency graph corresponds to exactly one edge in the shape graph.

In the Delaunay triangulation, triangle A-B-C connects the three
polygons, and can be represented by corner 2. Thus, corners in the
Delaunay triangulation are polygons in the Voronoi diagram, and vice
versa. Here's a larger example showing the relationship, with Voronoi
polygon centers in red and corners in blue, and the Voronoi edges in
white and the Delaunay triangulation in black:

This duality means that I can represent the two graphs together.
Edges are the key. Each edge in a normal graph points to two
nodes. Instead of representing two edges in the two graph separately,
I made edges point to four nodes: two polygon centers and two
corners. It turns out to be quite useful to connect the two graphs
together.

With the combined representation, I can now use the Relationships
Between Grid Parts sections of my article on
grids. They're
not grids so I'm not assigning grid coordinates, but many of the
algorithms that work on grids also work here, and the algorithms that
work on graphs also work here (on either of the two graphs).

Islands

The second step is to draw the coastline. I used a simple function to
divide the world into land and water. There are many different ways to
do this. You can even draw your own shapes, e.g., a skull island. The
map generator works with any division of points, but it forces the
outer layer of polygons to be ocean. Here's an example that divides
the world into land and water:

A simple flood fill starting from the border of the map can determine
which water areas are oceans (connected to the border) and lakes
(surrounded by land):

In the next two blog posts (part 2, part 3) I'll describe how I add elevation data to
build mountains and valleys, add moisture data for lakes and
rivers, render the map so that it doesn't look polygonal, and conclude with the demo and source code. Together, elevation and moisture produce a good range of
terrain and map features. The goal is to produce maps like this:

Update: [2010-09-22] Since the original blog post, I added a corner adjustment step to lengthen short edges. Just as Lloyd relaxation improves the polygon sizes, I needed to adjust the edge lengths. The adjustment does not preserve Voronoi properties, but I'm not using those properties so it worked out. I didn't update diagrams to reflect this change. I also improved map rendering and replaced the last diagram on this page. I originally wanted to have a rendering that didn't show the polygons at all, but couldn't get it to work in time, so at the time of the blog post I used this rendering instead. The rendering technique is described in the full article but not in the blog posts.

Read More