[In this in-depth technical article, originally published in Game Developer magazine, Neversoft co-founder West examines how procedural generated content and compression can lead to expanding vistas for your open-world games.]

In a game where the environment and game objects are spooled from the disc as the player moves through the game world, the limiting factor in the allowable scene complexity is often a function of the data transfer rate of spooling and the virtual speed of the player within the world.

If the world has too much variety, then as the player moves from one region to another, a large amount of new data may need to be spooled from the disc in order to correctly display all the elements in the new region. If the data cannot be spooled fast enough, visible glitches may result as new geometry pops into existence.

Anyone playing the Grand Theft Auto series on the PlayStation 2 will have had the occasional experience of rapidly turning a corner and finding a large section of the road invisible for a few seconds.

If the missing elements are logically necessary for the game to work, the player may be forced to wait out these stalls in gameplay, as the missing elements are loaded.

To prevent these problems, developers should be placing limits on the scene complexity and the allowable variation between game regions.

Limits should also be placed on the maximum speed at which the player can move through the world, keeping it slow enough so there is sufficient time for the world to be updated as the player moves through it at top speed.

Disc bandwidth is frequently used as a shared resource, with the environment spooling simultaneously with the background music, voice over, and sometimes video.

So, in addition to increasing allowable scene complexity, any improvement in the utilization of disc bandwidth will allow a richer game experience with these additional audio and video elements.

Data Compression Limits

To maximize disc bandwidth utilization, the data on the disc needs to be compressed as much as possible. The greater the ratio between the size of the disc data and the system memory data, the more disc bandwidth we're able to use.

Naive lossless compression generally gives us an approximately 50 percent reduction in the size of the data. While there is frequent talk of more powerful processors (and particularly multi-core processors) that would let us use more powerful compression algorithms, the fact is that we are not talking about orders of magnitude in improvement.

On arbitrary data, advanced algorithms (such as PAQ) don't perform much more than 10 to 20 percent better than simple algorithms (such as Lempel-Ziv), despite taking more than twice as much CPU time in the decompression stage and several orders of magnitude more time in the compression stage (which can cause serious production problems by increasing build time).

It's possible to achieve more significant improvements by tailoring specific compression strategies to the data being compressed. This could involve re-ordering the data by de-interleaving data channels to allow the compressor to take better advantage of repetition within a channel (such as the X, Y, and Z channels of a vertex list).

Another data-specific compression technique is recognizing that certain numbers fall within a well-defined range and re-coding them using a reduced number of bits per value, or re-coding floats as fixed point.

You could also use lossy compression, although there's an obvious trade-off between improving bandwidth and perceptual degradation of the spooled content.

But compression on the actual scene geometry can only be taken so far. To further increase the spooling scene complexity, we need to look at procedural content.

Procedural Content

Procedural content is content that's generated from a mathematical description of the underlying form of that content, and a set of parameters that describe the specific instance of that content.

All forms of content can be expressed in procedural form to one extent or another. For example, music can be stored in MIDI format.

Speech can be stored as annotated text and converted using a text-to-speech converter. Textures can be generated with algorithmic patterns and combined archetypal layers. Animations can be generated based on archetypes and physical constraints.

The most relevant form of procedural content in the context of spooling is procedural geometry. As the player moves through a spooling world, the majority of new content that needs to be spooled is usually the environment geometry and the geometry of any new entity models.

Environment geometry can be divided into two types: natural and artificial. Natural geometry consists of things found in nature, such as natural terrain and rock formations, trees, flowers, vegetation, rocks, rivers, streams, lakes, smoke, and clouds. Artificial environment geometry is anything man-made (or alien-made, if that's your game), like roads, buildings, telegraph poles, walls, light poles, steps, ladders, and fences.

There are some obvious differences between natural and artificial environment geometry. Artificial geometry tends to have a lot of straight edges, flat surfaces, right angles, and identical components, like bricks.

Natural geometry has more curved edges, curved surfaces, and components that are similar but not the same, such as leaves and branches.

Figure 1: A procedurally generated tree of 65,000 polygons is generated from just 48 bytes.

The irregular nature of natural environment geometry results in a large number of polygons used to accurately represent the variety found in real life. Figure 1 shows the archetypical form of procedurally generated natural content: a tree.

Trees and plants are formed based on fairly simply mathematical procedures, and the shape of a tree consisting of thousands of polygons can be represented in less than a hundred bytes.

Natural geometry is hence the most obvious candidate for compression using procedurally generated geometry.

Procedural Compression

Procedural compression is simply storing a piece of geometry as a set of procedural parameters rather than as the final model. While this is not compression in the normal sense of the word, the effects are essentially the same, only with a vastly increased (even arbitrarily large) compression ratio.

The disc spooling bandwidth requirements are thus greatly reduced, allowing us to pack vastly more level geometry into a small percentage of that bandwidth. The trade-off is that artists have reduced flexibility in the models they can represent, since they are constrained to the possible output of the procedural algorithms.

We also trade some CPU resources, since the generation of geometry may require more CPU time than the standard spooling and decompressing of the raw data.

Are these trade-offs worth it? What are the ultimate benefits of using procedural models for level geometry?

To get some real-world numbers to answer this question, I wrote a procedural tree generator and measured how long it took to generate level geometry. (The code used to generate the table and figures shown here can be downloaded here.) I then compared my results to the theoretical peak spooling speeds of various game platforms. The results are summarized in Table 1.

The bandwidth figures shown in Table 1 are peak bandwidth; in reality, actual average bandwidth can be as little as half. Two factors influence these results. First, it's difficult to actually fully utilize the available bandwidth, as the data set tends to be loaded in chunks.

Second, seek-times play a significant role in actual bandwidth utilization. Layout of data on the disc can greatly affect these numbers by causing excessive seeking, especially when data spooling needs to be interweaved with audio spooling.

Hard drive figures are included in the table, too. On a PC, the level data is generally loaded onto the hard drive first, and hard drives generally have a much faster average read rate than optical drives. Unfortunately, we must code for a lowest possible common denominator on the PC. Not so on the PlayStation 3, with a default hard drive which can potentially be used to cache level data.

Note though that the transfer rate of the 2.5-inch drive used isn't astoundingly faster than the peak Blu-ray rate, so many of the same problems still apply even if the hard drive is used for caching. On the Xbox 360, the hard drive is optional, so we have to assume it's not there.

A typical broadband internet rate of 0.3MB per second is shown for comparison. Spooling level geometry over such a slow connection would be very limited. However, if the majority of the level content is procedural, it's quite possible to spool an arbitrarily large world of content over the internet. To a small extent, this is the driving idea behind Will Wright's game Spore.

The tree generator in the code samples is very simple and rather inefficient, using vertex lists rather than indexed vertices. However, it does perform a reasonable amount of computation to generate the model, calculating texture coordinates and vertex normals. No optimization efforts have been made with this code, so the figures given here can be viewed very much as the bottom end for procedural geometry generation, with a more efficient algorithm easily being twice as fast.

Looking at the figures for the Xbox 360, the DVD spooling figure is a maximum of 16MB per second. Again, this is a peak figure, with a sustainable average of perhaps 8MB per second (although standard compression would again bump this up to an effective >16MB per second). Utilizing one of the three CPU cores of the Xbox 360, we should easily be able to generate level geometry at a rate upwards of 300MB per second.

Procedural level geometry is an ideal use of a multi-core system, like the Xbox 360 or PlayStation 3. If the procedural generation is being used essentially as a spooling system, then the geometry generation can be run on a low priority thread, making very effective use of "spare" CPU cycles.

Instant Spooling

Using procedural level generation as a way of accelerating spooling is great, but it can swiftly lead to another limited system resource: memory. If we're building the geometry in memory, then we're limited by how much memory we can reserve for geometry. In many cases, the available memory can hold far fewer polygons than the GPU can process.

The solution to this resource issue is not to use memory at all; instead, we generate the geometry in real time and feed it directly to the GPU. Theoretically, this method lets programmers fully utilize the polygon-pushing power of the GPU, while freeing up system memory for other things, such as materials or additional artist-generated geometry.

One way of generating polygons in real time is to perform dynamic tessellation, in which surface polygons are subdivided into smaller polygons, interpolating across surface normals to maintain the curve of the surface.

A better looking result can be achieved if the model is stored as higher order surfaces, such as NURBs, which can be tessellated in real time. Real-time tessellation can be dynamically varied depending on view distance, and so can be used as a very effective real-time level of detail (LOD) generator.

Dynamic tessellation can be used to enhance procedural geometry. In my tree-generating sample code, I can dynamically alter the number of polygons that make up the trunk and branches based on camera distance.

Real-time LOD is another great advantage of real-time procedural model generation. Instead of storing discrete models for several levels of detail, the procedural model generator simply generates a model to a sufficient level of complexity based on camera distance and current viewable scene complexity.

You can also code for a fractional LOD transition, where the LOD is given a floating point value, and smoothly transitions from one stage to another.

Figure 2: A forest of real-time procedural trees with continuous LOD generation.

In the tree sample, the LOD is defined by the branching depth. If this were done at the integer level, the user would notice distinct pops as the LOD moved from one stage to the next. However, by scaling the terminal branches by the fractional part of the LOD, the geometry of the tree can smoothly and simply morph from one stage to the next, providing a continuous increase in LOD that is almost imperceptible.

Figure 2 shows a variety of procedural trees being generated in real time, with the trees in the distance having lower LOD. As you move through this scene, the LOD transitions are very smooth, an effect that would be impossible to achieve without real-time procedural geometry generation.

Generated Conclusions

Procedurally generated content has the potential to support huge and unbelievably detailed worlds. It can be used to significantly augment traditionally spooled static level geometry to more fully utilize disc spooling bandwidth. Effective use of procedural content may require a new set of tools and working practices, which may take some developers a while to acquire.

The difficulty in creating swathes of content by hand, and the imbalance in spooling speed and polygon pushing power, has made the utilization of procedural content an almost unavoidable necessity. The good news is it's a lot of fun to code!

References

Sample code available at www.gdmag.com

Bulkley, Brad. "Edge of the World," Game Developer, June/July 2006.

Dapper, Tim. "Practical Procedural Modeling of Plants," University of
Bremen.www.td-grafik.de/artic/talk20030122/overview.html

Wikipedia: Procedural Generation
http://en.wikipedia.org/wiki/Procedural_generation

Stokes, Jon Hannibal. "Inside the Xbox 360, Part I: Procedural synthesis
and dynamic worlds," Ars Technica, May 24, 2005.
http://arstechnica.com/articles/paedia/cpu/xbox360-1.ars/3

[EDITOR'S NOTE: This article was independently published by Gamasutra's editors, since it was deemed of value to the community. Its publishing has been made possible by Intel, as a platform and vendor-agnostic part of Intel's Visual Computing microsite.]