Procedural generation

In computing, procedural generation is a method of creating data algorithmically as opposed to manually. In computer graphics, it is also called random generation and is commonly used to create textures and 3D models. In video games it is used to automatically create large amounts of content in a game. Advantages of procedural generation include smaller file sizes, larger amounts of content, and randomness for less predictable gameplay.

Overview

The term procedural refers to the process that computes a particular function. Fractals are geometric patterns which can often be generated procedurally. Commonplace procedural content includes textures and meshes. Sound is often also procedurally generated, 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".^[1]

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 in 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, while its sequel featured a randomly-generated level mode. Avalanche Studios employed procedural generation to create a large and varied group of detailed tropical islands for Just Cause. No Man's Sky, a game developed by games studio Hello Games, is all based upon procedurally generated elements.

The modern demoscene uses procedural generation to package a great deal of audiovisual content into relatively small programs.

New methods and applications are presented annually in conferences such as the IEEE Conference on Computational Intelligence and Games and Artificial Intelligence and Interactive Digital Entertainment.^[2]

Contemporary application

Video games

RoboBlitz used procedurally generated textures in order to reduce the file size of the game

Early history

Prior to graphically-oriented video games, roguelike games, including Beneath Apple Manor (1978) and the genre's namesake, Rogue (1980), used procedural generation to construct dungeons for ASCII- or regular tile-based systems. The procedural generation would define rooms, hallways, monsters, and treasure that the player would find. Roguelikes, and games based on the roguelike concepts, continue to be a popular genre, as it allows the development of complex gameplay without having to spend excessive time in creating a game's world.^[3]

The earliest graphical computer games were severely limited by memory constraints. This forced content, such as maps, to be generated algorithmically on the fly: there simply was not 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 to be premade.

Perhaps the first game to use a seed to generate the world is Richard Garriott's Akalabeth (1980); by using the same seed number, a player can always return to a given world.^[4] The Sentinel supposedly had 10,000 different levels stored in only 48 and 64 kilobytes. An extreme case was Elite, which was originally planned to contain a total of 2⁴⁸ (approximately 282 trillion) galaxies with 256 solar systems each. However, the publisher was afraid that such a gigantic universe would cause disbelief in players, and eight of these galaxies were chosen for the final version.^[5] 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.

As computer hardware advanced and CDs became able to store thousands of times more data than was possible in the early 80s, using procedural generation to build large worlds became unnecessary. Game content, such as textures, and character and environment models, is often created by artists beforehand, to keep the quality of the content consistently high.

Storing unique designs in the game's memory, rather than producing multiple objects using similar guidelines, allows a variety of detailed models that are each substantially different. However, when each model needs to be designed by hand, a limited number of objects will exist. Some initial approaches to procedural synthesis attempted to solve this problem by shifting the burden of content generation from the artists to programmers who can create code that automatically generates different meshes according to input parameters.

Although this still happens on occasion, 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 is widely considered 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 premade assets or to apply some distortions to them procedurally.

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 similar level of immersion to the player. This method would require far more processing power, but since CPUs are constantly increasing in speed this 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 that can dramatically change their appearance and distribution.

Modern use

Though modern computer games do not have the same memory and hardware restrictions that earlier games had, the use of procedural generation is frequently employed to create randomized games, maps, levels, characters, or other facets that are unique on each playthrough.^[6][7]

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 times larger. Naked Sky's RoboBlitz used procedural generation to maximize content in a less than 50 MB downloadable file for Xbox Live Arcade. Will Wright's Spore also makes use of procedural synthesis.

Procedural generation is often used in loot systems of quest-driven games, such as action role-playing games and massive multiplayer online role playing games. Though quests may feature fixed rewards, other loot, such as weapons and armor, may be generated for the player based on the player-character's level, the quest's level, their performance in the quest, and other random factors. This often leads to loot having a rarity quality applied to reflect when the procedural generation system has produced an item with better-than-average attributes. For example, the Borderlands series is based on its procedural generation system which can create over a million unique guns and other equipment.^[8]

Many open world or survival games procedurally create a game world from a random seed or one provided by the player, so that each playthrough is different. These generation systems create numerous pixel- or voxel-based biomes with distribution of resources, objects, and creatures. The player frequently has the ability to adjust some of the generation parameters, such as specifying the amount of water coverage in a world. Examples of such games include Dwarf Fortress and Minecraft. An artifact of the procedural generation around these games is that if the space that the player is allowed to explore is not limited, the randomness of the procedural generation will start to produce more noise than content; this is exemplified in the idea of the "Far Lands" within some earlier versions Minecraft, where the usual smooth transitions between biomes was replaced with haphazard formations.^[9]

Procedural generation is also used in open-world games of very large scale, particularly in space flight simulator games. Elite: Dangerous, though using the 400 billion known stars of the Milky Way Galaxy as its world basis, uses procedural generation to simulate the planets in these solar systems. Similarly, Star Citizen utilises the technology for its planets, to create a collection of seamlessly-loaded planet-sized planets among its hand-crafted universe. I-Novae Infinity features a plethora of planets which are procedurally generated between which the player can travel via space ships. Outerra Anteworld is a video game in development that uses procedural generation and real world data to create a virtual replica of planet Earth in true scale. No Man's Sky features a universe containing 18 quintillion planets which are procedurally generated on the fly as the player encounters them, including their terrain, weather, flora, and fauna, as well as a number of space-faring alien species. This universe is defined by the use of a single random seed number to their deterministic engine, assuring that the same content will generated at the same places for all players, which enables players to share discoveries using only knowledge of the locations of the planets in the virtual galaxy.^[10][11]

Games that feature co-operative play may use procedural generation to craft unique experiences for the players as they complete the game. The Left 4 Dead series, based on a zombie apocalypse setting, uses an AI Director, an artificial intelligence that monitors the behavior of the players and creates a dynamic experience to keep players alert. It can sense when players have become comfortable and spawn new zombies and hordes to attack the players in mid-level and alter which routes are available for players to take. Similar concepts are used for games like Warhammer: End Times – Vermintide and Evolve.^[12]

Film

As in video games, procedural generation is often used in film to create visually interesting and accurate spaces rapidly. This comes in a wide variety of applications.

One application is known as an imperfect factory, where artists can generate a large number of similar objects rapidly. 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.

MASSIVE is a high-end computer animation and artificial intelligence software package used for generating crowd-related visual effects for film and television. It was developed to create fighting armies of hundreds of thousands of soldiers for Peter Jackson's The Lord of the Rings films automatically.^[13]

Coherent noise can be extremely important to procedural workflow in film. Simplex noise is often faster with fewer artifacts, though an older function called Perlin noise may be used as well. Coherent noise, in this case, refers to a function that generates smooth pseudo-randomness in n dimensions.

Games which use procedural generation

Notable games which use procedural generation include those listed below. For a full list, visit the article above.

• Rogue (1980)
• Elite (1984)
• Diablo (1996)
• Diablo II (2000)
• Shin Megami Tensei: Persona 3 (2006)
• Shin Megami Tensei: Persona 4 (2008)
• Spelunky (2008)
• Spore (2008)
• Left 4 Dead (2008)
• Left 4 Dead 2 (2009)
• Minecraft (2011)
• Terraria (2011)
• Diablo III (2012)
• Rust (2013)
• Elite: Dangerous (2014)
• No Man's Sky (2016)
• Star Citizen (to be confirmed)

See also

• Procedural modeling
• Procedural texture
• Procedural animation
• Scenery generator
• Random map
• Random dungeon
• Fractal landscape
• Computational creativity
• Generative art

References

Further reading

• David S. Ebert, F. Kenton Musgrave, Darwyn Peachey, Ken Perlin, and Steve Worley (2002). Texturing and Modeling: A Procedural Approach (3rd ed.). Morgan Kaufmann. ISBN 978-1-558-60848-1.  CS1 maint: Multiple names: authors list (link)
• Noor Shaker, Julian Togelius, and Mark J. Nelson (2016). Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer. ISBN 978-3-319-42714-0.  CS1 maint: Multiple names: authors list (link)

External links

• The Future Of Content – Will Wright keynote on Spore & procedural generation at the Game Developers Conference 2005
• Ken Perlin's Discussion of Perlin Noise
• 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
• Search-based procedural content generation: a taxonomy and survey