Async Drink

Generating landscapes with the Diamond Square algorithm

Sep 17, 2019

Generating realistic looking landscapes is not only a fun activity it could also help you if you ever want to break into the video gaming industry.

Today we are going to look at one algorithm you can use to generate a landscape: the Diamond Square Algorithm.

The Diamond Square Algorithm is a recursive algorithm which generates a height map. A height map in essence is a 2-dimensional array storing (often) floating point numbers. Each number represents the height at the given index.

The algorithm

I will first explain the algorithm step-by-step using images. Understanding the algorithm first will help you understand the code I'll show later on.

For this example we will use a 5x5 grid. Note how the grid size can be expressed also as the formula 2^2 + 1. This is not a coincidence as only grid sizes satisfying the formula 2^n + 1 are valid. We'll see later why.

Below you'll see the grid in its default state. Note how I have initialized all values as NaN. I prefer this as it allows me to easily catch any errors (as a value of 0 is a valid value and therefore indistinguishable from an invalid value).





Next we are going to assign a random value to each other corner points. In my case this is going to be a random value between 1 and 10. You are free to pick whatever value makes sense for you though.





Looking at the grid in its current state you could say (by looking at the filled corner points) we have created one big square. This is the initial step of the algorithm.

Next we are going to perform the first step. We call this the Diamond Step. Basically we take the average of each corner point and store this value in the centre of the grid.





Next we are going to create four new squares. We do this by filling in the missing corner points. We do this again by averaging neighboring points. We call this the Square Step.





Again we have now effectively creates four new squares. The below image will illustrate this.





We are now going to repeat the previous steps. First we perform the diamond step creating four centre points.





Note how we perform the diamond step for each square before moving on to the next square step.

Next we again do the step creating a new set of squares.





For the size of this grid we are done after only two iterations. Larger grid sizes of course take more iterations. The basic logic remains the same though.

A few things to note:

  • Right now we have averaged all values without any other modification. This means the same height map will be produced if the four initial corner points are the same. An adjustment you might consider is applying a small random variation for each averaged value. This will create a unique height map each time.
  • When applying such a random variation make sure the magnitude of this random value decreases each iteration. This way later iterations which comprise smaller areas will also naturally have less drastic fluctuations from the average.
  • Looking at the steps involved it should now make sense why a grid not satisfying the formula (2^n) + 1 would not work. If not try and draw the above steps on paper on a 4x4 grid.
  • You may consider smoothing the final result. I find if I just run the algorithm 'as is' results can appear to be a bit jagged.

The code

The basic algorithm isn't hard to grasp and maybe you already have an idea how to implement it in your favorite language. If not: read on as I will share the code in this chapter.

I have chosen to implement the algorithm as a basic website. The algorithm itself is programmed in Typescript while for rendering I use the Canvas API.

You can find the finished code here.

I have taken no great effort to optimize the algorithm. The focus here is on explaining how you could implement it rather than explaining the best or fastest implementation.

I have created the Grid class which helps me with managing the 2D grid. You can find this class here.

My main focus will by on the DiamondSquareGenerator class. The full source can be found here. I'll spent the rest of this chapter walking through the implementation step by step.

The DiamondSquareGenerator class has a single public method: the generate method. The implementation is simple:

generate() {
    this.grid.clear();

    this.initialize();

    this.step(this.grid.getSize());

    this.grid.smooth();
}

The basic steps are:

  • Clear the grid so it is reset to its initial state
  • Initialize the four corner points
  • Perform the algorithm
  • Smooth the result for a nicer looking result

Initializing the four corner points is also trivial:

private initialize() {
    // Left top corner
    this.grid.setValue(
        Math.random(),
        0, 0
    );

    // Right top corner
    this.grid.setValue(
        Math.random(),
        this.grid.getSize() - 1, 0
    );

    // Right bottom corner
    this.grid.setValue(
        Math.random(),
        this.grid.getSize() - 1, this.grid.getSize() - 1
    );

    // Left bottom corner
    this.grid.setValue(
        Math.random(),
        0, this.grid.getSize() - 1
    );
}

In this implementation the four corner points have a value between 0.0 and 1.0. During the course of the algorithm they could, in theory, drop below 0.0 or above 1.0.

To run the actual algorithm we use the step method. This method will recursively call itself until the entire grid has been filled. By splitting up the square and diamond steps into separate functions the actual step method becomes quite small:

private step(scale: number) {
    if (scale <= 2) {
        return;
    }

    this.diamond(scale);
    this.square(scale);

    this.step(Math.ceil(scale / 2));
}

The scale parameter we pass to this function describes how large the current square is. Initially this is equal to the size of the grid.

The algorithm itself will run until the scale is less or equal to two. At this point we can assume the entire grid is filled.

Now for the first step (the Diamond Step):

private diamond(scale: number) {
    const steps = Math.floor(this.grid.getSize() / (scale - 1));
    const magnitude = scale / this.grid.getSize();

    // Do square step
    for(let x = 0; x < steps; x++) {
        for(let y = 0; y < steps; y++) {
            const xCoord = x * (scale - 1);
            const yCoord = y * (scale - 1);

            const maxLength = scale - 1;

            const values = [
                this.grid.getValue(xCoord, yCoord),
                this.grid.getValue(xCoord + maxLength, yCoord),
                this.grid.getValue(xCoord + maxLength, yCoord + maxLength),
                this.grid.getValue(xCoord, yCoord + maxLength),
            ];

            const average = this.getAverage(values);

            this.grid.setValue(
                average + this.getRandomValue(magnitude),
                xCoord + (scale >> 1), yCoord + (scale >> 1)
            );
        }
    }
}

Again we pass the current scale we work at. This scale is used to determine for how many squares we need to calculate a center point.

I have written two utility functions (getAverage and getRandomValue) to help me calculate the average and offset it just a little bit to create more randomness.

The amount we offset the average with is determined by dividing the current scale by the grid size. Effectively this decreases the maximum potential offset the smaller the squares become.

Next for the Square Step I have chosen a rather straightforward approach. There are clever ways to minimize the amount of code needed. However I have chosen not to use this here to improve readability of the code.

private square(scale: number) {
    const steps = Math.floor(this.grid.getSize() / (scale - 1));
    const magnitude = scale / this.grid.getSize();

    // Do diamond step
    for(let x = 0; x < steps; x++) {
        for(let y = 0; y < steps; y++) {
            const xCoord = x * (scale - 1);
            const yCoord = y * (scale - 1);

            const maxLength = scale - 1;
            const halfSize = scale >> 1;

            // Top
            {
                const values: number[] = [
                    this.grid.getValue(xCoord, yCoord),
                    this.grid.getValue(xCoord + maxLength, yCoord),
                    this.grid.getValue(xCoord + halfSize, yCoord + halfSize)
                ];

                if (this.grid.isInGrid(xCoord + halfSize, yCoord - halfSize)) {
                    values.push(this.grid.getValue(xCoord + halfSize, yCoord - halfSize));
                }

                const average = this.getAverage(values);

                this.grid.setValue(
                    average + this.getRandomValue(magnitude),
                    xCoord + halfSize, yCoord
                );
            }

            // Bottom
            {
                const values: number[] = [
                    this.grid.getValue(xCoord, yCoord + maxLength),
                    this.grid.getValue(xCoord + maxLength, yCoord + maxLength),
                    this.grid.getValue(xCoord + halfSize, yCoord + halfSize)
                ];

                if (this.grid.isInGrid(xCoord + halfSize, yCoord + maxLength + halfSize)) {
                    values.push(this.grid.getValue(xCoord + halfSize, yCoord + maxLength + halfSize));
                }

                const average = this.getAverage(values);

                this.grid.setValue(
                    average + this.getRandomValue(magnitude),
                    xCoord + halfSize, yCoord + maxLength
                );
            }

            // Left
            {
                const values: number[] = [
                    this.grid.getValue(xCoord, yCoord),
                    this.grid.getValue(xCoord, yCoord + maxLength),
                    this.grid.getValue(xCoord + halfSize, yCoord + halfSize)
                ];

                if (this.grid.isInGrid(xCoord - halfSize, yCoord + halfSize)) {
                    values.push(this.grid.getValue(xCoord - halfSize, yCoord + halfSize));
                }

                const average = this.getAverage(values);

                this.grid.setValue(
                    average + this.getRandomValue(magnitude),
                    xCoord, yCoord + halfSize
                );
            }

            // Right
            {
                const values: number[] = [
                    this.grid.getValue(xCoord + maxLength, yCoord),
                    this.grid.getValue(xCoord + maxLength, yCoord + maxLength),
                    this.grid.getValue(xCoord + halfSize, yCoord + halfSize)
                ];

                if (this.grid.isInGrid(xCoord + maxLength + halfSize, yCoord + halfSize)) {
                    values.push(this.grid.getValue(xCoord + maxLength + halfSize, yCoord + halfSize));
                }

                const average = this.getAverage(values);

                this.grid.setValue(
                    average + this.getRandomValue(magnitude),
                    xCoord + maxLength, yCoord + halfSize
                );
            }
        }
    }
}

Note how for each corner we calculate we also check if we can add a fourth coordinate. Around the edge of the grid we cannot add a fourth coordinate (as we would be out of bounds there). However more towards the center of the grid we can use four coordinates to calculate a corner point.

In theory you could make the grid wrap around it self. This means we can always use four coordinates in the Square Step. Effectively this would mean the height map would move from the right back to the left side and from the bottom back to the top side.

Putting it all together

When filling a grid using the DiamondSquareGenerator class we just get a boring 2D height map. To actually render it with some nice colors I have written the following code (main.ts in the repository):

import { Grid } from './grid.js';
import { DiamondSquareGenerator } from './diamond-square-generator.js';

window.onload = () => {
    const grid = new Grid(Math.pow(2, 8) + 1);
    const scale = 4;

    const canvas: HTMLCanvasElement = document.getElementById('canvas') as HTMLCanvasElement;

    canvas.width = grid.getSize() * scale;
    canvas.height = grid.getSize() * scale;

    const context = canvas.getContext('2d');

    const generator = new DiamondSquareGenerator(grid);
    generator.generate();

    context.scale(scale, scale);

    for(let x = 0; x < grid.getSize(); x++) {
        for(let y = 0; y < grid.getSize(); y++) {
            const value = grid.getValue(x, y);

            let color: string;
            if (value < 0.4) {
                color = 'rgb(0, 0, 255)';
            } else if(value >= 0.4 && value < 0.41) {
                color = 'rgb(160, 160, 9)';
            } else if(value >= 0.41 && value < 0.7) {
                color = 'rgb(0, 255, 0)';
            } else if(value >= 0.7 && value <= 0.95) {
                color = 'rgb(64, 192, 64)';
            } else if(value >= 0.95 && value < 0.98) {
                color = 'rgb(128, 128, 128)';
            } else if(!isNaN(value)) {
                color = 'rgb(255, 255, 255)';
            }

            context.fillStyle = color;
            context.fillRect(x, y, 1, 1);
        }
    }
}

This code goes hand in hand with the accompanying HTML file found here.

It basically prepares the Canvas element for drawing and then iterates through the 2D grid. For each point it will decide which color to apply. There is no real magic here. Just a set of if/else statements.

How you color things is entirely up to you. The important thing is you now have a 2D height map you can play with!

I would advise to play with the color values. Maybe you can come up with a new scheme? Also play around with the size of the grid and the offset applied to each averaged value. See if you can come up with an interesting result!

Got any feedback or questions? Or just want to send me a message? You can contact me at info@asyncdrink.com
© Copyright 2019 by Mathyn