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
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
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.