# Diamond-square algorithm

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-square algorithm visualised in a 5×5 grid by each stage. First, plot four points (random or user defined) and then proceed to the diamond step. It is important that the canvas is a power of two, plus one. (65×65, 257×257 etc…)

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).

I’m generally bad at explaining things, so I made you a gif.

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.

The squares and diamonds highlighted.

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!

• januz

This is one of the best explanations about the DS algorithm I’ve seen on the web. Specially the little gif and graphs. A lot of writers overlook how useful they can be. I checked the video that you posted on your projects page and I’m impressed at how little spikes you get. Even when reducing the randomness divider. My terrains look more hedgehog than terrain, did you add any special smoothing, pre-seeding or changes to the algorithm?

Thanks!

• grub

Hi januz!

First of all, thank you for your kind words! I haven’t been active on my blog recently and Disqus didn’t notify me, so I apologise for the really late response.

It was a long time ago that I wrote the code, and I can’t locate it currently. However, if I recall correctly, I ran into the hedgehog problem you describe and managed to eliminate it with (unfortunately quite extensive) debugging. In my case, I believe the problem was my randomisation was tending to be positive (upwards) more than negative, however the problem can arise from other small nuances such as rounding issues.

To debug, try removing all randomness in your algorithm temporarily aside from the generation of the first 5 points. Is the output surface smooth (curving to a single point like a circus tent)? If so, then that’s good, and it’s probably an issue with randomness. If it’s not, then it might be a rounding issue or some problem with picking the surrounding points (i.e. grabbing a point a mere pixel away of where it should be etc).

I implemented the algorithm as is, and as far as I recall I didn’t make any particular changes (certainly not ones that would be likely to remove this type of artifacting if it were inherent in the algorithm itself).

Best of luck!

• januz

Hey, thanks for replying. I’ve had issues with Disqus notifications in the past too. I didn’t think about rounding errors, I’ll look at that. I got it working mostly right with gaussian randomization (from python’s random package) and a “box filter” that only smooths peaks.

Cheers!

• tash

Hi Owen. Thanks for this post! I’m writing a report on diamond square algorithm, and I found your clarifications really useful. I would like to cite this blog post as a source, but I can’t find your full name anywhere on your blog. Would you just like me to credit “Grub”?
Thanks,
Tash

• grub

Thanks Tash, I’ve added my full name to the ‘About’ page now. Glad you found this post useful!