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.