The Trouble with Streams (in generated terrain)

These images are extracts from screenshots from a program called The Forest. The scene is the view from the red circle on the map, showing where two streams meet and finish in a small marsh.

Some background

The program has limitless terrain generated in real time from a very small amount of code by an algorithm devised in 1982 for the first version of The Forest published for ZX Spectrum computers. The current version, available free at grelf.itch.io/forest, is written in plain Javascript to run in browsers. The map is drawn to international standards for the sport of orienteering. The program is partly a simulation of the sport to help with reading contours but also, for general users, a rather long treasure hunt.

How streams are generated and drawn

There is a PDF file on github describing how my terrain generator works, including sources in Java.

For present purposes you only need to know that the algorithm creates ponds in random but repeatable (x, y) positions. The map symbol for a pond is a blue V.

The displayed map is 800 x 600 pixels and shows a portion of the terrain which is 800 by 600 metres. Point features such as ponds can appear at whole-metre coordinates (but the observer is free to move anywhere, not just on metre-grid squares).

In plotting the map area whenever a pond is found the program determines whether a stream runs downhill from there. This is done by repeatedly finding the lowest ground height in a circular patch first around the pond and then around the end of the stream as it flows. The process ends when either the stream meets a lake or there is no lower surrounding point, in which case the end is shown as a marsh. There are two constraints: (a) there is no stream if it would be less than 10m long and (b) the stream ends in a marsh if its length reaches 300m without encountering a lake.

On the map extract above there are some ponds without streams and one stream ends in a lake. Streams are helpful in showing whether contours indicate downhill or uphill slopes.

When a stream has been found the program also marks positions along its route in a hash table to enable the stream to be shown in the scene display. (Hash tables enable quick look-ups without searching. More details in the PDF in the link above.)

There is a problem with that process

Displaying the map applies the terrain generation algorithm at 800 x 600 positions. On a decent Windows laptop (or on my Android phone) that takes about 1 second, including plotting the streams. But streams are only found for ponds lying within that area. Streams starting outside the map but flowing onto it are not shown. Streams have a maximum length of 300m but searching a 300m band around the outside of the 800 x 600 area would significantly lengthen the map plotting time.

A further consequence is that the hash table is not marked for such streams. In a very unlucky case a stream coming straight southwards towards the observer from just off the north edge of the map area would not be seen by the observer in the scene view. Fortunately the contours are convoluted enough that such a case is extremely unlikely. But what if the observer wanders a long way without ever looking at the map again? In that case some streams would not have been marked for showing in the scene but switching to the map and back again would make them suddenly appear. (In The Forest you see either the map or the scene and have to switch between them.)

My partial solution

Javascript is essentially single-threaded but it has had the capability of running "Workers" in parallel threads for a long time (I stick to long-time JS to be sure of running in as many browsers as possible). So I have written a StreamWorker to run in parallel to the main program, sending messages between the two processes. It has copies of exactly the same terrain and stream Javascript files as the main program.

Whenever the observer moves a message is sent to the worker giving the new (x, y) position. If the worker is not already doing so, it starts scanning like the map display would but over a wider area (by 300m on each side). Then whenever a stream is found its route is sent back to the main program for the coordinates to be marked in the hash table for display, if it is not already so marked.

The hash table continually grows. To avoid running out of memory a count is kept of the number of entries (as they are entered). At a certain (fairly large) size all streams are cleared and the worker starts again centred on the observer's position.

This ensures that the scene view will always show streams around the observer but it does not ensure that streams outside the 800 x 600 map area will be seen on the map. I consider this to be less important because such streams will be well away from the area around the observer.