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


There are four steps to constructing the polygon mesh we need:

Evenly distributed pointsDelaunay triangulationTriangle centroidsPolygonsDual mesh
  1. Pick evenly distributed points using Poisson disc (or Lloyd relaxation).
  2. Construct a Delaunay triangulation.
  3. Calculate the centroids of the triangles.
  4. Construct polygons from those points.

Putting it all together, I have a dual mesh. The same steps work for Voronoi instead of centroid polygons; compare: Centroid  Voronoi.

{ implementation notes - here or later? }

For evenly distributed red points, I used Poisson disc sampling in this project and Lloyd relaxation in a previous project.

I added points along the boundary of the map with a slight curvature to avoid long skinny Delaunay triangles.

#Map representation

{ should implementation be on a separate page? }

stuff from this page


I’m generating islands, so the boundary of the map will always be water. In the interior, I can use noise to determine which areas are land and water.

Choose polygons that are water vs land
Connectivity from the boundary identifies oceans vs lakes
Lakes are water polygons not connected to the boundary
Coastline separates oceans from land
parameters: noisyround ; deflateinflate

There are two things we need once we’ve assigned water vs land:

  1. Use noise to determine land vs. water.
  2. Use connectivity to determine which water polygons are ocean.
  3. Lakes are the water polygons not connected to the boundary of the map. Try changing the parameters until lakes form.
  4. Coastlines are the edges connected to an ocean polygon on one side and a land polygon on the other.

{ should I explain the game’s needs, so that the reader can pick different algorithms that match their own needs? }

{ implementation notes could include the noise function – maybe the noisy/deflate parameters could move to a separate diagram to avoid having to explain the lack of lakes in the main list; connectivity is depth first or breadth first search }


For this project I set elevation based on the distance from the coast. It’s not the right choice for most maps, but it was the right thing for the project I made this for. To calculate it, I’ll run Breadth First Search from the coastline. I tried distances on the polygons and distances on the corners, and I found corners worked better for this map generator.

Distance from coastline, corners
Distance from coastline, polygons
  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 polygon elevation to the average elevation of the polygon’s corners.


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.

4.2TODO Elevation from noise#

Elevation based on distance to coastline produces simplistic symmetric volcanic-style islands. It’s what we wanted in our game. There are lots of other ways to set elevation.

4.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.


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

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

Rivers follow the drainage map, but for this project, not all drainage channels become rivers. I pick them randomly.

{ implementation: because elevations are based on distances, there are many possible downslope graphs for the same elevations, and which one we calculate depends a lot on the graph traversal order, ick – this needs to be part of the random seed, maybe using noise or some location based hash }


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.

5.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 }

5.3TODO 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.


I use a “moisture” value to assign biomes in the next section. I set moisture to the distance from a lake or river. The start points are lake polygons and the the polygons adjacent to a river. 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.


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. Consider instead using noise (Perlin, Simplex, etc.) or 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.


(explanation about whittaker diagrams)


7.1TODO 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

9.1Noisy edges#

9.2Noisy transitions#

9.3Noisy fills#

#10  References

#11  More