Generating game maps based on: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

• General info
• Polygons
• Map Representation
• Islands
• Elevation
• Rivers
• Moisture
• Biomes
• Final Map
• Libraries
• Status
• Credits

The first step was to create a grid of polygons. We did that by generating random points which created Voronoi polygons. The distribution of points in some parts of the [0,1]^2 space is denser to get a better variety of final maps. Then we replaced each point by the centroid of the polygon region related to this point.

The polygons weren't evenly distributed, so we used a technique called Lloyd relaxation, which replaces each point by the centroid of this polygon.
Here we also plotted edges to the neighbouring polygons.

Map is built from two graphs, Nodes and Edges. Nodes graph has edges between every neighbouring polygons. Edges graph has edges between every neighbouring corners.

class TerrainType(Enum):
    OCEAN = 1
    LAND = 2
    LAKE = 3
    COAST = 4

class Graph:
    Centers
	Corners
	Edges

class Center:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.neighbors = []
        self.borders = []
        self.corners = []
        self.terrain_type = TerrainType.LAND
        self.biome = BiomeType.OCEAN
        self.height = 0
        self.moisture = 0

class Corner:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.touches = []
        self.protrudes = []
        self.adjacent = []
        self.terrain_type = TerrainType.LAND
        self.height = 0
        self.downslope = None
        self.river = 0
        self.moisture = 0

class Edge:
    def __init__(self, center1, center2, corner1, corner2):
        self.d0 = center1
        self.d1 = center2
        self.v0 = corner1
        self.v1 = corner2
        self.river = 0

To generate coastline we're using flooding simulation. First, we're setting edges touching the map borders and edges located in random areas near the map borders as water edges. Then the flooding is started until enough edges become the water we're choosing new water edges and set all edges touching this one as water edges.

Finally, we're choosing random edges inside the island as the lake edges, and then starting flooding once again from those edges.

Finally, the tile is assigned as water if more than min_water_ratio of their borders are water edges.

Assigning terrain type goes as follow:

• The tile is an ocean if it's water and it's touching the map border or one of their neighbours is an ocean tile.
• Thie tile is a coast if it's land and it's touching an ocean tile.
• The tile is a lake if it's water and it's not an ocean.
• In another case, the tile is a land.

The main rule we followed is the more polygons there are between a point and the closest edge of the map, the higher is the elevation of this point. We calculate the elevation of corners first and then proceed with the polygons (centers).

We run BFS from every corner which is on the edge of a map. For every neighbor of the current_corner we update the neighbor.height with current_corner.height + epsilon if current_corner.height + epsilon < neighbor.height. If current_corner or neighbor is of type Ocean or Lake, the epsilon is equal to 0.01. Otherwise (when both of them are Land/Coast) it's 1.0. This way lakes will be more or less flat, oceans will be deep on the edges of the map and a little bit more shallow near the coast and land will become more and more elevated the closer it is to the map's center of mass.

Before assigning elevation for centers we redistribute elevation of corners so that they will take values from 0 to 1.0 and there will be less higher points on a map than the lower ones. It also smooths out the terrain.

Elevation of centers is simply the average of the elevation of all neighboring corners.

Elevation is very important for:

• Biomes types:
  • high elevations: get snow, rock, tundra
  • medium elevations: get shrubs, deserts, forests, and grassland
  • low elevations: get rain forests, grassland, and beaches
• 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.

First we defined downslope. From each Corner it is an arrow that points towards its lowest neighbouring corner.

We say that rivers flow from the highest points downwards following the downslopes.

We chose a random point in the mountains and we follow downslopes until we reach a lake or the ocean.

If more than one river is flowing through a given edge the river becomes visually thicker. The formula for width of an edge with k rivers is:

river_width(k) = 2 + 2 * sqrt(k)

Instead of the standard approach, where the localization of rivers and lakes depends on the moisture, we decided to first create water sources and then define the moisture of the terrain based on the distance from the freshwater.

First, we assigned starting moisture of corners. If the corner is a port of the river the moisture is equal to max(1.0, min(3.0, 0.25*corner.river)). If the corner touches the lake then the moisture is equal to 1.0.

Then we run BFS from every corner with nonzero stating moisture. The moisture of a corner is equal to: max(corner.moisture, 0.9*max(moisture of neighbors)).

After the moisture-spreading process, we set moisture of corners touches the ocean as 1.0.

The next step was to assign centers moisture. It's given by: mean(min(1.0, corner.moisture) for corner in center.corners)

We decided to redistribute those values to get equal distribution of dry and wet tiles. Finally, the moisture of the tile is equal to the position on the sorted list of moistures given by the previous step.

Each polygon has a biome type assigned to it. They can be easily defined using the moisture and elevation values.

Biomes in upper right corner are snowy mountains, lower right corner is a tropical rain forest, upper left corner are scorched mountains and lower left corner is a desert. Besides that, we also distinguish ocean from deep ocean - the latter are darker and have smaller elevation.

Below are listed all types of biomes that we use:

class BiomeType(Enum):
    OCEAN = 1
    LAKE = 2
    COAST = 3
    SNOW = 4
    TUNDRA = 5
    BARE = 6
    SCORCHED = 7
    TAIGA = 8
    SHRUBLAND = 9
    TEMPERATE_DESERT = 10
    TEMPERATE_RAIN_FOREST = 11
    TEMPERATE_DECIDOUS_FOREST = 12
    GRASSLAND = 13
    TROPICAL_RAIN_FOREST = 14
    TROPICAL_SEASONAL_FOREST = 15
    SUBTROPICAL_DESERT = 16
    MARSH = 17
    ICE = 18
    DEEPOCEAN = 19

The examples of maps generated by this approach (using different parameters and amount of starting points):

• Python - version 3.7.3
• numpy
• scipy
• shapely
• matplotlib
• plotly

Project: finished

• @MatMarkiewicz
• @jgrodzicki
• @SWi98
• @TheFebrin