Procedural midpoint displacement

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.