Suppose, just for a moment, that you’re writing a program that allows you to explore a planet, similar to the Earth, but completely made up. The main problem in writing such a program would be generating the terrain of the planet- all the mountains, trenches, and everything in between. Sure, you could spend years modeling the entire landscape, meter by meter, kilometer by kilometer, but it’s much easier just to write a different program to automatically generate the terrain of the planet. (The former method, in fact, would take about 16 million years, even if you could create a square meter every second, without any breaks or sleep) It turns out that it’s possible to create very realistic landscapes, even by using methods which at first would seem to have no correspondence whatsoever with how terrain forms in real life.
First, however, it helps to simplify the problem a bit: Throughout this post, except when specified otherwise, we’ll be referring to a two-dimensional, square, array of heights, called a height map. Typically, this will represent a region of land, sampled at a constant interval in both the x and y directions, called the sampling rate. While this approach does have some deficiencies- for example, it is incapable of making caves, and it will look very strange if projected onto a sphere- there are ways of overcoming these, and in general it usually shortens the description of each method by a lot.
Anyways, the first algorithm you might think of would be to assign each cell in the height map to be a random value from, say, -1 to 1. It should be obvious to most readers, though, that this is a horrible algorithm and does not produce realistic results. It produces mountains and valleys, but the density of these features depends on the sampling rate of the map, and if the map was meant to represent a small area, such as a 1m by 1m square, it would look more like a spike pit than an actual piece of land.
A basic feature of landscapes, at least in mountainous regions, is that they go up, they go down, and it’s a bit rough in between. These qualities can be simulated using Brownian noise (a.k.a. “1/f” noise, a “random walk”, or a “drunkard’s walk”). Essentially, a random walk is created in 1 dimension by starting from 0, then repeatedly adding a random number (between -1 and 1). In other words, a random walk is created by summing 1D noise. While this does produce a good profile of a mountain range, there are two problems: There’s not an elegant way to extend it to two dimensions, and it, much like the random number approach, depends on the sampling rate of the map.
A further feature of mountain ranges is that they, to a certain extent, are self-similar. For example, one could view Mount Everest as a sort of “sub-mountain” of the land around it, and various localized peaks on Everest as “sub-sub-mountains”. With this in mind, it is possible to modify the algorithm for producing Brownian motion to display fractal behavior. Start out with two points, forming a line segment. Then, move the midpoint of each line segment up or down a random amount, forming two more lines per line segment. If you repeat this second step, having the random amount decrease exponentially with the number of iterations, you get a result which almost looks plausible.
Not only is fractal Brownian motion invariant of the sampling rate- given a fraction of the form p/(2^q), it is possible to deterministically evaluate the height function at that point, as long as you store or can recreate the random numbers generated- it can be extended to two and higher dimensions as well, although the generalization’s not the most obvious thing.
I’ll just describe the algorithm for fBm in two dimensions, also known as the Diamond-Square Algorithm, then show how to extend it to three or more. First of all, notice that the 1D algorithm for fBm could be framed as an interpolation scheme- first start with an array of length 2, zoom in and fill in the missing point (with a random offset) to get a array of length 3, then 5, 9, 17, 33, 65, …= . The Diamond-Square algorithm works in a similar way: Starting from an array of size by , we zoom in (enlarging each 2×2 square to 3×3) , and fill in the missing 5 points.
I’ve left out an important part in this description: The order in which you fill in the missing points matters. Basically, points on the edge of a subsquare don’t have at least 3 adjacent points to average from, but rather 2. The correct approach here is to evaluate the center points of the subsquares first, by averaging the 4 diagonally adjacent points and adding a random amount, then to determine the heights at the edges of the subsquares from the 4 (3 if on the edge of the heightmap) adjacent points. While this can sometimes be surprisingly tricky to implement, it generates landscapes of almost professional quality.
I say “almost” here because, as with most terrain generation methods, there are problems with it. Perhaps the most evident of these is that you can see “creases” on the final model where early subdivisions happened, which makes it seem artificial. Additionally, real landscapes simply don’t have infinite fractal detail. Natural processes, such as erosion, tend to cause land to not be self-similar at small scales. If algorithms such as the Diamond-Square method are run for too long, the result will begin to look like a strangely shaped Gothic cathedral, or the side of a buckled-in hull of a ship- not a map of a mountain range. I didn’t include that in the animation above, but here’s a picture of when the Diamond-Square method has run for too long:
The generalization of fBm to higher dimensions is similar to the generalization of fBm to two dimensions: Start with the center of the (hyper)cube, and work your way out to the edges. For example, in 3D you evaluate the centers of the cubes, then the face centers, then the edges.
The other widely-used method for generating random fractal landscapes is to use a sort of “smooth noise” developed by Ken Perlin sometime around 1983, after working on the original Tron movie. While it does rely on an interpolation function, Perlin noise adds separate functions together to create the final result. The basic idea is that mountains can be thought of as a waveform, composed of a large, low frequency wave, a smaller, higher frequency wave, an even smaller, even higher frequency wave, and so forth. To create a wave in Perlin noise, we first create a list of random numbers, then create an (often piecewise) function which interpolates between these numbers. There are many interpolation functions that you can use, but basically any one except linear interpolation on Paul Bourke’s “Interpolation methods” page should work just fine.
Once n interpolation functions, have been defined, 1D Perlin noise is just , where p and q are typically both greater than 1.
Interestingly, a special case of Perlin noise was discovered by Weierstrass in 1872, in a completely different context. Suppose that the random numbers generated were 1,-1,1,-1… for all i, and that cosine interpolation was being used, so that . Then we get Weierstrass’ function, , which is nowhere differentiable and which, not coincidentally, looks a bit like a mountain.
Perlin noise can be generalized to 2D and higher dimensions by simply modifying the interpolation function to first interpolate over the x axis, then over the y axis, and so forth. For example, in 2D, to interpolate over a rectangle with heights a, b, c, and d, . (Another way is to start with an image of random noise, repeatedly zoom into the upper-left quadrant (blurring the image as a result), then add all the resulting images together, with the noisier ones contributing exponentially less to the final sum)
As I mentioned in the second paragraph, way above at the top of the post, the height map simplification is incapable of making caves or overhangs, because height maps are defined to only store the amount of terrain that sits directly above each point- not where any vacancies might be. Clearly, this is a problem for games such as Minecraft, where overhangs are practically a part of the game mechanic. This problem is fixed by using a 3D height map instead, where positive values might mean that there is land at that particular location, and negative values mean there is just air there. However, simply populating a 3D height map with 3D Perlin noise won’t work- instead of getting a landscape with mountains and valleys,
you’ll get a bizarre structure with nothing much which could really be called a mountain or a valley, and with entire chunks of land just hanging in the air:
In short, Bad Things Happen. Lots of work goes into making 3D noise behave properly, and I won’t go fully into it since it could take up a whole other blog post. For Minecraft in particular, Notch, the former developer, posted some information about it on his blog.
Can Perlin noise be used in other ways than terrain generation? To quote Don Knuth, “Yes”. Whenever a source of noise which has some continuity to it is needed, animated or otherwise, Perlin noise is always an option. 1D Perlin noise can be used for creating inexact lines, 2D and 3D Perlin noise can be used for artificial textures, such as marble or wood or bumps, 3D noise can be used to create static smoke or clouds, 4D noise can animate it, etc. It’s used in most CGI software, and Perlin himself won an Academy Award for it. I should mention, though, that the computation time of Perlin noise grows exponentially with the number of dimensions. This lead to the development of Simplex noise, which is faster and alleviates some problems with Perlin noise. In short, it’s like Perlin noise, but better.
In addition to the fractal terrain generation methods listed above, there are many which rely on completely different approaches, and which may or may not be suitable for computer implementation. One objection to fractal terrain is that it is fractal- specifically, there’s no reason why fractal landscapes happen to approximate the authentic ones so well. Perhaps the most realistic approach to terrain generation is just to simulate the system of tectonic plates directly, and see what forms it creates. This has been tried many times (I’ve found examples dating back to at least 1996), with levels of computation time and success varying over many magnitudes. Just this year, Lauri Viitanen published a thesis describing how to simulate such a system, and the video published with it seems to show that the algorithm works. However, there are a few problems with it: It uses the Euler approximation to simulating a system, which is prone to “blowing up” or otherwise malfunctioning; The plates have to be broken up and given new velocities every few hundred steps, when in reality the plates are driven; and the algorithm has to start from a height map, even though new land is automatically created. (Additionally, I’ve tried several times to translate it into C#, but have failed every time- I either get a boring result, or a clear bug, such as bouncing or teleporting continents)
The analogy of mountains to waveforms can be transformed into a function another way: Instead of having the amplitude of each wave scale by p^(-f), where f is the frequency, we could modify it to use f^(-p) instead. Paul Bourke’s implementation goes like this: We populate an array with random numbers between -1 and 1, take the discrete Fourier transform (converting from (amplitude, time) to (amplitude, frequency)) , scale by , then take the inverse discrete Fourier transform to convert back to (amplitude, time). The result will be a terrain which is about as good as Perlin noise, but has one additional property: Because the discrete Fourier transform assumes that the function is periodic, the resulting terrain can be tessellated smoothly. Additionally, this approach allows for a much easier generalization to higher dimensions than either Perlin noise or fBm: To get an nD landscape, just use an nD array and an nD Fourier transform!
It’s very hard to map rectangles onto spheres without any deformation- in fact, it’s impossible. However, there are map generation algorithms which can be implemented on a sphere, such as Hugo Elias’ spherical landscapes algorithm: Repeatedly slice a sphere with a plane in random places in random directions, always moving the part of the sphere in front of the plane out by a small amount, and the part of the sphere behind the plane in by the same amount. There’s not really any problems with this method, other than that points can’t be generated without running thousands of steps of computation.
Lastly, there are some methods which have no reason to work at all. Bill Gosper, my mentor, has noticed that when certain curtains are hung in front of a window, the shadows caused by the windowsill create a silhouette which looks vaguely like a mountain range. Unfortunately, I don’t have a picture of this effect, but as soon as I find one I’ll post it here.
In conclusion, there are a wide range of algorithms available for creating fake landscapes, many of which are quite imaginative and yet work well.