# What is the simplest method to generate smooth terrain for a 2d game?

What is the simplest method to generate smooth terrain for a 2d game like "Moon Buggy" or "Route 960"?

I got an answer at stackoverflow.com about generate an array of random heights and blur them later. Yes, it's quite okay. But it would be better to give some points, and get a smooth curve.

One way you could achieve this the following:

• Create a point in the middle of the screen, with a random height; you now have two sections, one on each side of this point
• For every section, divide into two placing a point in the middle of this section, with (ranged) random height between its two neighbours
• Repeat n times.

What happens is detail in the scenery gets finer with each iteration.

How you handle boundary cases is up to you: you could assume points at (0,height/2) and (width,height/2) for instance.

Hope this helps!

EDIT: Here is a picture I made for illustration: This is the same idea!

Assuming that you want an actually smooth terrain, I'd suggest stepping back from the noise-based answers and understanding where they come from. A 'noise' signal is essentially a sum of infinitely many sinusoids of random amplitudes, with the 'average' amplitude at a given frequency given by a function of the frequency f. You can get most of the common 'noise' definitions this way. For instance, Brownian motion has a 1/f^2 frequency response (that is, the average amplitude at a given frequency is inversely proportional to the square of the frequency): this means that nearby points have a fair bit of correlation with each other, since the high-frequency components of the signal are heavily damped. By contrast, the classic fractal noise (midpoint displacement, Perlin noise, etc.) has a 1/f frequency response; there's more variance between nearby points, but still quite a bit of correlation. Going a step further, white noise has a constant frequency response - there's no correlation at all between any points.

What good does this do you? Well, you can get a smooth signal that still has a bit of a noisy look to it by just summing a handful of sinusoids but making sure that they have an appropriate amplitude at any given frequencies. You want the frequencies to be 'random' so that no two of them will have a common multiple (otherwise you'll get a periodic component to the overall shape of your hills), so I'd suggest something like the following procedure (complete with working example):

1. Choose 4 (real) numbers at random in the range [1..10] - these will be the frequencies of your sine waves. I 'rolled the dice' at random.org and got: f0 = 1.75, f1 = 2.96, f2 = 6.23, and f3 = 8.07. There's nothing magical about the number 4 (you can use more, but using any fewer will start to make the individual sine waves more obvious) or the range 1 to 10 here (it'ss just a way of making sure that your highest and lowest frequencies aren't too far apart). It might make sense to choose one frequency in the range [1..2] and the rest in the range [2..10] just so that you have a known 'dominant' sinusoid.
2. For each of these four (or however many) frequencies fi, choose an amplitude ai somewhere in the range between -C/fi and C/fi for some constant C. The value you choose here controls the overall amplitude of your wave - for convenience's sake, I picked C = 1. Then I needed random numbers in the range [-1/1.75 (= -0.571) .. 1/1.75 (=0.571)], and similarly in the ranges [-0.338 .. 0.338], [-0.161 .. 0.161], and [-0.124 .. 0.124]. Rolling the dice four times again, I got a0 = -0.143, a1 = -0.180, a2 = -0.012, and a3 = 0.088 . (Note that this probably isn't quite the best way to do this step - since the maximum possible value of the function is the sum of amplitudes abs(a0) + abs(a1) + abs(a2) + abs(a3), it might make more sense to divide each of your four ai values by this sum once you've generated them, and then multiply each one by C so that you can be sure the precise maximum the function can attain is C.)
3. Pick four 'offsets' oi, each in the range [0..2π] (0..6.28) - these will tweak the starting points of your waves so that they don't all begin at 0. I got o0 = 1.73, o1 = 4.98, o2 = 3.17, and o3 = 4.63 .
4. 'Plot' the function f(x) = a0 sin(f0 ( k x + o0)) + a1 sin(f0 ( k x + o1)) + a2 sin(f0 ( k x + o0)) + a3 sin(f0 ( k x + o0)) - here k is another constant, one that controls the horizontal 'stretch' of your functions. You'll have to figure out what this is for your own application; for convenience I just picked k = 1, and so my overall function is f(x) = -0.143 sin(1.75 (x + 1.73)) - 0.180 sin(2.96 (x+4.98)) - 0.012 sin(6.23 (x+3.17)) + 0.088 sin(8.07 (x+4.63)).

Here's the result of my example run, as plotted in Wolfram Alpha - note that it fixes the size of its graphs for display purposes, but that you should have plenty of control over the horizontal and vertical stretch of the result via the constants I mentioned above: The midpoint displacement algorithm can generate beautiful 2d terrain. There is subtle different between midpoint displacement and what @tykel is suggesting. Tykel's algorithm subdivides the horizon and picks a new height. This creates terrain where the peaks are uniformly spaced. Humans are great at picking out regularities, so the generate terrain will seem generated, not natural.

Midpoint's power comes from picking the midpoint then displacing along the normal of the that line. This causes the peaks to vary up and down as well as side to side. The resultant terrain is fractal, and humans perceive fractals as natural.

Random height displacement could result in a descent terrain if you threw in a couple more parameters (horizontal displacement, maximum slope, etc). This highlights another of MPD strengths; it is very simple to tune. Two parameters, bumpiness and level of detail.

You can use noise functions to generate random heights. The simplest of them is value noise, which works exactly like your description: you generate some random integer heights, and then interpolate heights between them. The most-often used interpolation method is cubic S-curve mapping:

Suppose you have height h0 at point x0 and height h1 at point x1. Then to obtain height at any point x (x0<=x<=x1), you use

t = (x-x0)/(x1-x0); // map to [0,1] range
t = t*t*(3 - 2*t); // map to cubic S-shaped curve
h = h0+t*h1;


Heights obtained in this way will be smooth, random, but not really interesting. To make your terrain better, you can use fractal noise. It works like this: suppose you have generated a function h(x) that returns height at a given coordinate (using the method above). This function has a frequency, determined by frequency of original interger heights. To make a fractal out of it, you combine together functions with several frequencies:

fbm(x)=h(x) + 0.5*h(2*x) + 0.25*h(4*x) + 0.125*h(8*x);


In this example, I combine four frequencies - original, double, 4-times and 8-times original, with higher frequencies given less weight. Theoretically, fractals go all the way to infinity, but in practice only a few terms are required. The fbm in the formula stands for fractional Brownian motion - this is the name of this function.

This is a powerful technique. You can play with frequency multiplier, with weights of different frequencies, or add some functions to distort noise. For example, to get more "ridged" feel, h(x) can be changed to 1-abs(h(x)) (assuming -1<=h(x)<=1)

However, while all this is nice, this technique has a serious limitation. With a "heightline" based approach, you can never have terrain "overhangs". And I imagine them to be a very nice feature to have in a "Moon Buggy"-like game.

Adding nice overhangs is a difficult task. One thing that I can think of - you can start with a fractal "heightline", and "tessellate" it into a series of splines or bezier curves. Then the terrain line will be defined by several "key points". Apply some jitter to these key points - this will result in random deformation of the terrain, probably forming some interesting shapes. However, terrain self-intersections might become a problem with this approach, especially with high jitter amounts.

There are two popular methods for generating terrain height maps.

Some answers given here are already based on the Diamond-square algorithm, but knowing the name makes it easier to search for more information. Perlin noise has other uses as well, so it's good to check it anyway.

• The OP is talking about 2D, mario-style landscapes, but still these are good links. – tenpn Apr 13 '11 at 7:34

My idea would be to create a smoothed noise function. First with a method intNoise(int) which return a "random" int, but wich depends on the input. If you use the same input twice, the result will be the same.

Then use a smoothing method to make a floatNoise(float) which uses the two integers around the input to build a random value.

Then use the X position as the input and the Y as the output. The result will be a smoothed curve but with random height.