The diamond-square algorithm is a procedural terrain generation algorithm. It makes it easy to generate Heightmaps and Terrain for games. In this article we will implement the diamond-square algorithm in JavaScript, plot our terrain on a canvas and see how a player can interact with its various terrain types.

Many games are using *Procedural Terrain Generation*. This cool and geeky term means that one generates the terrain in one’s game… well… procedurally. Procedurally means we have a loop (or recursion), and on every step of the loop, the terrain is being refined until we reach the wanted result.

Figure 1 shows the terrain generated using the Diamond-Square algorithm. Let’s see how you can generate such maps, play with their parameters to generate a more refined map and eventually, use it in a game (or any other interaction you can think of).

Figure 1: A terrain created using the algorithm. White marks snowpeaks, red/brown marks mountains, green is grassland and blue/purple is water.

Table of Contents

## The Algorithm

As usual, we need to remember our canvas is a matrix. That means, it is an N x M table with pixels in it. Figure 2 illustrates the phases of the algorithm.

- Start with a matrix width and height of 2^n+1 and fill the 4 corners with random numbers (can do non random ðŸ™‚ ).
**Start**in**Figure 2**. - In each iteration:
- Calculate the center of the available diamonds such that their value is equal to the mean of the 4 closest diagonals.
**Iteration 1 – Diamond step**and**Iteration 2 – Diamond step**in**Figure 2**. - Calculate the center of the available squares such that their value is equal to the 4 closest top, left, right and bottom values.
**Iteration 1 – Square step**and**Iteration 2 –**in**Square**step**Figure 2**.

- Calculate the center of the available diamonds such that their value is equal to the mean of the 4 closest diagonals.
- When the matrix is full, the algorithm finishes.

One thing to note, to make it a bit more interesting – the calculation should actually be:

`mean(4 corners) + jitter`

Where `jitter`

is a random number proportionate to the iteration index:

`jitter = intInRange(-RANDOM/Math.pow(2,i), RANDOM/Math.pow(2,i))`

That’s kind of it… Figure 2 shows the direction of calculations (blue arrows) in every step for a matrix with N = 2. You can click on the figure to enlarge it.

## How to Implement Diamond-Square in JavaScript?

### Step 1: Generate a random matrix

const N = 2; | |

const RANDOM_INITIAL_RANGE = 10; | |

const MATRIX_LENGTH = Math.pow(2, N) + 1; | |

function randomInRange(min, max) { | |

return Math.floor(Math.random() * (max - min + 1) + min); | |

} | |

function generateeMatrix() { | |

const matrix = new Array(MATRIX_LENGTH) | |

.fill(0) | |

.map(() => new Array(MATRIX_LENGTH).fill(null)); | |

matrix[0][MATRIX_LENGTH - 1] = randomInRange(0, RANDOM_INITIAL_RANGE); | |

matrix[MATRIX_LENGTH - 1][0] = randomInRange(0, RANDOM_INITIAL_RANGE); | |

matrix[0][0] = randomInRange(0, RANDOM_INITIAL_RANGE); | |

matrix[MATRIX_LENGTH - 1][MATRIX_LENGTH - 1] = randomInRange( | |

0, | |

RANDOM_INITIAL_RANGE | |

); | |

return matrix; | |

} |

The function `generateMatrix`

creates a two dimensional array of the size MATRIX_LENGTH. As mentioned in the algorithm, we set it to be `Math.pow(2, N) + 1`

. N is 2 in this example, but you can set any N depending on the pixel resolution you are interested in.

After creating the matrix, the function then sets the 4 corners of the matrix with random values. Eventually, the function returns a starting matrix much like the **Start** matrix in **Figure 2**.

### Step 2: Iterate until matrix is full

function diamondSquare(matrix) { | |

let chunkSize = MATRIX_LENGTH - 1; | |

let randomFactor = RANDOM_INITIAL_RANGE; | |

while (chunkSize > 1) { | |

calculateSquare(matrix, chunkSize, randomFactor) | |

calculateDiamond(matrix, chunkSize, randomFactor) | |

chunkSize /= 2; | |

randomFactor /= 2; | |

} | |

return matrix; | |

} |

This function is pretty simple and implements the algorithm quite literally. It starts with `chunkSize`

as the length of the matrix and the `randomFactor`

as our jitter.

On every iteration it calculates the diamonds, then the squares and divides the `chunkSize`

and `randomFactor`

by 2.

### Step 3: Calculate Diamond

function calculateDiamond(matrix, chunkSize, randomFactor) { | |

let sumComponents = 0; | |

let sum = 0; | |

for (let i = 0; i < matrix.length - 1; i += chunkSize) { | |

for (let j = 0; j < matrix.length - 1; j += chunkSize) { | |

const BOTTOM_RIGHT = matrix[j + chunkSize] | |

? matrix[j + chunkSize][i + chunkSize] | |

: null; | |

const BOTTOM_LEFT = matrix[j + chunkSize] | |

? matrix[j + chunkSize][i] | |

: null; | |

const TOP_LEFT = matrix[j][i]; | |

const TOP_RIGHT = matrix[j][i + chunkSize]; | |

const { count, sum } = [ | |

BOTTOM_RIGHT, | |

BOTTOM_LEFT, | |

TOP_LEFT, | |

TOP_RIGHT | |

].reduce( | |

(result, value) => { | |

if (isFinite(value) && value != null) { | |

result.sum += value; | |

result.count += 1; | |

} | |

return result; | |

}, | |

{ sum: 0, count: 0 } | |

); | |

const changed = {row: j + chunkSize / 2, column: i + chunkSize / 2}; | |

matrix[changed.row][changed.column] = | |

sum / count + randomInRange(-randomFactor, randomFactor); | |

} | |

} | |

return matrix; | |

} |

This is the first “complex” bit of logic in our algorithm.

It runs on the matrix in chunks so for every chunk it sums the 4 corners (BOTTOM_RIGHT, BOTTOM_LEFT, TOP_RIGHT, TOP_LEFT) and calculates the mean into the center.

### Step 4: Calculate Square

function calculateSquare(matrix, chunkSize, randomFactor) { | |

const half = chunkSize / 2; | |

for (let y = 0; y < matrix.length; y += half) { | |

for (let x = (y + half) % chunkSize; x < matrix.length; x += chunkSize) { | |

const BOTTOM = matrix[y + half] ? matrix[y + half][x] : null; | |

const LEFT = matrix[y][x - half]; | |

const TOP = matrix[y - half] ? matrix[y - half][x] : null; | |

const RIGHT = matrix[y][x + half]; | |

const { count, sum } = [BOTTOM, LEFT, TOP, RIGHT].reduce( | |

(result, value) => { | |

if (isFinite(value) && value != null) { | |

result.sum += value; | |

result.count += 1; | |

} | |

return result; | |

}, | |

{ sum: 0, count: 0 } | |

); | |

matrix[y][x] = sum / count + randomInRange(-randomFactor, randomFactor); | |

} | |

} | |

return matrix; | |

} |

It first takes half the chunk sent to it and runs over the matrix in half chunks. So if we sent the whole length, it starts by calculating for the middle (length/2, length/2). It then gets the values of the `BOTTOM`

, `TOP`

, `LEFT`

and `RIGHT`

, calculates the mean, adds the jitter and assigns the value to the middle.

On the next iteration, it will get `chunkSize = length/2`

so it will run on the smaller squares.

## Generating a heightmap

Now that we have our algorithm, we can generate a heightmap using canvas.

function normalizeMatrix(matrix) { | |

const maxValue = matrix.reduce((max, row) => { | |

return row.reduce((max, value) => Math.max(value, max)); | |

}, -Infinity); | |

return matrix.map((row) => { | |

return row.map((val) => val / maxValue); | |

}); | |

} | |

function draw(matrix, canvas) { | |

const ctx = canvas.getContext("2d"); | |

const normalizedMatrix = normalizeMatrix(matrix); | |

ctx.beginPath(); | |

normalizedMatrix.forEach((pixelsRow, rowIndex) => { | |

const y = rowIndex * MATRIX_DIMENSIONS.pixelHeight; | |

pixelsRow.forEach((pixel, pixelIndex) => { | |

const x = pixelIndex * MATRIX_DIMENSIONS.pixelWidth; | |

ctx.fillStyle = getColor(pixel); | |

ctx.fillRect( | |

x, | |

y, | |

MATRIX_DIMENSIONS.pixelWidth, | |

MATRIX_DIMENSIONS.pixelHeight | |

); | |

}); | |

}); | |

ctx.closePath(); | |

} |

Our drawing function gets a matrix and a canvas to draw on. It normalizes the matrix to its maximum, which means that the maximum value in the matrix will be 1 and the rest will be a fraction. This creates the effect of values as percentages. Then, for each pixel in our matrix, we draw a rectangle with a color that is represented by the value in the cell.

The `getColor`

function can be anything we want. Let’s start with something simple:

function getColor(percentage) { | |

const hue = percentage * 360; | |

return `hsl(${hue}, 100%, 50%)`; | |

} |

The `getColor`

function above will generate a random color in `HSL`

. HSL has hue values between 0 and 360, so multiplying our percentage (normalized values) will give us a value between 0 and 360. Watch a live demo here:

See the Pen Diamond Square by Yonatan Kra (@yonatankra) on CodePen.

## Generating a simple terrain

The heatmap or heightmap generated using HSL in the former section is nice. But what if we want to generate something more meaningful to our strategy game? We’d like to actually show mountains, plains and water…

Here’s a simple function that generates these colors:

function landscapeColors(percentage) { | |

const hue = percentage >= .66 ? 240 : percentage >= .33 ? 120 : 0; | |

const lightness = 50; | |

const saturation = 100; | |

return `hsl(${hue}, ${saturation}%, ${lightness}%)`; | |

} |

This simple function simply returns 3 colors: red for mountains, green for plains and blue for water.

Check out this live demo:

See the Pen Diamond Square Height Map by Yonatan Kra (@yonatankra) on CodePen.

## Generating a more realistic terrain

The simple terrain we’ve generated reminds us games we played in the 80’s. Ok, some of us played in the 80’s ðŸ˜‰

But we can play with the code to return much more complex terrain types. Here’s a code that generates a smoother terrain and adds snow in the mountains:

function landscapeColors(percentage) { | |

const colorVariety = 3; | |

const colorStep = 360 / colorVariety; | |

const colorIndex = Math.floor(percentage * colorVariety); | |

const hue = | |

colorStep * colorIndex + colorStep * (percentage - (colorIndex * 100) / 3); | |

const lightness = percentage < 0.01 ? 100 : 50; | |

const saturation = 100; | |

return `hsl(${hue < 360 ? hue : hue - 360}, ${saturation}%, ${lightness}%)`; | |

} |

In this code example, I smooth the experience by adding more hues with a more complex hue equation. In addition, I add a rule to set lightness to 100 in case of a very small percentage – that in high chance appears in the middle of a mountain range.

Check out the live demo with another more complex example here (complements of Miki Ezra Stanger):

See the Pen Diamond Square Terrain by Yonatan Kra (@yonatankra) on CodePen.

## Using the terrain in a game

Now let’s assume that in our game, we’d like the user to click on a terrain and see its details. There are many ways to do this, but the new Path2D API makes collision detection a breeze.

We’re going to change our code a bit:

function landscapeColors(percentage) { | |

const colorVariety = 3; | |

const colorStep = 360 / colorVariety; | |

const colorIndex = Math.floor(percentage * colorVariety); | |

const hue = | |

colorStep * colorIndex + colorStep * (percentage - (colorIndex * 100) / 3); | |

const lightness = percentage < 0.01 ? 100 : 50; | |

const saturation = 100; | |

const terrainType = | |

lightness === 100 | |

? "snow" | |

: colorIndex === 0 | |

? "mountains" | |

: colorIndex === 1 | |

? "plains" | |

: "water"; | |

return { | |

hsl: `hsl(${hue < 360 ? hue : hue - 360}, ${saturation}%, ${lightness}%)`, | |

terrainType | |

}; | |

} | |

function draw(terrain_matrix) { | |

const ctx = canvas.getContext("2d"); | |

const paths = { | |

water: new Path2D(), | |

plains: new Path2D(), | |

mountains: new Path2D(), | |

snow: new Path2D() | |

}; | |

ctx.clearRect(0, 0, CANVAS_HEIGHT, CANVAS_WIDTH); | |

ctx.beginPath(); | |

terrain_matrix.forEach((pixelsRow, rowIndex) => { | |

const y = rowIndex * MATRIX_DIMENSIONS.pixelHeight; | |

pixelsRow.forEach((pixel, pixelIndex) => { | |

const x = pixelIndex * MATRIX_DIMENSIONS.pixelWidth; | |

const { hsl, terrainType } = getColor(pixel); | |

ctx.fillStyle = hsl; | |

ctx.fillRect( | |

x, | |

y, | |

MATRIX_DIMENSIONS.pixelWidth, | |

MATRIX_DIMENSIONS.pixelHeight | |

); | |

const tmpPath = new Path2D(); | |

tmpPath.rect( | |

x, | |

y, | |

MATRIX_DIMENSIONS.pixelWidth, | |

MATRIX_DIMENSIONS.pixelHeight | |

); | |

paths[terrainType].addPath(tmpPath); | |

}); | |

}); | |

ctx.closePath(); | |

return paths; | |

} | |

canvas.addEventListener("click", (event) => { | |

const pathsNames = Object.keys(paths); | |

const ctx = canvas.getContext("2d"); | |

const { top, left } = canvas.getBoundingClientRect(); | |

for (let i = 0; i < pathsNames.length; i++) { | |

if ( | |

ctx.isPointInPath( | |

paths[pathsNames[i]], | |

event.clientX - left, | |

event.clientY - top | |

) | |

) { | |

alert(`I've just hit the ${pathsNames[i]}`); | |

return; | |

} | |

} | |

}); |

In the code above we can see 3 parts: 2 changed functions and one event listener.

Our `landscapeColors`

function now also returns a terrain type.

Our `draw`

function now creates paths (instances of `Path2D`

) that will hold each terrain type in a path of its own. It then returns this paths object to its caller.

The event listener listens to user clicks on the canvas. It then checks for every terrain path if the click was on it or not. If it was, it raises an alert with the terrain type we clicked on.

Here’s the live demo:

See the Pen Diamond Square Better Terrain by Yonatan Kra (@yonatankra) on CodePen.

The example above can be used in order to create all sorts of interactions. For instance, you can use collision detection between a player moving on the screen and the terrain. Maybe a user can’t move through mountains, or needs to purchase a boat to enter water terrain.

## Summary

Procedural generators are awesome. I really enjoy using them. They can easily give you random imagery or data that has some “hidden” rule in it. Just like maze generation with Cellular Automaton, here we procedurally generated a terrain map that can be used in a game.

The algorithm to generate the matrix is pretty simple and the outcome is really up to how you implement your coloring function.

Using `Path2D`

for user interaction and collision detection is also awesome. It makes the whole user interaction in a canvas so easy – just give me x and y coordinates, and I’ll let you know if it falls inside a path. You just have to generate your paths so they will fit your needs.

I hope you enjoyed this one! Would love to see if you can come up with cool maps, so feel free to fork the codepen and play around.

Thanks toÂ Omer DolevÂ from Microsoft andÂ Miki Ezra Stanger for their very kind and helpful review.

Featured Photo by Hans Eiskonen on Unsplash

Excellent explanation for the algorithm and it also produces quite nice terrain.

One small thing, the normalizeMatrix function does not (always) work properly because there can be negative numbers in the matrix.

It should be something like this:

function normalizeMatrix(matrix) {

const maxValue = matrix.reduce((max, row) => {

return row.reduce((max, value) => Math.max(value, max));

}, -Infinity);

const minValue = matrix.reduce((min, row) => {

return row.reduce((min, value) => Math.min(value, min));

}, +Infinity);

return matrix.map((row) => {

return row.map((val) => Math.abs(minValue – val) / Math.abs(minValue – maxValue));

});

}

Thanks for that!

That’s an edge case I should cover with tests I guess ðŸ™‚

Thanks again Stefan!