Theory

The key points on theory and applications of procedural generation is described in the series Procedural Generation parts 1 to 3, where we looked at a number of elements that could describe our virtual world. In this section we look at a practical implementation, combining all the different elements.

Implementation

As application I chose a scenario based on the 3 part article, to generate a artificial 'world' with a varied terrain, climate and biomes. As I was making the implementation while writing the previous articles, the implementation is consistent with the information in the articles.

The tool of choice was Microsoft Visual Studio, C# .net using WPF. WPF actually comes with a 3D engine (using the WPF component 'ViewPort3D') which was surprisingly easy to use, and ideal for implementing the visualisation of this atificially generated world. Credit also goes to the WriteableBitmapEx extension, which extends the WPF bitmap with convenient access functionality.

The resulting application is crude, but includes a number of illustrative components:

- Selection of key parameters such as the master seed number

- A bitmap representation of the generated map (where 1 pixel represents 1 square km in this case)

- Numerical key statistics on terrain / biomes

- A 3D view of the current location within the map including immidiate surrounding

Download

Download ProceduralWorldGenerator

Links

Microsoft Visual Studio

WPF

WriteableBitmapEx

Terrain

Continuing from part 2, a scalable fractal method is used to create terrain. All attributes generated is based on a specific seed for the current region.
An example of terrain elevation (black / blue: low, green / yellow: high), and using a threshold to define land (green) / water (blue)

Humidity / Rainfall

Continuing to a more advanced scenario, humidity / rainfall could be determined from obvious sources, any bodies of water. In this case, a streight forward approach is used, using a Gaussian function / filter.

Humidity / rainfall map (blue: humid, yellow: dry)

Temperature

Temperature can be generated by using a similar algorithm used for the terrain, and subsequently applying a Gaussian filter. As mentioned, all the attributes for this region are based on a single seed. This means that for each map or set of attributes, random generators are reset to the start seed. Generating this secondary map for temperature would result in a geography identical to the terrain map. This is resolved by offsetting the generation by 1 or more draws.

for (loop = n)
{
    random()
}
// proceed with random draws from terrain

It was found that a single draw is enough so the resulted maps show no similarity with previous generated maps based on the same seed.

Additionally, this map can be adjusted for water and elevation. Above water temperature is moderated, reducing very low or very high temperatures towards a baseline value. For land, the temperature is reduced by the elevation level.

Temperature map (red: hot, blue: cold)

We now have elevation, humidity and temperature. Using composite coloring, these can be combined into a single map. But first, lets look at defining biomes.

Biome

As final step, biome type can be defined. The biome type can be determined as function of temperature and rainfall.

In the composite map, the temperature is shown using the red / blue color channels as in the temperature map, and humidity / rainfall is indicated using the green color channel. Water is shown as plain blue.

Using a mapped coloring scheme, the biome types can be visualised on the same map.

Composite map / Biome map

Links

Generating Random Fractal Terrain

Projections / Biome generation

Hero Extant: World Generator

Wikipedia: Biome

In part 1 we looked at the method used for creating terrain. Midpoint Displacement is a fractal method which results in self-similarity implicitely making it scalable. Moreover the method can be scaled depending on the extent of the scope (e.g. 10 m vs 1 km vs 10 km), and number of iterations into smaller sub-divisions it is continued for (e.g. from 1 km to about 1m after 10 iterations). But imagine a large map of 1000 km, where we want to evaluate terrain upto a detail of 1 m, would take a lot of computing power, and significant storage. And this is only considering a single plane in 2 dimensions. So we can introduce partitioning. This is used in Minecraft, which uses three dimension segments of 16 x 16 (x 256) m.
In this case we use a two dimensional plane, of about 1000 km square, made up of 1000 x 1000 segments each representing 1 km square. Looking back to part 1, where we create an array of random seeds. Instead of a simple array, we create a 2 dimensional array of segements including a seed. To make this aspect scalable as well, seeds are generated in a similar order using a simple iterative midpoint method. This pattern is shown below, starting with the segments marked 1, then 2, 3, until each segment has a seed allocated.

step = size while step > 1
{
    for y = 0:size:step
    {
        for x = 0:size:step
        {
            seed[y,x] = new seed
        }
    }
    size / 2
}

Segmentation pattern

Segments are only evaluated on-demand. Each segement is initialised using its seed, generating a terrain map. In addition other characteristics are evaluated as we will see in part 3.

Links

Generating Random Fractal Terrain

The concept of procedural generation is creation based on rules and algorithms, instead of manual construction. A common application is to create scenarios like a landscapes, but in such a way that is repeatable and predictable within a controlled setting. Additionally this normally results in high consistency. Though widely used in games including recent ones such as Minecraft and Rust, there are many other useful applications such as simulation modelling.

Ideally, the generation is a fractal method providing scalability. We will look at this in more detail in part 2.

To produce a set of proporties and attributes in a reproducible yet variable way, the common Random (or Rnd) function can be used. This function does not actually provide real random numbers, but psuedo random numbers. The 'random' numbers are generated, effectively implementing procedural generation. Additionally these are normally based on a start seed. So we want to create a set of properties, such as for different locations, each based on a seed. Next we want all of those to be based on one single master seed.

In simple pseudo code:

int masterSeed = 12345678

Random randomGenerator = new Random(masterSeed)

int[] locationSeeds = new int[100]

foreach (int locationSeed in locationSeeds)
{
    locationSeed = randomGenerator.getNext()
}

As this example illustrates, changing the masterSeed will result in a different set of location specific seeds. Next, for each specific location, different properties can be generated, in a consistent way - if and when they are required:

Random randomGenerator = new Random(locationSeed)

foreach (Property property in properties)
{
    property = randomGenerator.getNext()
}

The method used for creating fractal terrain is Midpoint Displacement, though it is worth mentioning Perlin noise is another popular method used for this. Midpoint Displacement in one dimension is simple (see images below), starting with two points (1), and a straight line connecting these (2), find the midpoint on the line (3) and displace the new point up or down with a particular magnitude(4). There are now 2 connecting straight lines, drawn over 3 points (5). The process continues iteratively, finding the next midpoint between previous points in turn, and displacing these with a decreasing magnitude. For two dimension, the diamond-square algorithm is applied.
Midpoint Displacement illustration

Links

Procedural Content Generation in Games

Generating Random Fractal Terrain

Fractal landscape

Diamond-Square algorithm

Perlin noise