This article explains in some detail how I generate terrain in The Forest (www.myforest.uk) as the player moves around. I discovered the techniques around 1980 when making games for a TRS-80 with only 16 kilobytes of memory available. In 2014 I began converting my old Z80 assembler to HTML5/JavaScript.

The starting point is a 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. 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]

If p = 27y (no x-dependence), and the heights are multiplied by 5, and then heights below 204 x 5 are deemed to be lake, we get the very boring contour map shown as Figure 2.

If instead p = 13x + 26y we get the equally boring contour map shown as Figure 3, with the same pattern just lying at an angle.

But if we average those two patterns we begin to get a more interesting map as shown in Figure 4.

In The Forest there is an average of 5 such patterns in different directions, with the result shown in Figure 5.

It is like a snapshot of an interference pattern between 5 irregular waves passing through each other in various directions.

Notice that if the profile array were much longer, to give greater variety, and its length was still a power of 2 so that a bit-wise AND was still possible, it would make no difference to performance.

If the height is below a certain fixed value (204) there is deemed to be a lake. A rain feature was added to The Forest 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.

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 parameters are different the patches of vegetation do not follow the contour shapes, as seen in Figure 6.

Height is calculated using the full floating point values for x and y, because the observer is not necessarily standing exactly on the whole-metre x-y grid and we want height to be as smooth a function as possible. Vegetation and point features use only the integer parts of x and y however.

The existence of a point feature (boulder, pond, etc) at a given position does also involve the profile. Then a relatively simple function of x and y is tested for certain values within a range of bits.

This method of generating terrain does not permit vertical cliffs, overhangs or caves. (If you put a step in the profile you will find that multiple instances of it run right across the map, in 5 directions.) That is why one of the point features available in The Forest is a mineshaft (shown on the map by a black V - there are several on the small example above). Explorers can fall down such shafts and discover a limitless network of mines (or dungeons, if you like). These are generated by an even simpler algorithm which I explain elsewhere.

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 no linear features such as paths or streams. In fact it would be much more difficult to generate a map containing such features. Only the vegetation boundaries can be considered as linear features. One of the aims of The Forest is to help orienteers learn to navigate by using the contour information, so the absence of paths to follow is considered to be a good thing. Making the contours form narrow continuous lines was not so easy and I explain that elsewhere.

As of version 19.2.19 of The Forest some tracks have been placed on the ground but these are not generated automatically. Instead a test version of the program has been used to set a series of (x, y) ground points manually. These are then used as the vertices of a path in the usual graphics sense. A new file road.js defines a Road as a list of points and the map can then use a draw () method of a road object. More interesting is the way the road is embedded in the terrain. The terrain object has a property placed which is initialised simply as a new Object (). Recall that in JavaScript there can appear to be 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 (aka 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 the 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). What really happens in the buildroad () function in road.js is (a) that a Road object is constructed containing the list of ground positions, for the map, and (b) the lines along that list are traversed to set terrain.placed [x + ',' + y] for every integer position within a certain distance of the line. Then scene.draw () can discover which ground tiles need to be shown as road (or track).

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.

The same technique could 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 The Forest in having auto-generated terrain. The technique has been used to make helicopters stay where they land and not to be seen any longer where they started from. It has also been used (19.2.23) to plant a self-moving mystery object next to one of the tracks, an object which may see more action in future versions.

Here is a view of a tiny part of my generated terrain, as seen from a point 30m above ground, and the relevant section of map: