Terrain Generation is something that feels far into the future, but I believe it’s good to discuss about the architecture we are going to use already from now.
@HyperbolicHadron has already raised the issue here and some technical details have already been discussed, though the exact architecture of these systems have been a bit of a closed-source black box for years, as of today. I believe the whole thing should be kept fully transparent in each step to ensure the technical feasibility and playability of the system.
In this discussion, I want to propose my infrastructure for terrain generation, inspired by @HyperbolicHadron’s work and some of my past experience with these systems.
The problem of realistic Terrain Generation
In Thrive we want to generate realistic terrain while accounting for both hydrogeological and tectonic effects and constraints, and possibly extraplanetary effects like meteorites. Terrain generation is already a computationally expensive process, and adding these other layers of simulation is inevitably incompatible with the real-time processing required by the gameplay.
The proposed solution
This problem can be overcome by separating terrain generation in two major steps: a Mapped Terrain Pipeline that runs in real-time and an Unmapped Terrain Pipeline that runs between evolutionary epochs, e.g. before (or after) editor sessions, like auto-evo.
Mapped Terrain is terrain data that has already been generated. It consists of both heightmap and voxel data (in a signed distance format) that is stored in a file cache on the disk and memory-mapped for fast I/O. The Pipeline runs in real-time and its responsibility is to compute create both terrain mesh and physical shapes on-the-fly. This data could be stored in a GIS format (as suggested by HyperbolicHadron). Most of this data resides in the RAM, but if the player decides to travel a lot during a single session we need to make swapping terrain chunks possible, as long as they are generated. Later in this post we will discuss what happens if the requested chunks are still unmapped.
Finally, mapped terrain is static, meaning it’s not editable nor it does evolve during the gameplay. This is an extremely important optimization as it keeps the pipeline snappy and fast. Actually, limited terrains edits will still be theoretically possible with local SDF functions.
Unmapped Terrain is terrain data that is yet to be generated. This involves the heavyweight pipeline that has to generate the terrain and store it in heightmaps and SDF textures. The pipeline consists in a multi-step algorithm that, roughly:
- Computes tectonic plates;
- Computes noise;
- Computes erosion.
The less expensive step here is the noise computation, as it can be heavily parallelized and accelerated by SIMD instructions.
Both pipelines can be definitely GPU-accelerated, but since we offer the OpenGL fallback, the CPU version of this must be implemented.
The algorithms
Here’s the algorithms I propose for terrain generation and meshing. These are industry standards and result from years of research.
Noise
Godot offers the FastNoiseLite library to generate noise. This is a deterministic, fast, SIMD-accelerated library that supports many noises in both 2D and 3D. These can be combined to generate already realistic terrains without even erosion and plate tectonics. It will also be useful to produce biomes and weather maps. FastNoiseLite is also available as a shader library which allows us to run it on the GPU if we wish to accelerate the generation process.
Data structures and SDFs
Heightmaps alone can be used to keep the terrain data, but it will be interesting to have caves, 3D cliffs and similars in the game. This requires representing data in 3D images locally using SDFs. This allows us to blend heightmaps with 3D features easily with the following equation:
SDF(x,y,z) = H(x,y)-y-D(x,y,z)
Where H(x,y) is the heightmap and D(x,y,z) is the SDF of the 3D terrain features.
Meshing
There are a few optimized algorithms that turn SDFs into meshes on-the-fly, supporting LODs and LOD stitching. One of these is the Transvoxel Algorithm.
Simulating plate tectonics and global weather
Having raster maps all over the world is a massive storage problem: it could take gigabites for a single world and a lot of compute. We obviously want to avoid this. Non-mapped areas can be stored in memory for tectonic and climatic calculations by subdividing the planet sphere with a voronoi tiling. This easily reduces the data usage and the compute bandwidth by 6 or 7 orders of magnitude while giving a good compromise in the quality of the results.
This is is roughly what Azgaar’s Fantasy Map Generator does.
The Non-Euclidean Problem
We are discussing an intrinsically non-euclidean problem and giving an euclidean solution. This is wrong. Mapping a sphere on a plane is not topologically possible, but we can project the sphere on a cube. Of course, locally, a sphere (and any manifold) is euclidean, so terrain generation is roughly unchanged and probably needs no (or very little) correction. Globally, we obviously need to remember that planets are spheres and that they have positive gaussian curvature.
The Continuity Problem
Suppose we spawn in a point A of the world, and we start exploring. Then we change to point B, a hundred of kilometers away from A. The world generation of these two points is likely to be disconnected, meaning we probably have an unmapped gap between the mapped areas of A and B. Now, suppose the player wants to travel from B to A during the game. Since the unmapped area wasn’t generated, it has only been approximately simulated. This leaves a discontinuity between the generated areas, which is probably impossible to stitch or smoothen. Therefore, I suggest keeping the playable areas on the planet isolated and find a way to prevent the player from doing this. Traveling for hundreds of kilometers is obviously kinda extreme, but we need to consider this. One possible solution is to have a transition screen, e.g. a message saying
You are attempting to travel from B to A. Do you really want to?
And if yes, get teleported to A.
The Architecture
I propose having a TerrainServer that wraps the pipelines and serves mapped chunks on-demand, acting as an Abstraction Layer on top of the machinery and as a reliable API. This manages generation and meshing. Then, each stage has a TerrainSystem acting as a Communication Layer between the simulation and the server, and keeps all the terrain data.