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.

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.

1. 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.
2. In each iteration:
   1. 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.
   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 – Square step in Figure 2.
3. 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

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

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

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

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.

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:

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:

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:

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:

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