# Procedural Terrain Using Voronoi Diagrams

Voronoi Diagrams: Sounds scary and intimidating! Fear not! They're actually very straight-forward to implement and have a wide variety of applications.

I needed a method to divide a matrix of cells into a series of "regions" to create a procedurally generated map for a game setting, and after researching and testing other methods I found that Voronoi Diagrams gave me good looking results with benefits over other methods such as simplex noise algorithms. It allows control over the shape of your generated landmass, and the "region" points information can be saved from the map generation process to support gameplay features like region naming and identifying geographic features.

## What *IS* a Voronoi Diagram?

In mathematics, a Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane. That set of points (called seeds, sites, or generators) is specified beforehand, and for each seed there is a corresponding region consisting of all points closer to that seed than to any other. [1]

Mathemetician jargon! What does it mean? Well, I break it into two simple steps:

### 1. Seeding a Plane

Plotting seed points on a mathematical plane: a 2D grid of cells (a matrix) which will represent our map when the process is complete. So the first thing we need to do is create a list of 2d points to use as seeds for the voronoi regions.

*Example 1: Click to randomize the x and y coordinates 7 points within the plane.*

### 2. Regions Based on Distance to Points

Time to dust off the old Euclidean formula for finding the distance between two points! If you don't remember it from your math classes in school, this may refresh your memory (Where x1, y1, x2 and y2 are points in the Cartesian coordinate system):

So now we have our formula, where does the point data come from in order to find the distance? Since the voronoi seeds are just Cartesian points themselves, we need to loop through each voronoi seed in the list we generated in step 1.

But where do we get the x2 and y2 values? Remember, we're plotting all of this on a 2d grid of cells and each individual cell is referenced in the matrix by its Cartesian coordinates. This means that we can get these coordinates for the formula by iterating over each column and row in our grid with a few nested for loops. For each cell in that matrix, we iterate through the voronoi seeds in our list from step 1, calculating the distance from the current matrix cell and each voronoi point. When we find the voronoi seed that has the least distance to the current cell we simply store which voronoi seed that matrix cell "belongs" to and then move on to the next point.

*Example 2: Click to refresh the voronoi regions using the randomized points from Example 1.*

Finally, we will have a plane that is subdivided into regions based on the distance to points in a specific subset of the plane. In lay terms: We've finished plotting our voronoi diagram!

## Regional Topography

So now we have divided the plane into regions, how do we make this into a topographic map? The voronoi regions on their own make a great political map, but we want to see more than just splotches of colour. We want to see mountains, oceans, plains and grasslands!

The way I achieve this is to assign a random height to each voronoi seed. That way, we can use it as a sort-of "average elevation" for that region and calculate the "altitude" of each cell in our matrix by taking that point's height. As we iterate again through each cell in the matrix we can take the point's height and add or subtract a random amount to get some altitude variation within the region and store that value in the cell.

Assigning altitude isn't enough on its own, we also need to know which cells in the matrix are sea and which are land. I simply store the "sea level" height as a constant and when iterate through the matrix comparing the height of the cell to the "sea level" for the map: If it's below or at sea level it becomes a "sea" cell, if not it becomes a "land" cell. Whether or not the land cell is classified as a flatland cell (grassland/plains) or a hilly/mountainous cell can be determined similarly by storing a "mountain level" constant and comparing the cell's altitude to that value as we iterate through the matrix.

## Screenshots

Here are some examples of terrain generated using the method I've described in my WWII Simulator project (GitHub: ). The maps are generated using a random seed number so that the starting conditions can be repeated and the same map can be regenerated in game.