How to make limitless terrain for games in real time
Sections in this page
This is a description for game programmers of how I generate essentially limitless terrain for a simulation of the sport of orienteering which may be seen and explored at myforest.uk (The Forest, completely free). The terrain is not stored permanently as data. Instead it is generated by mathematical functions as the explorer or orienteer moves around.
There is an extended version of this page, including some program source, available as a PDF file (TerrainGeneration.pdf) to download from either grelf.itch.io/forest or github.com/grelf-net/forest. The PDF version gets more material added from time to time. The github site includes a working Explorer-only version of The Forest written in Java, with all sources available to download.
I first developed these techniques in the early 1980s when I had rather primitive versions of The Forest published for TRS-80, Sinclair ZX Spectrum, and BBC Microcomputers. In those days the program was written in assembly code but the present version (as at the URL given above) is programmed in JavaScript to run in any HTML5 graphical web browser, even on phones.
Ground shape: heights
The starting point is a rather arbitrary 1-dimensional profile of length 256 for which the data are stored as a literal array of integer values. Charted in a spreadsheet it looks like this:
The profile is a periodic structure (its last value and slope are very similar to its start). The array is indexed by the remainder of some number (p, say) when divided by 256 to get the height of the terrain. The number p is a function of the x, y coordinates of a point (x eastwards, y northwards).
height = profile [p % 256]
Performance is important here, so we do not want to be doing a modulus operation because that involves division. Instead a bit-wise AND is done:
height = profile [p & 0xff]
0xff is hexadecimal for decimal 255; I just write it this way to emphasise what is being done.
(If you look at the full JavaScript source you will see that a division by 128 is also needed in the height calculation. For speed, that is replaced by a multiplication by a constant set at the start: RECIP128 = 1 / 128;)
Recall that the number p above is a function of position. If p = 27y (no x-dependence), and the heights are multiplied by 5, and then heights below 204 are deemed to be lake, we get the very boring contour map shown here:
If instead p = 13x + 26y we get the equally boring contour map shown here, with the same pattern just lying at an angle:
But if we average those two patterns we begin to get something more interesting:
In The Forest there is an average of 5 such patterns in different directions, with this result:
The interesting terrain shape is therefore calculated by something essentially like this (but using a for-loop):
height = sumOverI
(profile [(a [i] * x + b [i] * y) & 0xff]) * RECIP128;
where a and b are arrays of parameters, declared as constants at the start of the program.
Notice that if the profile array were much longer but its length was still a power of 2 so that a bit-wise AND was still possible, it would make no difference to performance. Longer arrays could make for greater variety in the terrain: there might be flatter plains and sharper mountainous areas.
It is also important to note that although the initial profile repeats after 256 metres*, the fact that we are adding versions at various angles means that the resulting terrain is unlikely ever to repeat.
* 1 pixel on the map = 1 metre on the ground = 1 element difference in the profile array.
Height is calculated using the full floating point values for x and y, because the observer is not necessarily standing exactly on a whole-metre x-y grid and we want height to be as smooth a function as possible. The floating-point value of p interpolates linearly between adjacent elements in the profile array. Vegetation and point features (in the next sections) use only rounded integer versions of x and y, for speed.
The algorithm for drawing the contours was first described in 1987 in Byte magazine by Paul Bourke. His description can be found at http://paulbourke.net/papers/conrec/ . I have re-implemented the algorithm in JavaScript in a form that is most efficient for my map. It performs well. Every fifth contour is thicker, as is standard for orienteering maps, to help interpretation. Streams on the map (see below) also help to see which direction is downhill.
Lakes or islands
If the height is below a certain fixed value (204 in The Forest) there is deemed to be a lake. A rain feature was added in June 2018: the lake height slowly increases when it rains, reducing back to the original fixed value when the sun shines. (It is also possible for explorers to drain the lakes in order to find something at the bottom of one of them, if they can work out how and where to do this.)
A higher lake level also makes the ground break up into islands, which can be desirable for some games.
Lake level 450: countless islands in a limitless sea
Biomes (vegetation etc)
A similar summing of profile patterns is done for determining terrain types (thicket, moor, town, etc), using the same profile but different parameter arrays a and b. If the result lies within a certain range of values, the terrain is of a certain type. Because the parameter arrays are different the patches of vegetation do not follow the contour shapes but they have similarly irregular shapes:
The map is drawn as closely as possible to international orienteering standards (see https://orienteering.sport/iof/mapping/). White areas are runnable woodland (mature trees). Green is thicket, slower to penetrate or even best avoided. Yellow is open grassland but ochre is moorland which is slower to run across (all taken into account in the program). Arrays of black squares here represent buildings in "towns".
Point features on the ground
There are a number of different types of objects scattered throughout the terrain and located at specific (x, y) points. They include boulders, ponds, upturned tree roots, mine shafts (leading to systems of underground mines) and several other things. Whether an object appears at a given point and what kind it is, are also determined from the terrain profile. They have to be sparsely arranged of course.
It is vital that the determination of whether an object is present must use the rounded whole-number coordinates x and y, otherwise there would be an infinity of possibilities in every metre of ground. The essence of this part of the program is as follows.
xr = Math.round (x);
yr = Math.round (y);
xryr = xr * yr;
// Usual profile calculation but swapped a/b arrays
// to re-use them:
a = calcProf (b2, xr, a3, yr);
f = Math.round (a * xryr * RECIP128) & 0xfff;
if (4 === f)
{
xyff = xryr & 0xff;
if (xyff < 32) feature = MINE;
else if (xyff < 128) feature = BOULDER;
else if (xyff < 160) feature = POND;
else if (xyff < 200) feature = KNOLL;
else feature = ROOT;
}
else
if (8 === f
&& (Math.round (PI1000 * xryr) & 0xff) < 4)
feature = MANMADE;
else
if (16 === f
&& (Math.round (PI10000 * xryr) & 0xff) < 8)
feature = CONE;
in which an important constant declared at start-up is
PI10000 = Math.PI * 10000;
The code looks at bit patterns. To make the bits appear to be random, groups of bits are taken from a function that includes multiplication by π, mathematical pi which is irrational: it has an unpredictable sequence of digits (or, in base 2, bits). PI10000 shifts pi up so we are not looking at its first bits.
The testing of the value of f in the program above ensures that we only detect rarely occurring values and so the objects will be sparse across the ground.
There are several different images for each of the ground objects. The next section describes how any particular version is selected at a particular position.
Placing a mix of trees
There are trees in The Forest of course. They are loaded into the program as image files (from my own photos, cut out and saved in PNG format to allow transparency around them; transparency is shown by the chequered pattern here). To avoid monotony there needed to be several different tree images. Suppose there are four (in fact there are more than that). At each position on the ground one of the four is to be chosen, seemingly at random. At that position, whenever the user looks at it, maybe after moving away and coming back, it must always be the same tree out of the four.
This is achieved by calculating a pair of bits (2 bits allows 4 possible values) from a function of the x and y coordinates of each point. Just as was done for point features, to make the bits appear to be random a pair of bits is taken from a function that includes multiplication by π.
In JavaScript it looks like this:
treeSelector = Math.round (PI10000 * xr * yr) & 0x3;
A similar thing is done for the exact positions of trees within the square tiles that form the ground, so the trees do not lie always in dead straight rows. Once again, if the explorer comes back to any place, the same tree will be seen in exactly the same slightly offset position.
Placing buildings in towns
One of the "biome" types in The Forest is "town". In the main version of the program a town is a paved area with 12m square buildings placed on every position in which x and y are divisible by 16. So the buildings form a dense grid with alleyways 4m wide between them.
I have another version (not yet public) in which building placement uses a similar technique to that of the trees above: a repeatable pesudo-random function determines whether a building exists at a given (x, y) position in a town. A sample of the map can be seen here.
That pale blue patch on the hill-top is snow, another new feature in my newer version. I am also putting more variation into the buildings (again using repeatable pseudo-random seed values), as can be seen in this view which is from the point shown in the map:
Enabling things to move
The terrain object has a property placed which is initialised simply as a new Object (). Recall that in JavaScript there are two quite different ways of accessing the properties of an object: either as obj.propertyId or as obj ['propertyId'], like an array indexed by a string. Behind the scenes objects are implemented as hash tables. The property names as strings are hash keys, directly forming an address within the table (content-addressable memory). The point is that given a key we can very rapidly determine whether there is an entry in the table, with no searching involved. That is exploited here, using terrain.placed. The key (or property name string) is formed from integer (rounded) x and y ground coordinates. They are separated by a comma, so we test whether terrain.placed [x + ',' + y] contains a particular value. This is very fast and it does not involve preallocating an array for all possible x and y (which would be impossible anyway because the coordinates are unbounded).
Note that the comma in the key string has a dual purpose. Firstly it causes conversion of integers x and y to strings for concatenation (and slightly faster than 'x' + x + 'y' + y which I first wrote). Secondly it ensures that, for example, x = 123 and y = 45 does not produce the same key as x = 12 and y = 345.
This technique can be used to position any object at a required location or to indicate that an auto-generated feature has been moved, perhaps by the explorer. It does not want to be overdone because it goes against the initial principle of having auto-generated terrain. The technique has been used in The Forest to make helicopters stay where they land and not to be seen any longer where they started from. It has also been used to plant a self-moving mystery object on one of the tracks near the start.
Many programming languages have hash tables or maps, that can be used in a similar way.
Streams
Notice that the map is generated point by (x, y) point. There is no consideration of how neighbouring points may be related and therefore there are at first no linear features such as paths or streams. In fact it is much more difficult to generate a map containing such features. Only the vegetation boundaries or lake edges can be considered to be linear features. However I have recently (2020) added streams and paths.
Streams are created by testing the n x n neighbouring points around ponds (blue V on the map) to find whether any has a lower height than the pond. (n = 11 in The Forest.) If so, a stream extends to the lowest point in the neighbourhood. Repeat that process until either a lake or a hollow with no lower points is reached. The stream is described by an array of points, so its line can be drawn on the map.
There are still programming difficulties with streams, so I still consider them to be experimental: how to deal with streams coming from ponds lying outside the displayed portion of the map or the viewed portion of the scene. How far outside should be searched for such possibilities?
Paths
Automatically generating paths or roads is trickier. Unlike streams there is no rationality that can easily be automated for the directions they should take. In the real world they are created by people or animals repeatedly using a route they find useful. We cannot wait for a player to repeatedly follow a route in a game before turning it into a path.
The best thought I have had so far is that a line is an intersection between two surfaces. What surfaces do we have already? The contoured shape of the ground. So I have made experimental paths by putting paving slabs at every position that has the same height as another position some distance away, offset by a certain constant vector. This makes grey lines:
Underground (mines / dungeons)
One of the types of point features on the ground is a mineshaft. Explorers (non-orienteers) can fall down the shafts if they get too close. There is a layer of mines in a simple rectangular grid pattern. The grid squares are 16 metres across. The determination of whether any given grid square is open (as opposed to solid rock) is extremely simple. Just determine whether the fractional part of some function of grid x and grid y is above or below some threshold value:
// Is a mine open at this position?
// Must be if there's a mineshaft on the ground
Mine.prototype.isOpen = function (x, y)
{ if (this.isOpenAbove (x, y)) return true;
var u = Math.PI * 10000 * x * y;
return (u - Math.floor (u)) > 0.4;
// Note threshold value 0.4 - could vary to give
// different openness/connectivity
};
// There is 1 level of mines, so open above
// only if the ground has a mineshaft
Mine.prototype.isOpenAbove = function (x, y)
{ for (var ix = x - 8; ix < x + 8; ix++)
{ for (var iy = y - 8; iy < y + 8; iy++)
{ if (forest.terrain.terra (ix, iy).feature === MINE)
return true; }
}
return false;
};
Next is a tiny fragment of map of the mine level. The cells shown in red are below mineshafts. Although the user can move in any direction, just like above ground, cells are not connected diagonally. This fragment shows a complete connected mine with 2 access shafts. At top left there is also a small mine with only one shaft. I don't know how far the other mines around the edges extend or whether they are all accessible.
The mines could very easily be extended to 3 dimensions, with a z value as well as x and y. A simple demonstration of that is available at https://grelf.net/caves/cavefly.html and that program allows the connectivity threshold to be varied by the user.
Cave entrances
I have several times seen it written that height maps, such as I have described, cannot generate overhangs and therefore cannot have cave entrances. This is not true. I have shown how I determine that there are vertical mineshafts in some locations. If we examine the slope of the ground around such a mineshaft and find that it is steeper than some value it would not be difficult to portray a cave mouth instead, leading into a horizontal tunnel. The path of the tunnel can be determined just as in the previous section about mines. A 3D version could then easily connect sometimes downwards too, as already indicated.
A note about coordinates
Some 3D programs have x and z as the horizontal coordinates and y vertically. I think this is because they started with views from cameras, in which z is always a measure of depth. Objects at higher z are further from the camera and so are drawn first (the concept of z-buffer has been around from the early days of computer graphics). However, the scene being viewed is more naturally described by x and y for the ground and z vertically, so that is how my programs do it.
Further information
More details about The Forest, its history and how it is programmed may be found at https://grelf.net/ojsvg.html and on subsequent pages. Further information for programmers, such as how to get a perspective view of the terrain from any height and how to make more distant features foggy,can be found here...