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.