I promised a look at generating 3D terrain procedurally, and now I’m delivering. This time around, we’ll look at the diamond-square algorithm, a kind of 3D extension of the midpoint displacement method we saw before.
Diamond-square is another way of generating fractal terrain, and it has been popular for a couple of decades. Old terrain generators like Terragen used it, and new programs continue to make use of this classic algorithm.
How to do it
Now, on a line segment, it’s easy to find the midpoint: just average together the ends. For a 2D plane (the source of our 3D heightmap), it’s not that much harder. But a simple midpoint displacement, as we did before, can cause severe “creasing” effects that render our terrain very unnatural, very obviously made by a computer. We don’t want that. That’s where the diamond in diamond-square comes in, as well see.
First things first, we need an array of points to represent our map. This can be as big as you like, but an array of size 2^n^+1 works best (in other words, something like 129, 257, or 1025). If you use that, then the highest index of the array will be 2^n^, and the midpoint 2^n-1^. Very easy to work with, especially once we get into the recursion. As before, we stop when we reach the bottom, which would be when we’ve run through every pixel. (If you’re paying attention, you know this makes diamond-square O(n²). Don’t worry, it’s not as bad as it seems.)
Like 2D midpoint displacement, we need a set of initial endpoints. Since we’re working with a 2D plane, we require 4 of them, one at each corner. We’ll average these together at the midpoint (the exact center of the map), and give the result a little nudge up or down, just like last time. This is the “diamond” step; if you look at the illustration on the Wikipedia page linked above, you’ll see why it’s called that.
Next comes the “square” step. We’ve got five points: 4 corners, 1 midpoint. This creates four diamonds (though we’ll sometimes have to overlap them). For each of these, we want to find the center of that, and displace it by a random amount. In coordinates, for a map of size 2n+1, our “square” center is at (n,n), and the “diamond” centers are (0,n), (2n,n), (n,0), and (n,2n).
We’ll repeat this process as long as necessary, alternating ever smaller diamonds and squares. Each time around, we’ll lower the range of our random displacement to make things smoother. At the end, we’ll have a full heightmap, with every point being at an elevation relatively close to the average of its neighbors. In other words, not too many sharp drop-offs. It looks somewhat natural, although I’ll admit that grayscale diamond-square heightmaps tend to resemble clouds to my eyes. Put them in 3D, though, and they look a lot better.
Tricks and traps
As with 2D midpoint displacement, diamond-square displacement has one major knob to tweak: smoothness. It works the same here as there: the less range given to the displacement, the smoother the resulting terrain.
But we’re working with a world now, so there’s more to it than that. One thing that most terrain generators allow is a “sea level” setting. One height is chosen as sea level, and everything below it is underwater. With a high sea level, the effect is something like an archipelago of volcanic islands sitting in an ocean. Lower values create the sense of mountains and valley lakes.
On the downside, diamond-square isn’t immune to the creasing mentioned above. The alternating diamond and square steps are meant to spread it around, but they don’t get rid of it entirely. However, a bit of post-processing can help with that, if it’s too much of a problem. (Or you can always say it’s natural, that your terrain really is sitting on a geological fault.)
The biggest disadvantage of any random displacement algorithm is its randomness, and that’s a lot harder to remove. If you’re procedurally generating terrain for a game, for example, and you use this method, you’re stuck with it. You can’t even change the RNG, because that will give a whole new set of values from the world seed. (This is not limited to purely random generation, however; any algorithm change will render old worlds obsolete. It actually happened with some early versions of Minecraft. To name one prominent example, the map used for the Achievement Hunter Let’s Play series is nearly impossible to recreate because of changes to the generator.) Your options there are limited. Either never, ever change the algorithm, or find some way to keep the old versions in the code for compatibility.
If you can live with those caveats, then procedural generation isn’t a problem. But there’s far more to it than simple randomness. In a later post, we’ll look at more predictable methods of content generation. These have the advantage that they’re easily reconstructible from a seed—as long as you use the same algorithm or sequence of them—so you still all the same benefits of procedural code. And they’re also more amenable to something other than terrain generation, as we shall see. Until then, whether you’re making maps or psychedelic images, have fun!