Virtual worlds have made leaps and bounds since the days of text-based adventure games and side-scrolling platformers. As computer hardware advances, designers are forced to come up with creative ways to model the complex things we see in the real world without sacrificing speed and efficiency. One long-standing problem is the question of terrain, and the best way to represent massive, varied and fully explorable landscapes in three dimensions.
Games like flight simulators and first-person shooters face this difficulty when they have to imitate the huge scales of the real world. What do they do behind the scenes to show the player fine, close-up detail while also not neglecting things far away on the horizon?
A brute force approach might just create one large grid to cover many square miles, consisting of equally spaced points sitting very close together. The heights of these points could then be offset using some elevation data, and that's it - you've got a large, high-resolution chunk of land which shows the same detail everywhere you look.
This could work for very linear games where sections of the world can be loaded and discarded as the player follows their path, but it gets excessive when we want to provide openness, and let the player roam around at will. So if we can't model all of our landscape at the resolution we want, how do we still make it convincing?
The answer is adaptive level of detail. We need an intelligent system which doesn't just draw the existing terrain, but re-builds it according to the player's movement. A common example of such a system is the quadtree.
When applied to this problem, a quadtree can be used to store, create and destroy small sections of the world dynamically. This provides nearby detail where it's needed while allowing things to be simpler much further away. The terrain can still consist of a single grid-style mesh which covers a large area, but the difference this time is that the structure isn't fixed.
So how do we take this abstract idea and break it down into something we can implement? Well, a quadtree is defined mostly by the nodes it holds. The diagram above shows the nodes as squares which seem to cascade down and quadruple across different levels, much like the branches of a tree might. Are you starting to see how the quadtree gets its name?
In our case, a node can simply be a small tile of terrain which isn't very useful by itself, but when duplicated at different scales, can build up a much larger world. The simplest node could be four vertices placed in a square, but for flexibility we'll extend this to be a square grid which has the same number of vertices along each edge.
Now that we know how our node looks, we can take its structure and add some logic to let it change depending on where the player is located. But what exactly should it do? Well, let's imagine that the player is sitting a few feet above ground level in the north-west section of a single root node whose sides are two square miles across.
Since we've decided our node structure is a sparse grid of, let's say 5x5 vertices, we clearly need more add more detail to make the landscape around the player look authentic. How about we take the root node and give it four child nodes, each of which covers a quarter of the original?
Now, instead of one four-square-mile grid, we've got four one-square-mile grids, which together will provide four times as much detail. This is a good start, but it's still unlikely it'll be enough given how close the player is to the ground.
The important thing here is that each child node we created is exactly the same as the root, only a quarter of the size. This means we can apply the same logic recursively, once again splitting any nodes close enough to the player into four children of their own. Perhaps this time, only the root's north-west child needs a higher level of detail; the others could be far enough away that, from the player's point of view, they already represent the terrain well enough.
This process can continue until the player is surrounded by child nodes whose sides may only be a few feet in length. These would be bordered by a group of nodes twice as large, and so on. When the player moves, we can loop over all nodes in the quadtree again, and decicde which should split and which should merge their children so that the detail moves to where it's needed.
Once implemented, this idea alone can give us a fairly good terrain model without needing any further tweaks. In practice though, there are a few more loose ends to tie up. One problem is the noticeable cracks that appear where a small node meets the edge of a larger neighbour. Because of the mismatch between the vertices at these boundaries, we need to think about rearranging some of the offending nodes' triangles so that we can enforce symmetry.
There are a few ways of doing this and I won't go into detail, but one thing that's common to most of the methods is that every node needs to know about its direct neighbours (if they exist). Neighbour finding should be done for all nodes whenever the quadtree changes, and can be handled using a set of conditions which check where a node sits within its parent.
Now that we've sorted out node splitting and neighbour finding, we've got all the building blocks we need to create a smooth, continuous landscape at any scale. All we have to do is place a single root node to cover the whole area, and be sure to update it with the player's position whenever they move. The recursive logic can then take over and refine the mesh where the detail is important, while keeping things simple and efficient further away.
There's no reason why we can't create a world which, in theory, stretches off to infinity in all directions by shifting the position of the root node so that the player doesn't ever get close to its edge. Another approach would be to have multiple root nodes which move around to ensure that the horizon stays far enough away. Coupled with a continuous noise function to generate the contours of the land, we can create trillions of unique environments, all of which start with something as simple as a square grid.
This has been a quick introduction to the concept of adaptive terrain which uses a quadtree to control level of detail. I wrote this article as a high-level description of something I've actually put into code over on my GitHub page. These C#/XNA classes contain all the algorithms for building nodes, splitting and merging children and finding neighbours so if you're interested in digging deeper, please go and take a look.
I hope this has been useful in helping you understand how a small part of many modern games is put together, and good luck if you decide to go world-building by yourself!
Games like flight simulators and first-person shooters face this difficulty when they have to imitate the huge scales of the real world. What do they do behind the scenes to show the player fine, close-up detail while also not neglecting things far away on the horizon?
A brute force approach might just create one large grid to cover many square miles, consisting of equally spaced points sitting very close together. The heights of these points could then be offset using some elevation data, and that's it - you've got a large, high-resolution chunk of land which shows the same detail everywhere you look.
This could work for very linear games where sections of the world can be loaded and discarded as the player follows their path, but it gets excessive when we want to provide openness, and let the player roam around at will. So if we can't model all of our landscape at the resolution we want, how do we still make it convincing?
The answer is adaptive level of detail. We need an intelligent system which doesn't just draw the existing terrain, but re-builds it according to the player's movement. A common example of such a system is the quadtree.
When applied to this problem, a quadtree can be used to store, create and destroy small sections of the world dynamically. This provides nearby detail where it's needed while allowing things to be simpler much further away. The terrain can still consist of a single grid-style mesh which covers a large area, but the difference this time is that the structure isn't fixed.
So how do we take this abstract idea and break it down into something we can implement? Well, a quadtree is defined mostly by the nodes it holds. The diagram above shows the nodes as squares which seem to cascade down and quadruple across different levels, much like the branches of a tree might. Are you starting to see how the quadtree gets its name?
In our case, a node can simply be a small tile of terrain which isn't very useful by itself, but when duplicated at different scales, can build up a much larger world. The simplest node could be four vertices placed in a square, but for flexibility we'll extend this to be a square grid which has the same number of vertices along each edge.
Now that we know how our node looks, we can take its structure and add some logic to let it change depending on where the player is located. But what exactly should it do? Well, let's imagine that the player is sitting a few feet above ground level in the north-west section of a single root node whose sides are two square miles across.
Since we've decided our node structure is a sparse grid of, let's say 5x5 vertices, we clearly need more add more detail to make the landscape around the player look authentic. How about we take the root node and give it four child nodes, each of which covers a quarter of the original?
Now, instead of one four-square-mile grid, we've got four one-square-mile grids, which together will provide four times as much detail. This is a good start, but it's still unlikely it'll be enough given how close the player is to the ground.
The important thing here is that each child node we created is exactly the same as the root, only a quarter of the size. This means we can apply the same logic recursively, once again splitting any nodes close enough to the player into four children of their own. Perhaps this time, only the root's north-west child needs a higher level of detail; the others could be far enough away that, from the player's point of view, they already represent the terrain well enough.
This process can continue until the player is surrounded by child nodes whose sides may only be a few feet in length. These would be bordered by a group of nodes twice as large, and so on. When the player moves, we can loop over all nodes in the quadtree again, and decicde which should split and which should merge their children so that the detail moves to where it's needed.
Once implemented, this idea alone can give us a fairly good terrain model without needing any further tweaks. In practice though, there are a few more loose ends to tie up. One problem is the noticeable cracks that appear where a small node meets the edge of a larger neighbour. Because of the mismatch between the vertices at these boundaries, we need to think about rearranging some of the offending nodes' triangles so that we can enforce symmetry.
There are a few ways of doing this and I won't go into detail, but one thing that's common to most of the methods is that every node needs to know about its direct neighbours (if they exist). Neighbour finding should be done for all nodes whenever the quadtree changes, and can be handled using a set of conditions which check where a node sits within its parent.
Now that we've sorted out node splitting and neighbour finding, we've got all the building blocks we need to create a smooth, continuous landscape at any scale. All we have to do is place a single root node to cover the whole area, and be sure to update it with the player's position whenever they move. The recursive logic can then take over and refine the mesh where the detail is important, while keeping things simple and efficient further away.
There's no reason why we can't create a world which, in theory, stretches off to infinity in all directions by shifting the position of the root node so that the player doesn't ever get close to its edge. Another approach would be to have multiple root nodes which move around to ensure that the horizon stays far enough away. Coupled with a continuous noise function to generate the contours of the land, we can create trillions of unique environments, all of which start with something as simple as a square grid.
This has been a quick introduction to the concept of adaptive terrain which uses a quadtree to control level of detail. I wrote this article as a high-level description of something I've actually put into code over on my GitHub page. These C#/XNA classes contain all the algorithms for building nodes, splitting and merging children and finding neighbours so if you're interested in digging deeper, please go and take a look.
I hope this has been useful in helping you understand how a small part of many modern games is put together, and good luck if you decide to go world-building by yourself!