My Thoughts On Virtual World Design

by Alan Baylis 2001

I searched around for a world or terrain algorithm that would allow good Level Of Detail (LOD) and suit both an indoor and outdoor environment. I looked into Portals, Binary Spaced Partition (BSP) trees, Octrees and others. They all work well for their intended game type but aren't suited to a game that is a combination of large terrains and indoor scenes. An indoor game is best programmed using Portals and BSPs while outdoor scenes are probably best programmed using an Adaptive Quadtree Mesh/Heightfield or ROAM style. At a guess I would say that the two would not go together easily. If we were to mix the two together we would end up with a world that looked like a natural terrain with buildings sitting on flat areas but where the terrain met roads, for example, we would most likely end up with a flat surface with a texture of a road. If we are to consider what we want from our game environments of the future this would not do.

On top of this we have to realize that we should hand over as much work as we can to the hardware. For example, the days of clipping polygons to the windows edges are gone, any algorithm we are likely to use will most likely be slower than just rendering all polygons that are potentially within the view and let the hardware do the clipping.

What we want is a fast game design, dynamic scenery, a comfortable view distance, spacious outdoor scenes and the seamless transition from terrain to buildings, roads, etc. No general terrain algorithm or portal style design is going to be able to achieve this.

I think the way forward is to subdivide the world into a 3d grid of cubes. This way we would be able to use a different approach in each cube. The LOD of the terrain will most likely be fixed but the buildings and objects could use multiple objects of reducing complexity for LOD. The easier way would most likely be to make multiple cubes of reducing complexity. Up until recently this approach would be unsatisfactory but Moore's Law (which states that the speed and storage capacity of computers doubles each year) is making this type of approach attainable. Even if this isn't quite true yet we should be looking at having something ready for when it is in the near future (given game development times these days we have to think ahead.)

With this poor approach to LOD how can the game be fast enough I hear you ask. Firstly, because the cubes are orientated and have a fixed position they are easy to occlude from the rendering process. We can also subdivide each cube into smaller cubes and if the large cube isn't in the scene then we need not render any of the smaller cubes (much like Octrees). Secondly, we use all the tricks in the book. Namely, using geometric primitives with low vertex counts like triangle strips/fans, Compiled Vertex Arrays and Display Lists.

To speed the process further we can introduce a flag in each cube that indicates what type of terrain it is. If the cube is empty then the flag could be set to zero or if the terrain is flat we could set the flag to 1. By checking the flag first in the process of drawing the cubes most of the cubes could be omitted quickly or drawn in a faster way. The amount of subdivision could also be variable for each cube. Some cubes would have no subdivision and others that contain a detailed area of the world could have subdivision down to a metre^3 or smaller.

Using a grid of cubes also speeds up the collision detection process in that we only need to check for a collision in the cubes we are passing through. We would need to check for a collision against all the polygons in the cubes we are going to pass through with our current velocity. If a collision in one cube diverts the colliding object we would need to find all the cubes that lie on the new path before recursively checking for any other collisions. An easier way may be to find the group of cubes that are within reach of the original velocity vector and recursively check for a collision against those.

Dynamic scenery should be achievable by designing up to 25 or so cubes to be used as animation frames for a location and cycling through them. The only expense to this would be the amount of memory used but if we consider that any cube can be reused at other locations (and should be wherever possible) then the savings made by reusing grids may balance the memory usage. A simple example may be a sign or tree moving in the wind with only a few animation cubes. As a more adventurous example we could imagine a cube with a car on the road. The car wouldn't be a separate model and have independent movement but is part of the cubes terrain. In the first frame the car could be drawn half in the cube travelling in the direction of the road, as the frames progress, the car could be drawn moving down the road to the other side of the cube until it is half out of the cube. By linking the cubes together we would have the equivalent of cars moving down the road. It may not sound like this would be any better than using a model of a car, however, because the cubes are optimized using pre-compiling and have no transforms or calculations, aside from moving the cube from the origin into its world location, there may be a large difference in speed and allow many more cars on a road than we currently have.

I also feel that this type of world design is intuitive and easy to modify. Building a world will eventually be as easy as choosing a cube from a library of pre-existing cubes rather than designing a new cube. The editor would need to be very flexible, allowing for different approaches to be used in each cube. Also, after selecting the cubes for a world scene, there should be a fast way to join the vertices of adjacent cubes together. Ideally this would be an automatic process but realistically this most likely will be a manual point and click operation.

The ideal world for this approach would most likely be an even mix of land and buildings. If terrain were used too much it would slow down the frame rate but by using plenty of buildings, with about three levels of detail, the view distance and frame rate should be reasonable. I foresee that this approach would be best suited to a more futuristic type of city-scape with high buildings joining together at various heights which create new levels rather than the customary ground level world. The city would also be criss-crossed with crosswalks and flyovers.

That's about all I have say up to this point. The design may not be as mathematical as other designs but should fulfil its objective and easily allow for a variable view distance. As computers get faster the view distance could be let out further with no extra programming.

Now all that is left to do is program the thing :)

Seeya later

Al