Tag: procedural

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!

So I’ve been talking in the abstract about procedural generation. Now, let’s get to something solid. In this post, we’ll look at one of the most basic methods of “terrain” generation out there. (I use the scare quotes here for a very good reason, as you’ll soon see.) The technique is called midpoint displacement, and it’s a fairly simple method that can give sensible results…if you know how to use it.

The easiest way to demonstrate the algorithm is in two dimensions. That’s for a couple of reasons. First, lines are easier to visualize than planes in a medium like this. Two, heightmaps take longer to construct, and they’re harder to tweak. So instead of making actual terrain (i.e., an area of simulated land), we’ll make a line-art representation. Think of it as a cross section if you like, or the beginnings of a 2D scroller’s background.

Onto the algorithm itself. You start with a blank surface (a straight, horizontal line, in our case). Take the midpoint of that surface and move it up or down by a small, random amount. Now you’ll have two lines meeting at an angle. That might not look very terrain-like, but, at this stage, it’s not supposed to. The trick with midpoint displacement is that it’s recursive. For each of these line segments, do the same thing as before: move the midpoint by a random amount. Keep going as long as you want, either until you’re bumping up against resolution limits or you reach some predefined level of detail.

The end result is an increasingly “fractalized” line that begins to look less artificial and more like something that could come from natural processes of erosion and the like. The more subdivisions you do, the smoother the finished product will look, like so:

The above image shows midpoint displacement, with an increasing number of subdivisions. At the top, we have 1, going up to 10 at the bottom. (Note that these are separately generated images.) By the bottom, we’re starting to see something that doesn’t look too bad. You can go farther in your own code; I used Inkscape just for illustration, and 10 is the highest setting it has.

Using your imagination, you might be able to see how this could be interpreted as terrain. It’s a very rugged terrain, though, and that comes from the other tweakable parameter. Remember how I told you, at each step, to move the midpoint a little in either direction? Well, how far you move it determines how rough the generated terrain becomes. This is the smoothness factor.

In general, midpoint displacement works best if you decrease the range of movement at each subdivision. Otherwise, you get wild swings that don’t look at all natural. The “default” assumption is that each step has half the range as the one before it, but changing the smoothness affects this; smoother generation requires smaller variation.

Interactive tools to visualize midpoint displacement aren’t hard to find, and code samples are almost as easy, so we’ll leave off here for now. Later, we’ll look at expanding this idea to a three-dimensional world, where we can truly see the effect of terrain generation.