Site logo, www.grelf.net
 

How to make limitless terrain for games in real time

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.

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 aribitrary 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) so 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.

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.

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. Vegetation and point features (in the next sections) use only the integer parts of x and y however.

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.

 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.

 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 can be considered as 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.

 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:


// 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;
};

// 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 
};

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 this allows the connectivity threshold to be varied by the user.

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

Next page