Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
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:
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:
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):
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.
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.
