3 Aug 2017

Table of Contents

{WIP- recreating the diagrams and algorithms from http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ in html5}

Back in 2010, I wrote an article about polygon map generation. I had wanted to make a map generator that did not use Perlin/Simplex noise for elevation, but instead was built by assigning properties to polygons in a mesh. Although the map generator was made for Realm of the Mad God, some of the algorithms are useful for other types of games too. In each section I’ll describe the rationale and variants.

This page is an update of the original page. I’m using the same algorithms (with a few tweaks), but the explanations now include interactive diagrams.

{why polygons?}

#Polygonal Regions

There are four steps to constructing the polygon mesh:

Dual mesh construction
  1. Pick evenly distributed points.
  2. Construct a Delaunay triangulation.
  3. Calculate the centroids of the triangles.
  4. Construct polygonal regions from those points.

Putting it all together, I have a dual mesh, which has both polygonal regions and triangles. Each red point corresponds to one region; each blue point corresponds to one triangle. The red points are the corners of the triangles; the blue points are the corners of the regions. I use centroid polygons here but the same steps work for Voronoi compare: Centroid  Voronoi. I picked centroids because the blue points are more evenly spaced.

For evenly distributed red points, I used Poisson disc sampling in this project and Lloyd relaxation in the first version. Other options are to use points on a grid, or points on a grid randomly perturbed. I didn’t use uniformly random points, because they aren’t evenly distributed.

1.1TODO Variable density points#

https://azgaar.wordpress.com/2017/10/05/templates/ - explores more points near coastlines, and fewer points in oceans

#Islands

For this game I’m generating islands, so the boundary of the map will always be water. In the interior, we can use noise to determine which areas are land and water. {this is the constraint+randomness theme}

Water, ocean, lake, coastlines
  1. Use noise to determine land vs. water.
  2. Use connectivity to determine which water regions are ocean.
  3. Lakes are any water regions not connected to the boundary of the map.
  4. Coastlines are the edges connected to an ocean region on one side and a land region on the other.

I’m using Simplex noise minus a value that depends on the distance to the boundary of the map: 1 + noise(x, y) - sqrt(x^2 + y^2) < 0? 'water' : 'land'.

https://en.wikipedia.org/wiki/High_island

2.1Alternatives#

There are many other ways to make coastlines. A mix of sine waves in polar coordinates works pretty well. Noise functions in polar coordinates work well too. A level designer might choose a specific shape for the coastline. For this project I chose to start with the coastline and then build a height map, but another approach is to start with a height map and set the coastline where the elevation crosses zero.

2.2TODO Noise map#

  • Display the noise values and the land/water map side by side
  • Control noisy/deflate parameters here
  • Control octaves/etc parameters here

2.3TODO Lakes#

  • Highlight some lakes on the map using my svg arrow-out-of-the-box; it doesn’t have to be a separate diagram

#Elevation

For this project I set elevation based on the distance from the coast. To calculate it, run Breadth First Search from the coastline. I tried distances on the polygon regions and distances on the corners, and found corners worked better for this map generator.

Elevation
  1. Find corners along coastline edges. As above, coastline edges have an ocean on one side and land on the other side.
  2. Calculate corner distance from the coastline using Breadth First Search.
  3. Set corner elevation by rescaling ocean distances from -1 to 0 and land distances from 0 to +1.
  4. Set the region elevation to the average elevation of the polygon’s corners.

There is no randomness or noise in this step.

3.1Alternatives#

Elevation based on distance to coastline produces simplistic symmetric volcanic-style islands. It’s what we wanted in our game. However it’s not the most interesting terrain. There are lots of other ways to set elevation, such as fractal noise, using river basins to set elevation, or drawing mountains and coastlines.

Both water → elevation (shown here) and elevation → water are possible.

3.2Lakes#

If there are no lakes, Breadth First Search works great, but with lakes, things get more complicated. I want the entire lake to have the same corner elevation, so I check if the edge has a lake on either side. If so, I don’t increase the distance along that edge. Look at the distance visualization to see this around lakes. This turns breadth first search into a more complicated graph search. I’m not happy with this but it’s good enough for now.

Alternatively, if you want lakes at elevation 0, you can treat them like oceans. Set elevation based on distance to ocean or lake.

3.3TODO Controlling the distribution#

{ show the distribution }

If we have a desired distribution of elevations, we can reshape the distribution. I’m using a linear mapping from distance to elevation but that mapping can be anything.

#Drainage

At each corner, I point to the corner that has the lowest elevation. This forms a drainage map, sometimes called a watershed map.

  1. Streams start on land and flow down to the coastline.
  2. Streams join together (tributaries) but don’t fork (distributaries).
  3. There are no cycles.
Drainage patterns

Because elevations are based on distances, there are many possible drainage graphs for the same elevation map. Which one we calculate depends on the graph traversal order. This is an opportunity to use a random seed to choose which of the many drainage graphs we generate:

4.1Lakes#

Along lakes, the elevation isn’t increasing, so what should the drainage map do? I make the drainage map follow the graph search used for elevation, so any drainage leading into a lake will eventually lead out, but may take a convoluted path inside the lake. I’m not happy with this but it’s good enough for now.

4.2TODO Watersheds#

Drainage can also be used to define watersheds, which can be useful as political and cultural boundaries. Rivers are also useful as political (but not cultural) boundaries.

{ diagram or layer showing watershed boundaries }

#Rivers

Rivers are a subset of the streams in the drainage map.

  1. Choose a subset of points to be potential river sources. {constraint}
  2. Choose a subset of those points to be rivers. {random}
River creation
rivers

5.1TODO Parameters for selecting a subset of rivers#

Not all locations produce equally good rivers. Some filters to consider:

  1. Only “leaves” of the drainage tree. (implemented above)
  2. Only above some elevation threshold.
  3. Only on sloped land. (if you have variable slopes)
  4. Only locations with plenty of rainfall. (if you have rainfall implemented)
  5. Only locations with wind carrying moisture from bodies of water.
  6. Only land that’s on a peak not a valley.

{should this be an interactive diagram?}

#Moisture

I use a “moisture” value to assign biomes in the next section. I set moisture on land to the distance from a lakeshore or riverbank. The start points are polygonal regions adjacent to lakes or rivers. Similar to elevation, I use Breadth First Search to calculate the distances, then rescale them. Zero distance will have moisture 1.0 and high distance will have moisture 0.0. Water regions will have moisture 1.0.

Moisture
rivers

There are many other ways to assign moisture/humidity/rainfall. I used this one because it was simple and worked well for the game these maps were for. It’s unable to produce effects like the Nile going through a desert. Other ways to assign moisture include noise (Perlin, Simplex, etc.) and wind simulation (rain shadows, evapotranspiration, etc.).

6.1TODO Controlling the distribution#

{ show the distribution }

If we have a desired distribution of moisture, we can reshape the distribution. I’m using a sqrt mapping from distance to moisture but that mapping can be anything.

#Biomes

(explanation about whittaker diagrams, indexed with temperature and rainfall – temperature is based on elevation and latitude, but on a small island the latitude is constant; rainfall is based on evaporation and wind but I’m just using moisture=evaporation here)

Biomes
rivers
temperature bias: moisture bias:

7.1TODO Noisy boundaries#

  1. Add random number to elevation/moisture
  2. Add random noise to elevation/moisture

7.2TODO Controlling the distribution#

{ show the distribution }

See also http://worldengine-ecs.readthedocs.io/en/latest/biomes.html – it seems useful to draw the scatter plot or a density plot, and then provide parameters for tuning that to make an ice world or a forest world etc.

#Noisy rendering

8.1Noisy edges#

Goal: replace the straight-line boundaries of polygonal regions (including biome borders, coastlines, and rivers) with “noisy” lines.

I am following the same general technique I used in 2010.

separate page

levels = amplitude =

8.2TODO Noisy transitions#

8.3TODO Noisy fills#

#Export

#10  Libraries

Although it’s sometimes fun to reimplement everything myself, I try not to do that. I used these libraries:

  • poisson-disk-sampling
  • delaunator
  • simplex-noise
  • int-hash

#11  References

#12  More