- Procedural generation
Procedural generation is a widely used term in the production of media, indicating the possibility to create content
on the flyrather than prior to distribution. This is often related to computer graphicsapplications and video game level design.
The term "procedural" refers to the process that computes a particular function.
Fractals, an example of procedural generation, dramatically expresses this concept, around which a whole body of mathematics— fractal geometry—has evolved. Commonplace procedural content includes textures and meshes. Soundis often procedurally generated as well and has applications in both speech synthesisas well as music. It has been used to create compositions in various genres of electronic musicby artists such as Brian Enowho popularized the term " generative music".
While software developers have applied procedural generation techniques for years, few products have employed this approach extensively. An exception is Will Wright's "Spore", a recently released
video gameentirely populated with procedurally generated content. Procedurally generated elements have also appeared in earlier video games: the first "" randomly generates terrain and NPCs, creating a world roughly the actual size of the British Isles. "Soldier of Fortune" from Raven Softwareuses simple routines to detail enemy models. It could also be said that the lighting in " Doom 3" from id Softwareis procedurally generated because it does not rely on lightmaps precomputed with a radiosityprocess. More recently Avalanche Studiosemployed procedural generation to create a large and varied group of tropical islands in great detail for "Just Cause".
demosceneuses procedural generation to package a great deal of audiovisual content into relatively small programs. Farbrauschis a team famous for such achievements, although many similar techniques were already implemented by The Black Lotusin the 1990s.
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 evaluationin functional programminglanguages.
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 pre-made 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 trillion) galaxies with 256 solar systems each. The publisher, however, was afraid that such a gigantic universe would cause disbelief in players, and eight of these galaxies were chosen for the final version.cite news | url=http://www.guardian.co.uk/weekend/story/0,3605,1064107,00.html | title=Masters of their universe | publisher=Guardian | author=Francis Spufford | date=October 18, 2003] Other notable early examples include the 1985 game Rescue on Fractalusthat used fractal technology to procedurally create in real time the craggy mountains of an alien planet and River Raid, the 1982 Activisiongame that used a pseudorandom number sequence generated by a linear feedback shift registerin order to generate a scrolling maze of obstacles.
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 worlds of the "Grand Theft Auto" games have been 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 greatly increases. First, high-end gaming PCs and current-generation game consoles like the Xbox 360and PlayStation 3are 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.
Furthermore, 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 exponentially 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, SpeedTreeis middlewareused 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 are 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, Mapleand 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 shootercalled " .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 gigabytesin size, more than 20,000 times larger. Naked Sky's " RoboBlitz" utilized procedural generation to maximize content in a less than 50MB downloadable file for Xbox Live Arcade. Will Wright's "Spore" also makes use of procedural synthesis.
As in video games, procedural generation is often used in film to rapidly create visually interesting and accurate spaces. This comes in a wide variety of applications.
One application is known as an "imperfect factory," where artists can rapidly generate a large number of similar objects. This accounts for the fact that, in real life, no two objects are ever exactly alike. For instance, an artist could model a product for a grocery store shelf, and then create an imperfect factory that would generate a large number of similar objects to populate the shelf.
Noise is extremely important to procedural workflow in film, the most prolific of which is
Perlin noise. Noise refers to an algorithm that generates a patterned sequence of pseudorandom numbers.
Cellular automata methods of procedural generation
Simple programs which generate complex output are a typical method of procedural generation. Typically, one starts with some simple initial conditions like an array of numbers. Then one applies simple rules to the array, which determine the next step in the evolution of the output - that is, the next array of numbers. The rules can be fixed, or they can be changing in time. One can let the program run, and given the right update rules and initial conditions, one can obtain a non-repeating evolution starting from an initial array.
Cellular automataare discrete computer models of evolutionary behavior which start from an array of differently-colored cells, then apply update rules to determine the colors of the next array of cells. Typically one starts with a two-color program, and a random finite array of black and white cells. Then one defines a neighborhood --- for the simplest case, just the two neighboring cells of any one cell ---- and creates a so-called "update rule" to determine what the next cell in the evolution will be. Typical elementary update rules are of the form, "If the current cell is black and the cells to the right and left are white, then the next cell in the evolution shall be white."
It is an astonishing fact that such simple rules, even in the simplest case of two colors, can produce a complex evolution. But, in fact, they can (see
Rule 30and Rule 110).
What does this mean for game developers? It means that, starting with finite initial conditions and extremely simple rules, one can generate complex behavior. That is, content can be nearly spontaneously generated from virtually nothing, which is the idea behind procedural generation. Evolving cellular automata is one way of generating a large amount of content from a small amount of input.
oftware using procedural generation
MaPZone/ProFX– a middlewareproduct designed to create and generate procedural textures in games (used in RoboBlitz).
* "Houdini" - a procedural 3D animation package. A free version of the software is available.
Filter Forge– an Adobe Photoshopplugin for designing procedural textures using node-based editing.
Art of Illusion– an open source and free 3D modeler, has an internal node-based procedural texture editor.
SpeedTree– a middlewareproduct for procedurally generating trees.
Terragen– landscape generation software. Terragen 2 permits procedural generation of an entire world.
Procedural worlds and universes for space simulations
* "Elite" (1984) - Everything about the universe, planet positions, names, politics and general descriptions, is generated procedurally; Ian Bell has released the algorithms in C as text elite [ [http://www.iancgbell.clara.net/elite/text/index.htm Ian Bell's Text Elite Page ] ]
StarFlight" (1986)Fact|date=April 2008
* "Exile" (1988) - Game levels were created in a pseudorandom fashion, as areas important to gameplay were generated.Fact|date=April 2008
* "" (1993) - Much as the game Elite had a procedural universe, so did its sequel.Fact|date=April 2008
* "" (1995)
Noctis" (2002)Fact|date=April 2008
* "" (Not yet released)
* "The Sentinel" (1986) - Used procedural generation to create 10,000 unique levels.
* "Darwinia" (2005) - Has procedural landscapes that allowed for greatly reduced game development time.Fact|date=April 2008
* "" (1996)
* "Diablo" (1998) and "
Diablo II" (2000) both use procedural generation for level design. Fact|date=April 2008
* "" procedurally generates the game's world.
Dark Cloud" and " Dark Cloud 2" both generate game levels procedurally.
* "" (2007)
* Nearly all
roguelikes use this technique.
*"Seven Kingdoms" (1997) - Uses procedural generation for levels.
Procedural third-person shooters
* "Just Cause" (2006) - Game area is over convert|250000|acre|km2, created procedurally Fact|date=September 2007
RoboBlitz" (2006) for XBox360 live arcade and PC (Textures generated on the fly via ProFX)
Almost entirely procedural games
Games with miscellaneous procedural effects
Jade Cocoon" (1998) - The merged minions were procedurally generated based on body part sizes.Fact|date=April 2008
* "Spore" (2008)
* "" (2002) - Water effects are generated on the fly with
procedural animationby the technique demonstrated in NVIDIA's "Water Interaction" demo. cite web|url=http://http.download.nvidia.com/developer/SDK/Individual_Samples/3dgraphics_samples.html#WaterInteraction | title=NVIDIA Water Interaction Demo | publisher= NVIDIA|accessdate=2007-10-08 |year=2003]
ToeJam & Earl" (1991) - The random levels were procedurally generated.
Generative Modelling Language
Iterated function system
* [http://www.pqhp.com/cmp/gdctv/ The Future Of Content] - Will Wright keynote on Spore & procedural generation at the
Game Developers Conference2005. (Scroll down 3/4 of page, registration required to view video).
* [http://www.intel.com/cd/ids/developer/asmo-na/eng/dc/games/graphics/20534.htm?page=1 Generating Procedural Clouds in real time on 3D HW]
* [http://www.darwinia.co.uk/ Darwinia] - [http://www.darwinia.co.uk/extras/development.html development diary] procedural generation of terrains and trees.
* [http://www.photoshoproadmap.com/Photoshop-blog/2006/08/30/creating-a-wet-and-muddy-rocks-texture/ Filter Forge tutorial at The Photoshop Roadmap]
* [http://in4k.untergrund.net/index.php?title=Procedural_Graphics_-_an_introduction Procedural Graphics - an introduction by in4k]
* [http://www.texturingandmodeling.com/ Texturing & Modeling:A Procedural Approach 3e 2002]
* [http://www.noisemachine.com/talk1/ Ken Perlin's Discussion of Perlin Noise]
* Eric W. Weisstein, " [http://mathworld.wolfram.com/ElementaryCellularAutomaton.html Elementary Cellular Automaton] " at [http://mathworld.wolfram.com/ mathworld.com]
Wikimedia Foundation. 2010.