I recently became interested in trying some procedural terrain generation – for fun. All the information I could find on the web was a bit overwhelmingly technical for me, having never done anything like this before. So I wrote this post about how I wrapped my head around it. Maybe it could help you out if you’re a bit stuck too!
The diamond-square algorithm is an algorithm which generates arguably some of the most realistic heightmaps, especially in terms of speed and ease of implementation.
It works by performing two stages over and over, the square stage and the diamond stage. After every square stage, you half the area in which the stages are performed (I’ll explain more about this later).
The diamond stage is the easy one. To put it simply, you grab the colour of the four corners, average them, add a little randomisation, and finally, you plot the point in the middle!
The square stage is also fairly straightforward, but it can get a little confusing to implement depending how you do it. The concept is nearly identical to the diamond stage, except rotated 45°.
This time, you grab the colours from middle of the sides, rather than the corners. Once you’ve got the average of these four points, you plot a point in the middle of them… like last time.
There are a few exceptions that make it a bit trickier. For example, at the edges of the canvas, half of the diamond is missing outside the boundaries. There are two solutions; you can either wrap it (grab the out-of-bounds point from the opposite side of the canvas. This allows you to create a tileable heightmap which is great for games on a tight memory). The other approach is to simply ignore the fourth, non-existing point, and just average the three points you’ve got.
This whole thing might sound a bit overwhelming to a newbie, but actually, it’s very simple. The easiest way to go about it is to create a bounding box. You will perform all of the steps inside this bounding box.
To start, set the size of the bounding box the same as the canvas (513,513 lets say). After you have performed both the diamond and square stage INSIDE the bounding box, chop the bounding box in half (now it’s 256,256).
Next, you perform the diamond stage inside the bounding box four times. Each time you perform the stage, push the bounding box to the right. When the bounding box goes too far, reset it on the x-axis and push it down. Eventually (or rather quickly in this instance), the bounding box will go too far downwards. When this happens, you start the same process with the square stage. However, the square stage is a little bit more awkward, the bounding box isn’t moved quite as simply. I created a gif to allow you to visualise how it all works below.
Finally, after the square stage, you half the bounding box again and start again. Rinse and repeat until your bounding box becomes smaller than 3×3, by which time; all the points will be filled! Excellent!
Just to clarify, something that I didn’t understand at first; the third and fifth stage are the square stage even though it looks like they’re creating diamonds. I had this misconception and it had me scratching my head for a while when I first tried implementing my own version.
Useful information that I didn’t mention:
- Reduce the factor of randomisation every time you perform a square step, otherwise your small details will be extremely bumpy.
- If the bounding box movement is too confusing for the square stage, you could just as easily use the same sort of movement from the diamond stage. You would have to grab the points from outside of the bounding box, but that’s actually extremely simple.
- If you decide to wrap the off-canvas points on the square stage, you should plot all edge points identically onto the opposite side. This reduces seams or creases between the tiles, you can remove the duplicate sides afterwards by cropping the overall canvas size by 1 pixel width and height.
If you’re running into problems implementing your own diamond-square algorithm, leave a comment or send me an e-mail and I’ll try my best to help!