In a few of my demos I’ve used 2d terrain. I love the effect and its really easy to do especially in 2d. The algorithm I use most is Diamond Square also known as Midpoint Displacement. What’s great about the algorithm besides its easy of use is that it can be used for simple 2d terrain as well as with 3d terrain. For now I will just be talking about generating 2d terrain, in a future article I will discuss how to use the same algorithm to make create height maps that can be used in turn to create 3d terrain.

Im going to use JavaScript and the canvas element for my examples but the principles can easily be applied to any language or rendering technology.

The method I will be describing is midpoint displacement. Its one of the simplest algorithms in my opinion when it comes to making good looking 2d procedural terrain.

## A Brief Overview of How it Works

For Each Segment Divide in half and average the middle point add a random value to the mid point reduce the random range Repeat Until segments are too small to continue.

## A More in Depth Explanation

First we assign a random value to the outer edges of our terrain. This can be anything from 0-1 or 50-100. The value itself is dependant on the system you want to use for plotting. We then need to get the center point of the segment. Once we have the center we calculate its value by averaging the two points and adding a random value to it.

So now that we have our 3 starting points we move onto the next step. The next step is exactly the same as above. As you can see we have 2 segments, so we get the center of each segment and add the average of its edges plus a random amount. We then need reduce our random range for the next iteration.

Now we have four segments so all we need to do is cut each segment in half again, average the center values add our random value and reduce the random range.

As you can see the more iterations creates more realistic terrain. Lately it seems like none of my articles can be complete without an animated gif, so here is one animating the process.

## How much do I reduce the random range?

From now on I’ll call this roughness. How much do you need to reduce it by each iteration? Well that all depends on how you want your end result to look. The greater the reduction the less jagged your hill’s will be. So if you want more of a rolling hill appearance you would to reduce the value at least by half every iteration, however if you want more jagged mountains you don’t want to reduce the value very much at all. Below is an example of terrain using two different values for roughness.

The following JavaScript function is what I used to create the above examples.

/* * width and height are the overall width and height we have to work with, displace is * the maximum deviation value. This stops the terrain from going out of bounds if we choose */ function terrain(width, height, displace, roughness){ var points = [], // Gives us a power of 2 based on our width power = Math.pow(2, Math.ceil(Math.log(width) / (Math.log(2)))); // Set the initial left point points[0] = height/2 + (Math.random()*displace*2) - displace; // set the initial right point points[power] = height/2 + (Math.random()*displace*2) - displace; displace *= roughness; // Increase the number of segments for(var i = 1; i < power; i *=2){ // Iterate through each segment calculating the center point for(var j = (power/i)/2; j < power; j+= power/i){ points[j] = ((points[j - (power / i) / 2] + points[j + (power / i) / 2]) / 2); points[j] += (Math.random()*displace*2) - displace } // reduce our random range displace *= roughness; } return points;

In my code I also use a value called displace. This is just to control the maximum distance a point can go this is so II can keep it inside of the canvas area.

## Wrapping Terrain and Scrolling

Using this algorithm makes it easy to create wrapping terrain, in order to do so you just set the two initial starting points to the same value.

There are a few ways to create scrolling terrain. In my codepen for example I cheat and just pop and push the points on the array itself which makes the wrapped terrain scroll. However a better approach in my opinion is to use two sets of values and just move them based on an offset. Once the second half reaches the edge of the screen reset the offset to 0 copy the second array to the first, and generate new terrain for the second array, passing in the seed. Below is a fiddle of how I personally achieve the effect.

Well that was a lot of information. Would you believe there is an even simpler method to creating 2d terrain than that? I’ll go over that in my next article.

THanks, explanation was picture perfect.I am going through the code, and understanding it slowly,but i got stuck in this line

“power = Math.pow(2, Math.ceil(Math.log(width) / (Math.log(2))));”

can you explain me whats the math behind this???i don’t follow the comment line too which says “Gives us a power of 2 based on our width”..so can you give some more specific??

Suppose you wish to mark the midpoints of a line of width 64 cm recursively, i.e. half of 64 and half of the 2 new segments and so on.. now we know that this can be done indefinitely. But on a screen a width 512 implies pixels. And hence midpoints can be found only in integral units. Now for a line of 64 to divided into integral units, the maximum number of divisions is 6 (power) as 2^6 = 64. In this case we know 2 and 64.. but how do u find 6 ? log (64) to the base 2! The ceiling function is used to get an integral power..

[…] reuse it someday. In a few lines of code you can create endless number of terrains. Check out this excellent post by Loktar for more […]

Very good article with a very interesting result . I was wondering, in the end of your post, you mention something about a simpler method in your next article…did you still write an article about that or not? I dont seem to find it 🙂 Thanks in advance

Where is your second article on this? Thanks!

[…] Vielen Dank an Jared Counts für die Idee mit dem zerstörbaren Terrain welche wir in C# portiert haben destructible pixel terrain Und ebenso danke an Loktar für den Algorithmus zur generierung des Terrains, welchen wir ebenfalls in C# portiert haben. terrain with midpoint displacement […]

[…] Special thanks to Jared Counts for the idea of the destructible terrain which we ported to C# destructible pixel terrain Also thanks to Loktar for his algorithm to generate terrain which we also ported to C#. terrain with midpoint displacement […]

If your width is not a power of 2 (e.g. 256, 512 etc) you get some funky effects. Upside-down mountains in the sky.