Tessellated multi-layer height map

This post describes a method for storing a very large landscape for a game world.
A height map is the conventional method for representing topography in game environments. A height map is essentially a monochrome bitmap in which darker colours represent greater heights. This means the landscape architect can draw it easily in conventional bitmap editing tools, and it’s easy to convert into a three dimensional map which can be rendered, just by drawing vertices between adjacent points in the grid. However, if you use a height map for a game territory, then either you have a fairly constrained territory or else you don’t have much complex topology. I want a territory of at least a million square kilometres - that’s four times the area of Great Britain or three times the area of Germany.

Having topographical features only at the kilometer scale - a one thousand by one thousand array of heights - would produce a wholly unnatural landscape. Having topographical features on the metre scale would produce a much more natural landscape, but at the cost of a million by a million array, which pushes the storage capacity of current generation machines and thus leaves much less storage for the many other things I want to model.

One solution, if a height map is chosen as the preferred representation of topology, is to tessellate the height map. The problem with that is that sooner or later the player is going to think ‘I’ve seen this same landform before somewhere else’.

However, it isn’t necessary to generate the whole map at once, and it isn’t necessary to generate the whole of the visible part of the map at the same resolution. Landscape close to the player’s viewpoint needs to be rendered at full resolution, of course. Landscape further away can be generated at progressively lower resolution: the far blue distance can afford to be generated at a very low resolution.

Stacking tessellations

Suppose one has a height map at the kilometer scale and tessellates onto it, additively, further heightmaps at the hundred metre, ten metre and one metre scales. Suppose each of these heightmaps is one thousand by one thousand. Then the same landform will never repeat, exactly, anywhere on the map, and the perturbations at different scales will make it extremely difficult for the user to recognise the repeating features. The actual height map used at each scale could even be the same height map, meaning that only one thousand-by-thousand array need be stored. 

But equally, not all the maps used even at a given scale need be the same map; provided that the north and south, and east and west, edges match you could use several different maps at each scale, repeating them according to some seeded pseudo-random algorithm, so that each time a user visited the same location he would see the same topography, in exactly the same way as he would see the same buildings and the same vegetation without our needing to store the exact building models or vegetation models between visits.

Drainage and erosion

Additive heightmaps mean that water courses won’t naturally always take the same path across each repetition of the same heightmap at any scale. But watercourses naturally change the landscape; they cut into landforms, eroding their banks. The greater the volume of water and the faster it flows (gradient), the greater the erosion. Furthermore, erosion is modulated by the hardness of the underlying rock. So either a complete watercourse map needs to be computed and stored, obviating the storage benefits of the tessellated height map, or else a water course map must be recomputed at run time for areas in the view of the user. In principle this is possible; in practice it would be necessary to experiment with how compute-intensive this proved to be.

Rainfall

Rain falls primarily on the windward side of high ground. Areas to leeward of high ground see less rainfall, and, broadly, the more high ground there is between the ocean and a given location in the direction of the prevailing wind, the dryer it’s going to be. Large areas of forest perturb this somewhat, but not to a degree I feel I need to worry about.

Either a rainfall map at a kilometre resolution can be hand drawn, or else automatically derived from the kilometre-resolution height map either at compile time or at run time. There’s no point in worrying about rainfall at less than the kilometre scale. Supposing we store eight bits of rainfall information. Then on each ten metre square we drop an amount of rain between 0 and 255 units. These units run downhill from square to square across the one-metre grid, creating a path. as streams converge, nodes on the path will be decorated with a traffic score - the number of units of rain that have passed through that node. That score gives the size of the watercourse at that point. Finally, a set or rules determine how the adjacent height map should be modulated to represent erosion. 

Deriving topography from tessellated height maps

Suppose one said, for simplicity, that each unit on the height map at the one kilometre scale represented ten metres, each unit at the hundred metre scale represented one metre, each unit at the ten metre scale represented ten centimetres and each unit at the metre scale represented  a centimetre; and further suppose we stored our heightmaps at one byte per cell resolution. Then we would have a vertical resolution of 2560 metres + 256 metres + 25.6 metres + 2.56 metres = 2844.16 metres, which is slightly more than three times the height of Mount Everest, which means we certainly have enough vertical resolution. However, it also means that high altitude landscapes would be no more rugged than low altitude landscapes, and, frankly, natural landscapes aren’t like that.

So, suppose instead we convert our values into a 32 bit unsigned integer height value as follows: the byte from the kilometre scale map forms the most significant byte, followed by the byte from the 100 metre scale map, followed by the byte from the ten metre scale map, and last the byte from the metre scale map. That gives us a value between zero and four and a third billion We’d have to divide that number by five thousand to bring it down to a metre scale which gave us the height of Mount Everest, and still we’d have the issue high altitudes would be no more rugged than low altitudes. 

However, if we raise the number we first thought of by a power - say, for convenience, we squared it, although I think it would take some experimentation to discover the exact power which gave the most satisfying landforms, and I’d further hazard a guess that it would be between 1.5 and 1.7 - and then divided the result by a constant to bring it back to plausible values to render, we’d get landscapes that were increasingly rugged with altitude, which is what I want.

Thus to be able to render the topography of a landscape from the viewpoint of the user, you’d compute vertices at metre scale for the cell the user is in and the adjacent cells on each side (so that you don’t need to compute new vertices in a panic when the user crosses a cell boundary). As a background task, you compute at metre scale vertices for cells which the user might visit soon. A ring of cells greater than one cell from the user, but less than about four cells from the user, you compute vertices at ten metre scale only. Beyond about four cells you compute vertices at one hundred metre scale only, and beyond about ten cells you either compute vertices at kilometre scale only, or else you compute flats. Obviously the exact numbers depend a little on the size of the cells, and whether (for rendering purposes) the cells are rectangular or (as I still rather prefer) hexagonal.