Procedural generation
Encyclopedia
Procedural generation is a widely used term in the production of media; it refers to content generated algorithmically rather than manually. Often, this means creating content on the fly
rather than prior to distribution. This is often related to computer graphics
applications and video game level design
.
s, an example of procedural generation , dramatically express this concept, around which a whole body of mathematics—fractal geometry—has evolved. Commonplace procedural content includes textures
and meshes
. Sound
is often procedurally generated as well and has applications in both speech synthesis
as well as music. It has been used to create compositions in various genres of electronic music
by artists such as Brian Eno
who popularized the term "generative music
".
While software developers have applied procedural generation techniques for years, few products have employed this approach extensively. Procedurally generated elements have appeared in earlier video games: The Elder Scrolls II: Daggerfall
takes place on a mostly procedurally generated world, giving a world roughly twice the actual size of the British Isles. Soldier of Fortune from Raven Software
uses simple routines to detail enemy models. Avalanche Studios
employed procedural generation to create a large and varied group of tropical islands in great detail for Just Cause
.
The modern demoscene
uses procedural generation to package a great deal of audiovisual content into relatively small programs. Farbrausch
is a team famous for such achievements, although many similar techniques were already implemented by The Black Lotus in the 1990s.
ically on the fly: there simply wasn't enough space to store a large amount of pre-made levels and artwork. Pseudorandom number generator
s 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.
Other notable early examples include the 1985 game Rescue on Fractalus
that used fractals to procedurally create in real time the craggy mountains of an alien planet and River Raid
, the 1982 Activision
game that used a pseudorandom number sequence generated by a linear feedback shift register
in 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 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.
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, 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 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. Since CPUs are constantly increasing in speed, however, the latter is becoming less of a hurdle.
A different problem is that it is not easy to develop a good algorithm for a single tree, let alone for a variety of species (compare Sumac
, Birch
, Maple
). An additional caveat is that assembling a realistic-looking forest could not be done by simply assembling trees because in the real world there are interactions between the various trees which can dramatically change their appearance and distribution.
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 have to be released on DVDs, often exceeding 2 gigabytes in size, more than 20,000,000 times larger. Naked Sky's
RoboBlitz
used 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.
In 2008, Valve Software released Left 4 Dead
, a first-person shooter based on the Source engine
that utilized procedural generation as a major game mechanic. The game featured a built-in artificial intelligence
structure, dubbed the "Director," which analyzed player statistics and game states on the fly to provide dynamic experiences on each and every playthrough. Based on different player variables, such as remaining health, ammo, and number of players, the A.I. Director could potentially create or remove enemies and items so that any given match maintained an exciting and breakneck pace. Left 4 Dead 2
, released in November 2009, expanded on this concept, introducing even more advanced mechanics to the A.I. Director, such as the ability to generate new paths for players to follow according to their individual statuses.
An indie game that makes extensive use of procedural generation is Minecraft
. In the game the initial state of the world is mostly random (with guidelines in order to generate Earth-like terrain), and new areas are generated whenever the player moves towards the edges of the world. This has the benefit that every time a new game is made, the world is completely different and will need a different method to be successful, adding replay value.
Another indie game that relies heavily on procedural generation is Dwarf Fortress
. In the game the whole world is generated, completely with its history, notable people, and monsters.
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 are 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."
Such simple rules, even in the simplest case of two colors, can produce a complex evolution (see Rule 30
and Rule 110).
For game developers, this means that, using 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.
Racing games
Role-playing games
Strategy games
Games with yet unknown genre
Third-person shooters
On the fly
-Colloquial usage:In colloquial use, on the fly means something created when needed. The phrase is used to mean:# something that was not planned ahead# changes that are made during the execution of same activity: ex tempore, impromptu.-Automotive usage:...
rather than prior to distribution. This is often related to computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
applications and video game level design
Level design
Level design, environment design or game mapping is a discipline of game development involving creation of video game levels—locales, stages, or missions. This is commonly done using level editor, a game development software designed for building levels; however some games feature built-in...
.
Overview
The term procedural refers to the process that computes a particular function. FractalFractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
s, an example of procedural generation , dramatically express this concept, around which a whole body of mathematics—fractal geometry—has evolved. Commonplace procedural content includes textures
Texture mapping
Texture mapping is a method for adding detail, surface texture , or color to a computer-generated graphic or 3D model. Its application to 3D graphics was pioneered by Dr Edwin Catmull in his Ph.D. thesis of 1974.-Texture mapping:...
and meshes
Polygon mesh
A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...
. Sound
Sound
Sound is a mechanical wave that is an oscillation of pressure transmitted through a solid, liquid, or gas, composed of frequencies within the range of hearing and of a level sufficiently strong to be heard, or the sensation stimulated in organs of hearing by such vibrations.-Propagation of...
is often procedurally generated as well and has applications in both speech synthesis
Speech synthesis
Speech synthesis is the artificial production of human speech. A computer system used for this purpose is called a speech synthesizer, and can be implemented in software or hardware...
as well as music. It has been used to create compositions in various genres of electronic music
Electronic music
Electronic music is music that employs electronic musical instruments and electronic music technology in its production. In general a distinction can be made between sound produced using electromechanical means and that produced using electronic technology. Examples of electromechanical sound...
by artists such as Brian Eno
Brian Eno
Brian Peter George St. John le Baptiste de la Salle Eno , commonly known as Brian Eno or simply as Eno , is an English musician, composer, record producer, singer and visual artist, known as one of the principal innovators of ambient music.Eno studied at Colchester Institute art school in Essex,...
who popularized the term "generative music
Generative music
Generative music is a term popularized by Brian Eno to describe music that is ever-different and changing, and that is created by a system.- Theory :There are four primary perspectives on "Generative Music" Generative music is a term popularized by Brian Eno to describe music that is ever-different...
".
While software developers have applied procedural generation techniques for years, few products have employed this approach extensively. Procedurally generated elements have appeared in earlier video games: The Elder Scrolls II: Daggerfall
The Elder Scrolls II: Daggerfall
The Elder Scrolls II: Daggerfall is a first-person, traditional role-playing video game for MS-DOS developed by Bethesda Softworks and released in 1996. It is a sequel to the RPG The Elder Scrolls: Arena and the second installment in The Elder Scrolls series. On July 9, 2009, it was made available...
takes place on a mostly procedurally generated world, giving a world roughly twice the actual size of the British Isles. Soldier of Fortune from Raven Software
Raven Software
Raven Software is an American video game developer. The company was founded in 1990 by brothers Brian and Steve Raffel. In 1997, Raven made an exclusive publishing deal with Activision and was subsequently acquired by them...
uses simple routines to detail enemy models. Avalanche Studios
Avalanche Studios
Avalanche Studios is an independent, privately held video game developer based in Stockholm, Sweden. It was founded in March 2003 by Christofer Sundberg, Linus and Viktor Blomberg. Avalanche Studios focuses on developing original intellectual properties for games and other media and base their...
employed procedural generation to create a large and varied group of tropical islands in great detail for Just Cause
Just Cause (video game)
Just Cause is an open world action-adventure video game developed by Avalanche Studios and published by Eidos Interactive. It was released for Microsoft Windows, PlayStation 2, Xbox, Xbox 360 on September 22, 2006 in Europe, September 27, 2006 in North America, September 29, 2006 in Australia and...
.
The modern demoscene
Demoscene
The demoscene is a computer art subculture that specializes in producing demos, which are non-interactive audio-visual presentations that run in real-time on a computer...
uses procedural generation to package a great deal of audiovisual content into relatively small programs. Farbrausch
Farbrausch
Farbrausch, or Farb-rausch, is a German group of demomakers who made themselves particularly famous in the demoscene in December 2000 with a 64k intro called "fr-08: .the .product". "Farbrausch" literally translates to "rave of color", "color rush" or "color frenzy" in English...
is a team famous for such achievements, although many similar techniques were already implemented by The Black Lotus in the 1990s.
Video games
The earliest computer games were severely limited by memory constraints. This forced content, such as maps, to be generated algorithmAlgorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
ically on the fly: there simply wasn't enough space to store a large amount of pre-made levels and artwork. Pseudorandom number generator
Pseudorandom number generator
A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...
s were often used with predefined seed values in order to create very large game worlds that appeared premade. For example, The Sentinel
The Sentinel (computer game)
The Sentinel is a computer game created by Geoff Crammond, published by Firebird in 1986 for the BBC Micro and converted to the C64 , Amstrad CPC , ZX Spectrum , Atari ST, Amiga and PC . It was released in the US as The Sentry...
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.
Other notable early examples include the 1985 game Rescue on Fractalus
Rescue on Fractalus
Rescue On Fractalus! is a March 1984 computer game created by Lucasfilm Games . It was originally released for the Atari 8-bit family and the Atari 5200 games console. It was also ported to other popular platforms of the day, such as the Apple II, ZX Spectrum , Amstrad CPC, Tandy Color Computer 3...
that used fractals to procedurally create in real time the craggy mountains of an alien planet and River Raid
River Raid
River Raid is a scrolling shooter videogame and was released in 1982 by Activision for the Atari 2600, and later the Atari 5200, Atari 8-bit, C64, ColecoVision, IBM PCjr, Intellivision, ZX Spectrum, and MSX...
, the 1982 Activision
Activision
Activision is an American publisher, majority owned by French conglomerate Vivendi SA. Its current CEO is Robert Kotick. It was founded on October 1, 1979 and was the world's first independent developer and distributor of video games for gaming consoles...
game that used a pseudorandom number sequence generated by a linear feedback shift register
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
in 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
Grand Theft Auto (series)
Grand Theft Auto is a multi-award-winning British video game series created in the United Kingdom by Dave Jones, then later by brothers Dan Houser and Sam Houser, and game designer Zachary Clarke. It is primarily developed by Edinburgh based Rockstar North and published by Rockstar Games...
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 360
Xbox 360
The Xbox 360 is the second video game console produced by Microsoft and the successor to the Xbox. The Xbox 360 competes with Sony's PlayStation 3 and Nintendo's Wii as part of the seventh generation of video game consoles...
and PlayStation 3
PlayStation 3
The is the third home video game console produced by Sony Computer Entertainment and the successor to the PlayStation 2 as part of the PlayStation series. The PlayStation 3 competes with Microsoft's Xbox 360 and Nintendo's Wii as part of the seventh generation of video game consoles...
are capable of rendering scenes containing many very detailed objects with high-resolution textures in high-definition
High-definition video
High-definition video or HD video refers to any video system of higher resolution than standard-definition video, and most commonly involves display resolutions of 1,280×720 pixels or 1,920×1,080 pixels...
. 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
Suspension of disbelief
Suspension of disbelief or "willing suspension of disbelief" is a formula for justifying the use of fantastic or non-realistic elements in literary works of fiction...
) 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, SpeedTree
SpeedTree
SpeedTree is a group of vegetation programming and modeling software products developed and sold by Interactive Data Visualization, Inc. that generates virtual foliage for animations and in real time for video games and simulations...
is middleware
Middleware
Middleware is computer software that connects software components or people and their applications. The software consists of a set of services that allows multiple processes running on one or more machines to interact...
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 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. Since CPUs are constantly increasing in speed, however, the latter is becoming less of a hurdle.
A different problem is that it is not easy to develop a good algorithm for a single tree, let alone for a variety of species (compare Sumac
Sumac
Sumac is any one of approximately 250 species of flowering plants in the genus Rhus and related genera, in the family Anacardiaceae. Sumacs grow in subtropical and temperate regions throughout the world, especially in Africa and North America....
, Birch
Birch
Birch is a tree or shrub of the genus Betula , in the family Betulaceae, closely related to the beech/oak family, Fagaceae. The Betula genus contains 30–60 known taxa...
, Maple
Maple
Acer is a genus of trees or shrubs commonly known as maple.Maples are variously classified in a family of their own, the Aceraceae, or together with the Hippocastanaceae included in the family Sapindaceae. Modern classifications, including the Angiosperm Phylogeny Group system, favour inclusion in...
). An additional caveat is that assembling a realistic-looking forest could not be done by simply assembling trees because in the real world there are interactions between the various trees which can dramatically change their appearance and distribution.
In 2004, a PC first-person shooter
First-person shooter
First-person shooter is a video game genre that centers the gameplay on gun and projectile weapon-based combat through first-person perspective; i.e., the player experiences the action through the eyes of a protagonist. Generally speaking, the first-person shooter shares common traits with other...
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 have to be released on DVDs, often exceeding 2 gigabytes in size, more than 20,000,000 times larger. Naked Sky's
Naked Sky Entertainment
Naked Sky Entertainment is an independent game development studio based in Los Angeles. They are a licensed developer for Microsoft Xbox 360, Sony PlayStation 3, Nintendo Wii, and Apple iPhone...
RoboBlitz
RoboBlitz
Since its release, RoboBlitz has garnered much critical acclaim and has been recognized with several awards and honors. The game was nominated for the 2007 Independent Games Festival for both the Seumas McNally Grand Prize and Excellence in Visual Art awards...
used procedural generation to maximize content in a less than 50MB downloadable file for Xbox Live Arcade
Xbox Live Arcade
Xbox Live Arcade is a type of video game download distribution available primarily in a section of the Xbox Live Marketplace, Microsoft's digital distribution network for the Xbox 360, that focuses on smaller downloadable games from both major publishers and independent game developers...
. Will Wright's Spore also makes use of procedural synthesis.
In 2008, Valve Software released Left 4 Dead
Left 4 Dead
Left 4 Dead is a cooperative first-person shooter video game. It was developed by Turtle Rock Studios, which was purchased by Valve Corporation during development. The game uses Valve's proprietary Source engine, and is available for Microsoft Windows, Xbox 360 and Mac OS X...
, a first-person shooter based on the Source engine
Source engine
Source is a 3D game engine developed by Valve Corporation. It debuted in June 2004 with Counter-Strike: Source and shortly thereafter Half-Life 2, and has been in active development ever since...
that utilized procedural generation as a major game mechanic. The game featured a built-in artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
structure, dubbed the "Director," which analyzed player statistics and game states on the fly to provide dynamic experiences on each and every playthrough. Based on different player variables, such as remaining health, ammo, and number of players, the A.I. Director could potentially create or remove enemies and items so that any given match maintained an exciting and breakneck pace. Left 4 Dead 2
Left 4 Dead 2
Left 4 Dead 2 is a cooperative first-person shooter video game. It is the sequel to Valve Corporation's award-winning Left 4 Dead. The game launched on November 17, 2009, for Microsoft Windows and Xbox 360 in the United States and November 20 in Europe; in 2010, Left 4 Dead 2 was made available to...
, released in November 2009, expanded on this concept, introducing even more advanced mechanics to the A.I. Director, such as the ability to generate new paths for players to follow according to their individual statuses.
An indie game that makes extensive use of procedural generation is Minecraft
Minecraft
Minecraft is a sandbox-building independent video game written in Java originally by Swedish creator Markus "Notch" Persson and now by his company, Mojang, formed from the proceeds of the game. It was released as an alpha on May 17, 2009, with a beta version on December 20, 2010...
. In the game the initial state of the world is mostly random (with guidelines in order to generate Earth-like terrain), and new areas are generated whenever the player moves towards the edges of the world. This has the benefit that every time a new game is made, the world is completely different and will need a different method to be successful, adding replay value.
Another indie game that relies heavily on procedural generation is Dwarf Fortress
Dwarf Fortress
Slaves to Armok: God of Blood, Chapter II: Dwarf Fortress, also called Slaves to Armok II: Dwarf Fortress, but most commonly known simply as Dwarf Fortress, is a freeware computer game by Bay 12 Games for Microsoft Windows, Linux, and Mac OS X set in a high fantasy universe that combines aspects of...
. In the game the whole world is generated, completely with its history, notable people, and monsters.
Film
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
Perlin noise
Perlin noise is a computer-generated visual effect developed by Ken Perlin, who won an Academy Award for its use in the motion picture Tron...
. 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 automata are 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."
Such simple rules, even in the simplest case of two colors, can produce a complex evolution (see Rule 30
Rule 30
Rule 30 is a one-dimensional binary cellular automaton rule introduced by Stephen Wolfram in 1983. Wolfram describes it as being his "all-time favourite rule" and details it in his book, A New Kind of Science...
and Rule 110).
For game developers, this means that, using 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.
Middleware
- Acropora - a procedural 3D modeling software utilizing voxels to create organic objects and terrain.
- Art of IllusionArt of IllusionArt of Illusion is a software package used for 3D modeling, texturing, ray tracing, and otherwise rendering computer generated imagery stills or animations ....
– an open source and free 3D modeler, has an internal node-based procedural texture editor. - CityEngine – a procedural 3D modeling software, specialized in city modeling.
- CityScapeCityscapeA cityscape is the urban equivalent of a landscape. Townscape is roughly synonymous with cityscape, though it implies the same difference in urban size and density implicit in the difference between the words city and town. In urban design the terms refer to the configuration of built forms and...
- procedural generation of 3D cities, including overpasses and tunnels, from GIS data. - Filter ForgeFilter ForgeFilter Forge is a standalone application and plugin for Adobe Photoshop and compatible 8bf plugin hosts that allows users to apply programmable image processing filters and to define them with a visual node-based filter editor...
– an Adobe PhotoshopAdobe PhotoshopAdobe Photoshop is a graphics editing program developed and published by Adobe Systems Incorporated.Adobe's 2003 "Creative Suite" rebranding led to Adobe Photoshop 8's renaming to Adobe Photoshop CS. Thus, Adobe Photoshop CS5 is the 12th major release of Adobe Photoshop...
plugin for designing procedural textures using node-based editing. - GromeGromeGrome is an environmental modeling package developed by Quad Software dedicated for procedural and manual generation of large virtual outdoor worlds suitable for games and other 3D real-time simulation applications.- History :...
– popular terrain and outdoor scenes modeler for games and simulation software. - HoudiniHoudini (software)Houdini is a high-end 3D animation package developed by Side Effects Software which is headquartered in Toronto, Canada. It is a rewrite of the PRISMS ecosystem of standalone tools. Its chief distinction from other packages is that it has been designed as a purely procedural environment...
- a procedural 3D animation package. A free version of the software is available. - Allegorithmic Substance – a middlewareMiddlewareMiddleware is computer software that connects software components or people and their applications. The software consists of a set of services that allows multiple processes running on one or more machines to interact...
and authoring software designed to create and generate procedural textures in games (used in RoboBlitzRoboBlitzSince its release, RoboBlitz has garnered much critical acclaim and has been recognized with several awards and honors. The game was nominated for the 2007 Independent Games Festival for both the Seumas McNally Grand Prize and Excellence in Visual Art awards...
). - Softimage - a 3D computer graphics application that allows node-based procedural creation and deformation of geometry.
- SpeedTreeSpeedTreeSpeedTree is a group of vegetation programming and modeling software products developed and sold by Interactive Data Visualization, Inc. that generates virtual foliage for animations and in real time for video games and simulations...
– a middleware product for procedurally generating trees. - TerragenTerragenTerragen is a scenery generator program for Microsoft Windows and Mac OS X developed and published by Planetside Software. It can be used to create renderings and animations of landscapes.-History:...
– landscape generation software. Terragen 2 permits procedural generation of an entire world. - Ürban PAD – a software for creating and generating procedural urban landscape in games.
- World Machine - a powerful node-based procedurally generated terrain software with a plugin system to write new, complex nodes. Exports to Terragen, among other formats, for rendering, as well as having internal texture generation tools. See http://www.world-machine.com/
Space simulations with procedural worlds and universes
- Elite (1984) - Everything about the universe, planet positions, names, politics and general descriptions, is generated procedurally; Ian BellIan Bell (programmer)Ian Colin Graham Bell is a game programmer, game designer and game producer. He is most famous for co-authoring the computer game Elite .He attended the independent St Albans School...
has released the algorithms in C as text elite - StarFlightStarflightStarflight is a computer game published by Electronic Arts and developed by Binary Systems in 1986. Originally developed for DOS and Tandy, it was later released for the Amiga, Atari ST, Macintosh and Commodore 64...
(1986) - Exile (1988) - Game levels were created in a pseudorandom fashion, as areas important to gameplay were generated.
- Frontier: Elite II (1993) - Much as the game Elite had a procedural universe, so did its sequel.
- Frontier: First Encounters (1995)
- Mankind (1998) - a MMORTS where everything about the galaxy, systems names, planets, maps and resources is generated procedurally from a simple tga image.
- NoctisNoctisNoctis is an open source computer space flight simulator featuring first-person visual exploration of an imaginary galaxy...
(2002) - Infinity: The Quest for Earth (In development, not yet released)
- Vega StrikeVega StrikeVega Strike is a first-person space trading and combat simulator, developed for Microsoft Windows, POSIX Unix-like operating systems such as Linux, and Mac OS X systems. Many of the core game mechanics of Vega Strike are indirectly inspired by Elite...
- An open source game very similar to Elite.
Games with procedural levels
Arcade games- The SentinelThe Sentinel (computer game)The Sentinel is a computer game created by Geoff Crammond, published by Firebird in 1986 for the BBC Micro and converted to the C64 , Amstrad CPC , ZX Spectrum , Atari ST, Amiga and PC . It was released in the US as The Sentry...
(1986) - Used procedural generation to create 10,000 unique levels. - DarwiniaDarwinia (computer game)Darwinia is the second game by Introversion Software.-Plot:Darwinia was created as a digital theme world for artificially intelligent polygons by Dr. Sepulveda. Housed in a massive network of surplus Protologic 68000 machines from the 1980s, Darwinia is a world where the single-poly Darwinians,...
(2005) - Has procedural landscapes that allowed for greatly reduced game development time.
Racing games
- FuelFuel (2009 video game)Fuel is a racing video game developed by Asobo Studio and published by Codemasters, released on June 2, for PlayStation 3 and Xbox 360, and June 5, for Microsoft Windows.-Gameplay:...
(2009) - Generates an open worldOpen worldAn open world is a type of video game level design where a player can roam freely through a virtual world and is given considerable freedom in choosing how to approach objectives...
through procedural techniques
Role-playing games
- Captive (1990) generates (theoretically up to 65,535) game levels procedurally
- Virtual HydlideVirtual HydlideVirtual Hydlide is an action-adventure video game for the Sega Saturn console, developed by T&E Soft. It is a remake of the original Hydlide, the first game in the series, but incorporated full 2.5D graphics....
(1995) - The Elder Scrolls II: DaggerfallThe Elder Scrolls II: DaggerfallThe Elder Scrolls II: Daggerfall is a first-person, traditional role-playing video game for MS-DOS developed by Bethesda Softworks and released in 1996. It is a sequel to the RPG The Elder Scrolls: Arena and the second installment in The Elder Scrolls series. On July 9, 2009, it was made available...
(1996) - DiabloDiablo (video game)Diablo is a dark fantasy-themed action role-playing game developed by Blizzard North and released by Blizzard Entertainment on December 31, 1996....
(1998) and Diablo IIDiablo IIDiablo II is a dark fantasy/horror-themed hack and slash, with elements of the role playing game and dungeon crawl genres. It was released for Windows and Mac OS in 2000 by Blizzard Entertainment, and was developed by Blizzard North. It is a direct sequel to the 1996 hit PC game, Diablo.Diablo II...
(2000) both use procedural generation for level design. - TorchlightTorchlightTorchlight is an action role-playing game developed by Runic Games and published by Perfect World, released for Windows in October 2009. The fantasy-themed game is set in the fictional town of Torchlight and the expansive caverns and dungeons nearby, which adventurers explore to collect valuable...
, a Diablo clone differing mostly by art style and feel. - Dwarf FortressSlaves to Armok II: Dwarf FortressSlaves to Armok: God of Blood, Chapter II: Dwarf Fortress, also called Slaves to Armok II: Dwarf Fortress, but most commonly known simply as Dwarf Fortress, is a freeware computer game by Bay 12 Games for Microsoft Windows, Linux, and Mac OS X set in a high fantasy universe that combines aspects of...
procedurally generates a large game world, including civilization structures, a large world history, interactive geography including erosion and magma flows, ecosystems which react with each other and the game world. The process of initially generating the world can take up to half an hour even on a modern PC, and is then stored in text files reaching over 100MB to be reloaded whenever the game is played. - Dark CloudDark Cloudis a role-playing video game for the PlayStation 2 video game console. It was developed by Level-5 and published by Sony Computer Entertainment in 2000 and 2001 in Japan and American/PAL regions respectively. The gameplay of Dark Cloud combines action role-playing with elements of city-building...
and Dark Cloud 2 both generate game levels procedurally. - Hellgate: LondonHellgate: LondonHellgate: London is a dark fantasy themed action role-playing game originally developed by Flagship Studios, released on October 31, 2007. It was developed by a team headed by former Blizzard Entertainment employees, some of whom had overseen the creation of the Diablo series...
(2007) - The DisgaeaDisgaeais a video game series of tactical role-playing games created and developed by Nippon Ichi. The series debuted in Japan on January 30, , with Disgaea: Hour of Darkness, later re-released as Disgaea: Afternoon of Darkness and Disgaea DS. One of Nippon Ichi's most popular franchises, it has branched...
series of games use procedural level generation for the "Item World". - Realm of the Mad GodRealm of the Mad GodRealm of the Mad God is a massive multiplayer browser game created by Wild Shadow Studios in partnership with Spry Fox, two independent developers...
- Nearly all roguelikeRoguelikeThe roguelike is a sub-genre of role-playing video games, characterized by randomization for replayability, permanent death, and turn-based movement. Most roguelikes feature ASCII graphics, with newer ones increasingly offering tile-based graphics. Games are typically dungeon crawls, with many...
s use this technique.
Strategy games
- Majesty:The Fantasy Kingdom SimMajesty: The Fantasy Kingdom Sim-External links:**...
(2000) - Uses procedural generation for all levels and scenarios. - Seven KingdomsSeven Kingdoms (computer game)Seven Kingdoms is a real-time strategy computer game developed by Trevor Chan of Enlight Software. The game enables players to compete against up to six other kingdoms allowing players to conquer opponents by defeating them in war , capturing their buildings with spies, or offering opponents...
(1997) - Uses procedural generation for levels. - XconqXconqXconq is an open source computer strategy game and game engine. First posted to comp.sources.games in 1987, it is notable as one of the first multi-player games to be released for the X Window System...
- an open source strategy game and game engine. - MinecraftMinecraftMinecraft is a sandbox-building independent video game written in Java originally by Swedish creator Markus "Notch" Persson and now by his company, Mojang, formed from the proceeds of the game. It was released as an alpha on May 17, 2009, with a beta version on December 20, 2010...
- The game world is procedurally generated as the player explores it, with the full size possible stretching out to be nearly eight times the surface area of the Earth before running into technical limits. - Frozen SynapseFrozen Synapse-External links:****...
- Levels in single player are mostly randomly generated, with bits and pieces that are constant in every generation. Multiplayer maps are randomly generated. Skirmish maps are randomly generated, and allow the player to change the algorithm used. - Atom Zombie Smasher - Levels are generated randomly.
Games with yet unknown genre
- SubversionSubversion (computer game)Subversion is the name for a planned game from Introversion Software. It makes heavy use of procedurally generated content. A generator capable of building a model city, complete with buildings, roads and highways was demonstrated at an Imperial College Games and Media event. Development of the...
(TBA) - Uses procedural generation to create cities on a given terrain.
Third-person shooters
- Just CauseJust Cause (video game)Just Cause is an open world action-adventure video game developed by Avalanche Studios and published by Eidos Interactive. It was released for Microsoft Windows, PlayStation 2, Xbox, Xbox 360 on September 22, 2006 in Europe, September 27, 2006 in North America, September 29, 2006 in Australia and...
(2006) - Game area is over 250000 acres (1,011.7 km²), created procedurally
Almost entirely procedural games
- NoctisNoctisNoctis is an open source computer space flight simulator featuring first-person visual exploration of an imaginary galaxy...
(2000) - .kkrieger.kkrieger.kkrieger is a first-person shooter video game created by German demogroup .theprodukkt which won first place in the 96k game competition at Breakpoint in April 2004...
(2004) - Synth video game (2009) - 100% procedural graphics and levels
Games with miscellaneous procedural effects
- ToeJam & EarlToeJam & EarlToeJam & Earl is an action video game developed by Johnson Voorsanger Productions and published by Sega for the Mega Drive video game console. Released in 1991, it centers on the titular ToeJam and Earl—alien rappers who have crash-landed on Earth. As they attempt to escape the planet, players...
(1991) - The random levels were procedurally generated. - The Elder Scrolls III: MorrowindThe Elder Scrolls III: MorrowindThe Elder Scrolls III: Morrowind, often simply referred to as Morrowind, is a single-player computer role-playing game developed by Bethesda Game Studios, and published by Bethesda Softworks and Ubisoft. It is the third installment in The Elder Scrolls series of games, following The Elder Scrolls...
(2002) - Water effects are generated on the fly with procedural animationProcedural animationA procedural animation is a type of computer animation, used to automatically generate animation in real-time to allow for a more diverse series of actions than could otherwise be created using predefined animations....
by the technique demonstrated in NVIDIANVIDIANvidia is an American global technology company based in Santa Clara, California. Nvidia is best known for its graphics processors . Nvidia and chief rival AMD Graphics Techonologies have dominated the high performance GPU market, pushing other manufacturers to smaller, niche roles...
's "Water Interaction" demo. - RoboBlitzRoboBlitzSince its release, RoboBlitz has garnered much critical acclaim and has been recognized with several awards and honors. The game was nominated for the 2007 Independent Games Festival for both the Seumas McNally Grand Prize and Excellence in Visual Art awards...
(2006) for XBox360 live arcade and PC (Textures generated on the fly via ProFX) - SporeSpore (2008 video game)Spore is a multi-genre single-player god game developed by Maxis and designed by Will Wright. The game was released for the Microsoft Windows and Macintosh operating systems in September 2008 as Spore...
(2008) - Left 4 DeadLeft 4 DeadLeft 4 Dead is a cooperative first-person shooter video game. It was developed by Turtle Rock Studios, which was purchased by Valve Corporation during development. The game uses Valve's proprietary Source engine, and is available for Microsoft Windows, Xbox 360 and Mac OS X...
(2008) - Certain events, item locations, and number of enemies are procedurally generated according to player statistics. - Left 4 Dead 2Left 4 Dead 2Left 4 Dead 2 is a cooperative first-person shooter video game. It is the sequel to Valve Corporation's award-winning Left 4 Dead. The game launched on November 17, 2009, for Microsoft Windows and Xbox 360 in the United States and November 20 in Europe; in 2010, Left 4 Dead 2 was made available to...
(2009) - Certain areas of maps are randomly generated and weather effects are dynamically altered based on current situation. - BorderlandsBorderlands (video game)Borderlands is a science fiction based first-person shooter with RPG elements that was developed by Gearbox Software for PlayStation 3, Xbox 360, Microsoft Windows and Mac OS X. It was first revealed in the September 2007 issue of Game Informer magazine...
(2009) - The weapons, items and some levels are procedurally generated based on individual players' current level. - Star Trek OnlineStar Trek OnlineStar Trek Online, often abbreviated as STO, is a massively multiplayer online role-playing game developed by Cryptic Studios based on the popular Star Trek series created by Gene Roddenberry. The game is set in the 25th century, 30 years after the events of Star Trek Nemesis...
(2010) - Star Trek Online procedurally generates new races, new objects, star systems and planets for exploration. The player can save the coordinates of a system they find, so that they can return or let other players find the system. - TerrariaTerrariaTerraria is an action-adventure/RPG indie game released by independent game studio Re-Logic. The game features exploration, crafting, building structures and combat with a variety of creatures...
(2011) - Terraria procedurally generates a 2D landscape for the player to explore. - Invaders: Corruption (2010) - A free, procedurally generated arena-shooter
See also
- Artificial Creativity
- Procedural modelingProcedural modelingProcedural modeling is an umbrella term for a number of techniques in computer graphics to create 3D models and textures from sets of rules. L-Systems, fractals, and generative modeling are procedural modeling techniques since they apply algorithms for producing scenes...
- Procedural textureProcedural textureA procedural texture is a computer generated image created using an algorithm intended to create a realistic representation of natural elements such as wood, marble, granite, metal, stone, and others....
- Procedural animationProcedural animationA procedural animation is a type of computer animation, used to automatically generate animation in real-time to allow for a more diverse series of actions than could otherwise be created using predefined animations....
- Scenery generatorScenery generatorA scenery generator refers to software used to create landscape images, 3D models, and animations. These programs use procedural generation to generate the landscapes.- Software :*Bryce is most famous for landscapes....
- Fractal landscapeFractal landscapeA fractal landscape is a surface generated using a stochastic algorithm designed to produce fractal behaviour that mimics the appearance of natural terrain...
- Cellular automata
- Digital morphogenesisDigital morphogenesisDigital morphogenesis is a process of shape development enabled by computation. While this concept is applicable in many areas, the term "digital morphogenesis" is used primarily in architecture....
- L-SystemL-systemAn L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms...
- Perlin noisePerlin noisePerlin noise is a computer-generated visual effect developed by Ken Perlin, who won an Academy Award for its use in the motion picture Tron...
- Random dungeonRandom dungeonA random dungeon is a dungeon in a role-playing video game which is procedurally generated by the computer using an algorithm, such that the dungeon is laid out differently every time the player enters it, and a player often never plays through quite the same dungeon twice. Random dungeons are...
- Generative Modelling LanguageGenerative Modelling LanguageGenerative Modelling Language in computer graphics and generative computer programming is a very simple programming language for the concise description of complex 3D shapes...
- Iterated function systemIterated function systemIn mathematics, iterated function systems or IFSs are a method of constructing fractals; the resulting constructions are always self-similar....
- Generative artGenerative artGenerative art refers to art that has been generated, composed, or constructed in an algorithmic manner through the use of systems defined by computer software algorithms, or similar mathematical or mechanical or randomised autonomous processes....
- Synth video game
- Shape grammarShape grammarShape grammars in computation are a specific class of production systems that generate geometric shapes. Typically, Shapes are 2- or 3-dimensional, thus shape grammars are a way to study 2- and 3-dimensional languages. Shape grammars have been studied in particular in computer-aided architectural...
External links
- The Future Of Content - Will Wright keynote on Spore & procedural generation at the Game Developers ConferenceGame Developers ConferenceThe Game Developers Conference is the largest annual gathering of professional video game developers, focusing on learning, inspiration, and networking...
2005. (registration required to view video). - Darwinia - development diary procedural generation of terrains and trees.
- Filter Forge tutorial at The Photoshop Roadmap
- Procedural Graphics - an introduction by in4k
- Texturing & Modeling:A Procedural Approach
- Ken Perlin's Discussion of Perlin Noise
- The HVox Engine: Procedural Volumetric Terrains on the Fly (2004)
- Procedural Content Generation Wiki: a community dedicated to documenting, analyzing, and discussing all forms of procedural content generation.
- Procedural Trees and Procedural Fire in a Virtual World: A white paper on creating procedural trees and procedural fire using the Intel Smoke framework
- A Real-Time Procedural Universe a tutorial on generating procedural planets in real-time