Majority of empiric algorithms is based on observations from fractal geometry, mainly that surfaces with some so called fractal dimension look very similar like terrain. For its generation we can therefore use some method for generating surface with given fractal properties.
The simplest (and most used) algorithm is one of midpoint displacement methods (see [1], [3]). The principle of the simplest one (and the worst) is that height field with square shape with heights prescribed in the corners only is divided into four square parts. We must therefore generate five new (random) heights. After they have been generated we apply this process recursively on parts that have just been created. These methods work with height field as well as with TIN. Their advance are simplicity, speed and quite good results, drawback is that computation is dynamic (it is impossible to simply compute height above one point). They work well for generating rough, jointed terrains.
The second often used method is approximation with trigonometric polynomials (Fourier synthesis), see [1]. Using some rules we generate coefficients for sin and cos functions, by summing Fourier series we get height of one point of terrain. If we want to know all heights in the height field we can use fast Fourier transform (FFT). Advance of this method is removal of some artifacts present in midpoint displacement methods (e.g. creasing, ie. it is visible how the terrain was generated), drawback is much bigger time requirement. Property of such generated terrain is its periodicity, it can be both an advance or a drawback. It is better to use this method for generating smooth, old terrains.
Last mentioned method is functional synthesis, extension of previous method, see [2], [3]. If we want to hide that functions sin and cos are perfectly smooth, we have to sum big number of such functions. When we use another functions, more visually complex, number of summands need not be so large. Very suitable for this purpose are noise functions, for example Perlin noise, see [2]. On the other hand, we loose the advance of using FFT.