Procedural generation

From Wikipedia, the free encyclopedia

Procedural generation is a widely used term to indicate the possibility to create content on the fly, as opposed to creating it before distribution. This is often related to computer graphics applications.

Procedural synthesis is actually the correct term for this kind of approach. In this document, the terms "synthesis" and "generation" are used interchangeably.

More generally, the term 'procedural' is strictly related to a procedure used to compute particular functions. This concept takes on dramatic expression in fractals, a specific example of procedural generation; one around which a whole body of mathematics--fractal geometry--has evolved. Most common procedurally generated content include textures and meshes. Sound is seldom procedurally generated in PC applications. While procedural generation techniques have been employed for years in countless games, few actually used this approach extensively. An exception is Will Wright's Spore, an upcoming video game title populated entirely with procedurally generated content. Some "procedurally generated" elements also appeared in previous games: the first Soldier of Fortune from Raven Software used simple routines to add random detail to enemy models. To a certain degree, it could be said that the lighting in Doom 3 from id Software is "procedurally generated" because it does not rely on lightmaps precomputed using a radiosity process. More recently Avalanche Studios have been using procedural generation to create a large and varied group of tropical islands with high detail in their game Just Cause.

The modern demoscene uses procedural generation for squeezing a lot of impressive audiovisual content into very small executable programs. Farbrausch is a team famous for its achievements in this area, although many similar techniques were already implemented by The Black Lotus in the 1990's.

Contents

[edit] Procedural generation as an application of functional programming

Procedurally generated content such as textures and landscapes may exhibit variation, but the generation of a particular item or landscape must be identical from frame to frame. Accordingly, the functions used must be referentially transparent, always returning the same result for the same point, so that they may be called in any order and their results freely cached as necessary. This is similar to lazy evaluation in functional programming languages.

[edit] Procedural generation in video games

The earliest computer games were severely limited by memory constraints. This forced content like maps to be generated algorithmically on the fly: there simply wasn't enough space to store a large amount of premade levels and artwork. Pseudorandom number generators were often used with predefined seed values in order to create very large game worlds that appeared premade. For example, The Sentinel supposedly had 10,000 different levels stored in only 48 or 64 kilobytes. An extreme case was Elite, which was originally planned to contain a total of 248 (approximately 282 million million) galaxies with 256 solar systems each. The publisher, however, was afraid that such a gigantic universe would cause disbelief in players, and the number of galaxies was therefore limited to eight in the final version.[1]

Today, most games include thousands of times as much data in terms of memory as algorithmic mechanics. For example, all of the buildings in the large game world of Grand Theft Auto were individually designed and placed by artists. In a typical modern video game, game content such as textures and character and environment models are created by artists beforehand, then rendered in the game engine. As the technical capabilities of computers and video game consoles increases, the amount of work required by artists also increases. First, high-end gaming PCs and next-generation game consoles like the Xbox 360 and PlayStation 3 are capable of rendering scenes containing many very detailed objects with high-resolution textures in high-definition. This means that artists must invest a great deal more time in creating a single character, vehicle, building, or texture, since gamers will tend to expect ever-increasingly detailed environments.

Second, the number of unique objects displayed in a video game is increasing. In addition to highly detailed models, players expect a variety of models that appear substantially different from one another. In older games, a single character or object model might have been used over and over again throughout a game. With the increased visual fidelity of modern games, however, it is very jarring (and threatens the suspension of disbelief) to see many copies of a single object, while the real world contains far more variety. Again, artists would be required to complete orders of magnitude more work in order to create many different varieties of a particular object. The need to hire larger art staffs is one of the reasons for the rapid increase in game development costs.

Some initial approaches to procedural synthesis attempted to solve these problems by shifting the burden of content generation from the artists to programmers who can create code which automatically generates different meshes according to input parameters. Although sometimes this still happens, what has been recognized is that applying a purely procedural model is often hard at best, requiring huge amounts of time to evolve into a functional, usable and realistic-looking method. Instead of writing a procedure that completely builds content procedurally, it has been proven to be much cheaper and more effective to rely on artist created content for some details. For example, SpeedTree is middleware used to generate a large variety of trees procedurally, yet its leaf textures can be fetched from regular files, often representing digitally acquired real foliage. Other effective methods to generate hybrid content is to procedurally merge different pre-made assets or to procedurally apply some distortions to them.

Supposing, however, a single algorithm can be envisioned to generate a realistic-looking tree, the algorithm could be called to generate random trees, thus filling a whole forest at runtime, instead of storing all the vertices required by the various models. This would save storage media space and reduce the burden on artists, while providing a richer experience. The same method would require far more processing power (though somewhat less disk access), but with CPUs getting faster, the problem is gradually becoming smaller. However it is not easy to develop such an algorithm for a single tree, let alone for a variety of species (compare Sumac, Birch, Maple and its species), moreover assembling a forest could not be done by just assembling trees because in the real world this introduces interactions between the various trees which dramatically change their appearance (although this is probably a minor detail).

In 2004, a PC first-person shooter called .kkrieger was released that made heavy use of procedural synthesis: while quite short and very simple, the advanced video effects were packed into just 96 Kilobytes. In contrast, many modern games are released across several CDs, often exceeding 2 gigabytes in size, more than 20,000 times larger. Several upcoming commercial titles for the PC, such as Will Wright's Spore, will also make use of procedural synthesis. If this trend continues in the console world, it will require special hardware support. Accordingly, the Xbox 360 and the PlayStation 3 have impressive procedural synthesis capabilities.

[edit] Next-generation console support and speculations

The Xbox 360's CPU, known as Xenon, is a 3-core design. When running procedural synthesis algorithms [1], one of the Xenon CPU's cores may "lock" a portion of the 1 MB shared L2 cache. When locked, a segment of cache no longer contains any prefetched instructions or data for the CPU, but is instead used as output space for the procedural synthesis thread. The graphics processing unit, called Xenos, can then read directly from this locked cache space and render the procedurally generated objects. The rationale behind this design is that procedurally generated game content can be streamed directly from CPU to GPU, without incurring additional latency by being stored in system RAM as an intermediary step. The downside to this approach is that when part of the L2 cache is locked, there is even less data immediately available to keep the 3 symmetric cores in the Xenon CPU running at full efficiency (1 MB of shared L2 is already a rather small amount of cache for 3 symmetric cores to share, especially considering that the Xenon CPU does not support out-of-order execution to more efficiently use available clock cycles).

The Cell processor contains an implementation-dependent number of vector processing units called SPEs. PlayStation 3, to date the largest use of the Cell processor, will contain 8 SPEs, only seven of which are active. The eighth is to be used in the event that another SPE malfunctions. The SPEs can stream data to each other, with each SPE performing a different operation on a large set of data, thus creating a highly efficient chain which performs a sequence of operations on a data set of arbitrary size (they are virtually assembled in a "hyper-pipeline", allowing high amount of parallelism). Each SPE can execute a different task in the algorithm and pass the result on to another SPE which does the next piece of work. The cell can thus generate game objects very quickly by dividing the algorithm into smaller tasks and setting up a chain of SPEs to do the work on an arbitrarily large number of objects.

For example, to generate a boulder, an SPE may initialize the basic vertex positions to a spherical object, a second SPE may displace those points to add randomness, a third to generate normals, tangent and binormals for bumpmapping while a fourth SPE may add volume texture coordinates (possibly in parallel with the third SPE). Note that this example assumes the compiler can guess correct parallelism opportunity.

The Cell's counterpart to Xenon "cache locking" is each SPE's 256 KiB local store, essentially L2 cache memory which can be accessed directly, rather than being used to speed up access to main memory. This approach has both perks and flaws, as it allows each SPE to work extremely quickly, but only on a small subset of the total data of a program. There is also a direct 35 GB/s link between the Cell and the PS3's "Reality Synthesizer" GPU, allowing objects to be sent directly to the GPU to be rendered as soon as they are generated.

[edit] See also

[edit] Software using procedural generation

[edit] References

  1. ^ Francis Spufford. "Masters of their universe", Guardian, October 18, 2003.

[edit] External links