To Infinity And Beyond
CSM
Ok last week I knew that, when introducing skybox on a reader's request, I completely ignored a key part to make sun light believable: shadows. I had implemented shadow for spot lights but I left sun shadow for another day as it is slightly more difficult.
Let's recap spot light shadows: we just render the scene from the point of view of the light and save the depth buffer which tells how far the light ray can go in each direction. Then when rendering from the camera's perspective, we can check for each render pixels if the light could "see" the pixel". This is relatively straightforward since anything that would block the light would be between the light bulb and the light radius.
This is from learnopengl.com, they explain it much better so click on image if you want to dive into it.
For sun shadow we have two issues that prevent us from using such a simple approach:
- sun light comes from "infinitely" far so there is no "rendering what the sun can see from its point of view" (the sun's camera would be infinitely far)
- usually sun light covers a large area of the screen, some being near the camera's position and some being far, so either shadow resolution would be bad near camera or GPU resource would be wasted far from camera
So the usual solution to those problems is to create N sun shadow maps using orthographic projections that cover slices of the view frustum:
- one for a small slice of what is displayed on screen near camera
- one for a bigger slice of what is displayed on screen a bit further from camera
- ...
- and a last one for the furthest slice of camera frustum
Those are called Cascading Shadow Maps (CSM). If you imagine camera's frustum in 2D, here is what it look like:
For each shadow map, we then figure the geometry that would be inside the view frustum slice or between the slice and the sun, and we render geometry just like with spot lights. Finally, once those shadow maps have been generated, and as we render fragments from the camera's perspective, we just have to figure which shadow-map should the fragment use and proceed just like with spot lights.
Here is a recap video where I show the camera frustum being divided in slices (yellow) and the sun's view cuboids (orthographic projections) used by each layer of the CSM (in grey), then display their content (blue is close, red is far). At the end I also show more in detail the transition between shadow map layers (loss of shadow detail, but it's far from camera).
Also, this was not straightforward at all, so you may spot I added a lot of debug to help finding rendering issues, such as ability to execute the rendering pipeline for a given camera but actually render from another camera. You can see for instance the frustum effect when this is activated: entities behind debugged camera disappear as they don't need to be rendered.
Chunk
So one of the main game mode I would like to start implementing will consist in driving on an infinite road generated procedurally (goal: TBD). The first step, even without any procedural generation, is to solve the issue of floating point numbers loosing accuracy as the car drives far from the world's origin. Here is the kind of errors that can happen:
To fix those issues, and without changing how my other systems work (they have to work in simpler worlds where this is not an issue, so all other systems must still work naively with simple 3D vectors for positions), I decided to implement a simple chunk coordinate system. The later keeps track of a target entity's position (probably the player) and, when it leaves the boundary of a chunk by a certain margin (we don't want to let player oscillate between chunks too easily), changes current world origin's chunk and moves every entities in the world accordingly. Ad-hoc systems (e.g. collision specific systems) may run just after to also "move" things that are not stored through entity's position component (e.g. collision triangles are stored in absolute coordinates).
The chunk coordinate here is just an arbitrary coordinate, there is no data associated to any chunk, it's really just a pair of integers stored to keep track by how much the world was offset. So far this work is somewhat engine-level: other game-specific systems will later take care of "unloading" entities that are too far from world's origin and "loading" entities getting closer. This simple pair of integer coordinates makes the world's limits virtually infinite but without hindering the physics and rendering precision of things happening near the player (let's be fair to Outer Wilds I unfairly criticized: this is exactly what they do! but in above video player goes far from solar system yet "looks at it" through the map so planets have been offset outside comfortable precision ranges for floating point numbers). Here, see top left corner, you can see the chunk coordinate changing as I drive around the map fairly seamlessly.
The camera jerks a bit, this is because I haven't yet properly managed interpolation when world is shifted.
Premises Of Procedural Generation
Generating Chunk Contents
Now that we know what chunk we are in, it is possible to generate entities (collider and 3d models) for an infinite road. As we detect that the world is offset to be centered around another chunk coordinate, we just have to destroy entities from chunks deemed too far from world's origin, and generate new entities for chunks that are now near player. I won't bore you with the details, this is really just about book keeping.
Procedural Generation
I think the more interesting thing is: how to generate a maze of roads that (somewhat) looks like a real road network. Ideally it is not a straight line, but at the same time the goal is to drive forever so I cannot let the road reach a dead end too easily.
Usually, procedural generation in "infinite" worlds is done using noise. It works especially well for continuous environments, variations of heights (mountains, oceans) or spread of resources (dirt, stone, ores, etc.), as there is no strong constraints between generated chunks (if some noise places a mountain next to a lake, then it's ok). Here is roughly how it works for minecraft:
Diagram borrowed from cybrancee.com, click on image for more details.
The huge advantage of such noise-based algorithms is that each chunk can be generated independently from every other.
However a road network comes with strong constraints: a road shouldn't bein or end out of nowhere as a new chunk is revealed, it should probably continue smoothly across chunks or properly connect to intersections. What this means is that generating a "believable" road network cannot be done by just looking at 1 chunk, we must also look at how previous chunks (ideally just nearby ones) were generated. Ideally I would still use noise as much as possible (because they require storing no data) but rely on another technique to ensure world's consistency. This is when I remembered about the Wave Function Collapse algorithm, popularized by Oskar Stalberg in Townscaper and simply explained in this video:
In short, and applied to my problem: we can imagine the world is a 2d grid of tiles of unknown state. As player discovers a new tile, we generate its type randomly (e.g. a road that connects the South and East borders of the tile) but while respecting constraints from neighbouring tiles already discovered (e.g. South tile was discovered and was generated with a road ending on its North border). Here is an example of what I generated with a simple implementation:
Off course this only dictates the overall layout of the world, where each cell is maybe 1km by 1km area: inside the cell we can now generate a road proceduraly, using simple noises (for instance to offset where the road starts exactly on its edge, the shape it has, loopings, jumps, etc.). This means only about a byte of data would be stored on disk per discovered cell (if we need to regenerate the same world exactly). And off course, as you may spot with the black and red colored roads, this still doesn't guarantee that an infinite road will exist (the road player drives on may end, and some roads may be generated but completely unreachable).
Shodown
Ok, I said all that, but already generating a "simple" straight but infinite road while not breaking everything was a challenge, so this is where I ended today (just imagine the Wave Function Collapse algorithm generates a long straight road, and then I use noise to generate smooth bezier curves). Enjoy:
You can watch while listening to this synthwave's track for more immersion.
Little bonus: I don't know if you remember when I talked about the complexity of finding good geometry separating planes for physics to run smoothly? when roads are generated procedurally it is very easy to find the perfect planes.