Procedural generation

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computing, procedural generation is a method of creating data algorithmically as opposed to manually, typically through a combination of human-generated assets and algorithms coupled with computer-generated randomness and processing power. In computer graphics, it 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[edit]

One example of procedural generation, here used to generate realistic looking tree models. Different models can be generated by changing both deterministic parameters and a random seed.

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 two thirds 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[edit]

Video games[edit]

Early history[edit]

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, allow the development of complex gameplay without having to spend excessive time in creating a game's world.[3]

1978's Maze Craze for the Atari VCS used an algorithm to generate a random, top-town maze for each game.[4]

Some games used pseudorandom number generators were often used with predefined seed values in order to generate very large game worlds that appeared to be premade. 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 248 (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.

Modern use[edit]

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 by a German demo group. It is entirely contained in a 96 kilobyte executable for Microsoft Windows that generates hundreds of megabytes of 3D and texture data when run. According to one of the programmers, "it was a complete failure as far as the game side was concerned (mostly because no-one involved really deeply cared about that aspect)."[8]

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.[9]

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 of Minecraft, where the usual smooth transitions between biomes was replaced with haphazard formations.[10]

Procedural generation is also used in space exploration and trading 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 uses 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 be 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.[11][12]

Film[edit]

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.

See also[edit]

References[edit]

  1. ^ Brian Eno (June 8, 1996). "A talk delivered in San Francisco, June 8, 1996". inmotion magazine. Retrieved 2008-11-07.
  2. ^ "Artificial Intelligence and Interactive Digital Entertainment". AIIDE.org. Retrieved 12 June 2016.
  3. ^ Hatfield, Tom (2013-01-29). "Rise Of The Roguelikes: A Genre Evolves". GameSpy. Retrieved 2013-04-24.
  4. ^ "Maze Craze". Atari Mania.
  5. ^ Francis Spufford (October 18, 2003). "Masters of their universe". Guardian.
  6. ^ Moss, Richard (January 1, 2016). "7 uses of procedural generation that all developers should study". Gamasutra. Retrieved January 1, 2016.
  7. ^ Baker, Chris (9 August 2016). "'No Man's Sky': How Games Are Building Themselves". Rolling Stone. Retrieved 9 August 2016.
  8. ^ Giesen, Fabien (April 8, 2012). "Metaprogramming for madmen". The ryg blog.
  9. ^ Kuo, Ryan (April 19, 2012). "Why Borderlands 2 Has the Most Stylish Guns in Gaming". Wall Street Journal. Retrieved April 21, 2016.
  10. ^ Peckham, Matt (8 August 2016). "NO MAN'S SKY IS WILDLY AMBITIOUS, UTTERLY VAST AND A HUGE CHALLENGE TO THE VIDEO GAME INDUSTRY'S STATUS QUO". Time. Retrieved 9 August 2016.
  11. ^ Khatchadourian, Raffi (18 May 2015). "World without end : creating a full-scale digital cosmos". Annals of Games. The New Yorker. 91 (13). pp. 48–57. Retrieved 5 August 2015.
  12. ^ Wilson (16 July 2015). "How 4 Designers Built A Game With 18.4 Quintillion Unique Planets". Fast Company. Retrieved 9 August 2015.
  13. ^ "About Massive". Massive Software. Retrieved 12 June 2016.

Further reading[edit]

External links[edit]