Site logo, www.grelf.net
 

The Forest - program design

This page documents important aspects of the deign of the software of The Forest, a simulation of the sport of orienteering. Further documentation from the user's point of view can be found here. It would be useful to have read that explanation and tried the program before reading the current page.

I want to encourage creative programming and I am keen for others to have access to this information so it will not be lost at some future date. If others wish to develop the ideas further or use them in other works, then I approve. A reference back to me would be appreciated.

 Some conventions

 A note about geometry

Computer graphics inevitably involves some geometry. The diagram on the right covers most of what is needed here. This shows a right-angled triangle with sides x, y and d. An observer at O (not necessarily the origin of the coordinate system) may be looking at a point P distance d away on a bearing of b degrees. If the diagram looks unconventional it is because in map work using a compass we use bearings measured clockwise from due north (the y-axis) wheras in maths the convention is that angles are measured anticlockwise from the x-axis (due east).

In JavaScript the formulae are as follows, where I have included the essential conversions from degrees to radians.

x = d * Math.sin (b * Math.PI / 180);

y = d * Math.cos (b * Math.PI / 180);

d = Math.sqrt (x * x + y * y);

The conversion factor Math.PI / 180 should NOT be calculated every time it is needed but done once beforehand and set to a constant for multiple re-use: this is an important general principle for speed.

You may also need to get b from x and y:

b = Math.atan2 (x, y) * 180 / Math.PI;

Do always use Math.atan2() instead of Math.atan() because the latter cannot return an unambiguous value in the full 360° range. And for the smart-eyed, yes that is atan2 (x, y) and not the other way round: check the diagram; it is because we are using bearings again.

 Programming notes by file

 forest.html

This is the single web page for the program, in HTML5. All of the user interaction occurs here but it is kept as simple as possible. All CSS is kept in a style element in the head because there is not very much of it. All JavaScript is loaded from files by script elements in the head. The names of the JavaScript files are changed every time they are modified, by a 1- or 2-character suffix. The script elements here must therefore be altered every time a new script version is to be uploaded. The server is set to tell browsers not to cache the HTML but all other resources may be cached.

The main action occurs in a canvas element, so it assumed that the user's browser is sufficiently up-to-date to recognise that. The canvas is initially set to 800 x 600 pixels and that gives a reasonable drawing speed for the various views. The ordinary 2D graphics context is used by the scripts, so that they should work on all platforms (so we do not use WebGL, for example).

The information and controls available on the page change as the program is used. This is done by having unique id attributes on several of the HTML elements and then using

document.getElementById ("an_id").innerHTML = "new content";

 forest.js

This script acts as an interface between the HTML and the other scripts which are all object-oriented (this one is not). It handles events such as button clicks, drop-down selections and keypresses. For touch-screens (tablets or smart phones) the only gestures recognised by the program are taps which appear as mouse click events.

Generally the event handlers call methods of relevant objects in the other scripts to carry out the required actions.

This file contains an initialisation function, init(), which is invoked by the onload event of the HTML page. This function creates the principal objects for the program: one each of screen, terrain, map, scene, observer and plot3d. It adds relevant event listeners to the canvas. It also calls function loadCourses() in course.js which will load any courses which had been created by the user in a previous run and put in local storage.

init() then calls the map object to draw itself. It is important that the map is drawn first, to give time for the images to download which are required for drawing a scene.

 screen.js

This small script has a constructor for type Screen which gets the size of the canvas and a reference to its graphics context, for all other scripts to use.

It contains methods for direct access to pixels in the image displayed on the canvas.

 observer.js

One object of this type is constructed by the init() function in forest.js. It repesents the orienteer standing on the ground, with x and y position coordinates in metres and a bearing in degrees clockwise from north. Given those 3 values it is possible to calculate everything that can be seen ahead: see scene.js.

The constructor of the observer object creates 2 properties which are arrays of sines and cosines at integer degree values from -360 to +360. Looking up these values is quicker than calculating them every time (verification). The negative range saves time worrying about negative values when angles have been subtracted.

An observer also has a role, initially the general one of explorer. If the user changes this to be an orienteer there will be a course object selected for the observer too. Actions available and whether control markers are seen depend on the role.

 terrain.js

One object of this type is constructed by the init() function in forest.js. This is almost exactly the same as in the original forest dating from the 1980s, simply translated from Z80 assembler to 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 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.

height = profile [p % 256]

p is obtained essentially by summing various multiples of x and y (though it is slightly more complicated than this):

p = sum (a [i] * x + b [i] * y)

Effectively this is adding together several copies of the profile at different amplitudes and various angles in the x-y plane. This is analogous to a Fourier series where a number of sine waves are added at different amplitudes and phases to create the shape of any desired function.

If the height is below a certain fixed value there is deemed to be a lake.

A similar thing is done for determining terrain types (thicket, moor, etc), using the same profile but different parameters 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.

Height is calculated using the full floating point values for x and y, because the observer is not necessarily standing exactly on the whole-meter 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.

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 a good thing. Making the contours form narrow continuous lines was not so easy and we consider that in the map section.

 map.js

One object of this type is constructed by the init() function in forest.js.

The map is drawn by a relatively simple scan of the canvas area. For each (x, y) position the terrain type, height and any point features are found by calling the terra method of the terrain object. The complications in the process are as follows.

MORE TO COME

 scene.js

One object of this type is constructed by the init() function in forest.js.

The constructor of the scene object initiates loading of the image resources. The images are in the PNG-8 format using transparency. Images are rectangular but the area surrounding a tree is transparent, for example.

Drawing the scene (the draw method of this object) involves first scanning a square area around the (x, y) position of the observer. Objects out to a predefined range (initially 60m but alterable by the user in the HTML) are to be drawn, so a square of side 2 x range + 1 metres is scanned. The results are held in an array called "around". As the points are scanned a check is done against the bearing of the observer, to find out whether each point lies within the visible angle, 45° either side of straight ahead. But because objects close to the observer but out to an angle 70° either side can affect the view, we really mark all points within the +/- 70 degree angle as being potentially ahead and these are all held in an array called "ahead" this array includes the view angle and distance of each point.

This diagram represents the 2D array called "around" in the case when the visible range is only 10 metres. The observer is at the centre, so the array has dimensions 21 x 21 (= 2 x range + 1). Clearly the size of the array goes up as the square of the range and computation time increases correspondingly. The blue dot in the centre of the diagram represents the observer and the thick blue line is the facing direction, in this case on a bearing of 120° (clockwise from north). The dashed lines either side represent the angle covered by the scene view, 45° either side of the facing direction. The solid thin lines are 70° either side. The centres of the red cells are outside the circular range and therefore need not be considered further.

Note that although the blue dot is shown in the centre of the central cell, the observer does not have integer coordinates. It cannot because it can move by fractions of a metre in any direction. Rounded versions of the observer's coordinates are used as the basis for the square array.

The white and green cells in the diagram all get a reference to a ScenePoint object stored in them, containing the following information.

Each green cell potentially affects the scene and a reference to the same ScenePoint object information is appended to the 1-dimensional "ahead" array as each green cell is encountered.

Importantly, the "ahead" array is then sorted in descending order of distance (so that the most distant points come first). The ScenePoint prototype includes a method for defining the sort order. The scene can then be drawn from the back towards the observer so that nearer objects can automatically obscure farther ones.

The "around" array is kept because it maintains the spatial relationship between neighbouring points: given x and y we can easily look up around [x + 1][y] for example. There is no such relationship between adjacent entries in the "ahead" array. This spatial relationship is needed when we come to tile the ground (next paragraph) and also to draw point features that are more than 1 metre across: knolls, mineshafts and pits; for these we need to mark the positions around their centres so that trees do not grow out of them.

Having sorted the "ahead" array we can start using it to draw, from the most distant points forward. First the whole scene is filled with sky colour. Then at a given point, several things are drawn in succession:

One of the neat things about the standard 2D graphics context is that the drawImage() method not only takes parameters for where to place the top left corner of the image but also the required width and height, scaling the image very efficiently to fit. In our case there is a scale factor (fscale) formed from the distance of the point from the observer which is applied to every item that is drawn. So distant tiles, trees, etc are scaled down very effectively without my program having to do very much.

A tile is drawn about every point for which both the x and y coordinates are odd. That is why the ScenePoint objects created during the scan around the observer contain a boolean indicating this fact. We use the "around" array to find the 4 neighbouring points (for which x and y are both even). We then get the distance and heights of those 4 corners of the tile. A method called getScreenXY() then does the perspective calculation to get the screen coordinates of each corner. A closed path is then created and filled to draw the tile.

When drawing trees and other features there are (or will be) several different images for each type of object, to give some variety in the scene. They are pseudo-randomly selected, by which I mean that although the selection appears to be random it will always be the same at any given (x, y) position. So if you see a particular kind of boulder at a certain spot it will always be the same type when you revisit. Equally, the variety of tree at any given spot in a wood remains the same as you move about. This is achieved with a variable called variant, created like this:

var variant = 0x3 & Math.round (this.PI10000 * x * y);

this.PI10000 is set as a constant property of the scene object when the object is first constructed. It is Math.PI x 10000 but we do not want to do that multiplication every time we want to use it, so it is set up first as a constant.

The digits of pi have no predictable pattern to them and so they can be considered for our purposes to be random. pi x 10000 simply shifts the digits up by a few places so there are several before the decimal point: 31415.926... Multiplying this by both the x and y coordinate values results in a new pattern of random digits but a pattern that is always the same for any given x and y. The final part of the formula for our variant is a bit-wise AND with the number 3 (written as a hexadecimal number simply to emphasise that a bit-wise operation is being done). In other words we look at only the least significant 2 bits of the integer part of the result of the multiplications. This can have 4 possible values: 00, 01, 10 or 11 and so we can select one of 4 image variants to display. If at some stage there were to be more than 4 images for boulders (or whatever), this could be modified to look at 3 bits (8 possibilities) by ANDing with 7 instead of 3.

A very similar thing is done when positioning a tree on top of a tile: the method getOffsetScreenXY() offsets the position by a pseudo-random amount within the tile before calculating the screen coordinates for the image. This is to ensure that trees are not always in dead straight rows.

MORE TO COME

 scenepoint.js

Many objects of this type are constructed during the drawing of the scene, and then discarded again. These objects are simply records containing values found in the square area around the observer, as described for the scene object.

These objects also have a method which defines the sorting order in descending order of distance.

 marker.js

One of these objects is constructed for every point feature found when drawing the scene ahead. It may or may not be displayed, depending on the role of the observer.

Each control on a course also has one of these marker objects.

A marker has an (x, y) position and a two-letter control code. It also knows how to draw itself as a standard orange and white orienteering flag with the control code on it. If the observer's role is course planner, markers also display their positions on the flag, to help programmers make courses.

The code is determined by the terrain object whenever a point feature is found. The two letters are from an alphabet as letter numbers x % 26 and y % 26. (% is the modulus, or remainder, operation in JavaScript).

 control.js

A control is part of a course. It has a marker plus an (x, y) offset for showing its number beside it in a suitable position when the course is overlaid on the map. This offset has 2 small shortcomings:

 course.js

MORE TO COME

 timer.js

MORE TO COME

 plot3d.js

One object of this type is constructed in by the init() function in forest.js.

MORE TO COME

 point.js

This is a convenient object to construct to help geometrical calculations, mainly because it contains a useful method to get the distance between this and another point.

 

 Verifying look-up speed

I wanted to verify my statement that looking up sines and cosines is faster than calculating them. It seems obvious but is it true in the browser JavaScript environment?

I found out that calculating (including conversion from degrees to radians) takes about 6 times as long as looking up. So it really is worthwhile pre-calculating trigonometric functions when possible.

The code I used for verifying this is below. I called it at the end of the constructor for the observer. There are a few complicating factors to take into account:

  1. It is necessary to put the results in arrays rather than assigning to a single variable because the JavaScript Engine (JSE) might be able to optimise the assignments away and just do the last iteration of the loop.
  2. The arrays must be pre-allocated, otherwise timings will include memory management operations as the arrays get bigger.
  3. The calls to Math.random() are also to avoid the JSE noticing that exactly the same operation is being done every time, so it can be optimised away.
  4. Then we should check how long the random calls take.

JSEs are now very clever at optimisation and of course that is why so much detail can be shown in The Forest in real time.

var N = 1000000;
var i, j = new Array (N), k, l = new Array (N), s, t0, t1;
var deg2rad = Math.PI / 180;
t0 = new Date ().getTime (); // ms
for (i = 0; i < N; i++) 
{ j [i] = Observer.prototype.SINDEG [Math.round (67 + Math.random())]; }
t1 = new Date ().getTime();
var dt1 = t1 - t0;
s = "Look up: " + dt1 + "ms<br/>";
t0 = new Date ().getTime ();
for (k = 0; k < N; k++) { l [i] = Math.sin ((67 + Math.random()) * deg2rad); }
t1 = new Date ().getTime();
var dt2 = t1 - t0;
s += "Calculate: " + dt2 + "ms<br/>Ratio: " + (dt2 / dt1) + "<br/>";
t0 = new Date ().getTime ();
for (i = 0; i < N; i++) 
{ j [i] = Math.random(); }
t1 = new Date ().getTime();
s += "Random: " + (t1 - t0) + "ms<br/>";
document.getElementById ("results").innerHTML = s;