Procedural generation

In computing, procedural generation is a method of creating data algorithmically as opposed to manually. In computer graphics it is commonly used for creating textures. In video games it is used for creating items, quests, and level geometry. 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, an example of procedural generation, express this concept, around which a whole body of mathematics—fractal geometry—has developed. 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".[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 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, while its sequel featured a randomly-generated level mode. Avalanche Studios employed procedural generation to create a large and varied group of tropical islands in great detail for Just Cause. "No Man's Sky," a game being 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

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 starting with 1978's Beneath Apple Manor used procedural generation to construct dungeons for ASCII-based systems (although Beneath Apple Manor used Lo-Res 16-color graphics). 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 in the present, as it allows the development of complex gameplay without having to spend excessive time in creating a game's world.[2]

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 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.

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.[3] 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. 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.[4] 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 as much 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 are often created by artists beforehand, so to keep the quality of 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 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 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.[5]

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 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.

One indie game that relies heavily on procedural generation is Dwarf Fortress, first released in 2006 and under active development. Before the player starts a game a whole fantasy world is generated, based on a complex set of configuration options, complete with its terrain, history, notable characters, and monsters. Another indie game that makes extensive use of procedural generation is Minecraft, first released in 2009. 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. Both Dwarf Fortress and Minecraft have the benefit that every time a new world is made, it is completely different and will need a different method to be successful, adding replay value.

The 400 billion star-systems big Milky Way Galaxy is being procedurally generated in Elite: Dangerous in true scale. Released in 2014, the game makes use of higher detailed procedural generation of the planets surfaces for planetary landing.

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. Another game in development is I-Novae Infinity which features a plethora of planets which are procedurally generated and between which the player can travel via space ships.

No Man's Sky, set to be released in June 2016,[6] is a game that allows players to explore planets that are procedurally generated. According to the developers, this allows for more than 18 quintillion possible planets. Planets, their terrain, weather, flora, and fauna are all generated by the use of a single random seed number to their engine, assuring that the same planet can be visited by players using only knowledge of the seed number, in this case, the location of the planet in the virtual galaxy. The engine uses mathematical formulas that, with adjustable parameters, can mimic a diverse number of natural formations, such as the Superformula and L-systems.[7][8]

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.

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 automatically generate fighting armies of hundreds of thousands of soldiers for Peter Jackson's The Lord of the Rings films.

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

References

  1. ↑ Brian Eno (June 8, 1996). "A talk delivered in San Francisco, June 8, 1996". inmotion magazine. Retrieved 2008-11-07.
  2. ↑ Hatfield, Tom (2013-01-29). "Rise Of The Roguelikes: A Genre Evolves". Gamespy. Retrieved 2013-04-24.
  3. ↑ Maher, Jimmy (2011-12-18). "Akalabeth". The Digital Antiquarian. Retrieved 9 July 2014.
  4. ↑ Francis Spufford (October 18, 2003). "Masters of their universe". Guardian.
  5. ↑ Moss, Richard (January 1, 2016). "7 uses of procedural generation that all developers should study". Gamasutra. Retrieved January 1, 2016.
  6. ↑ Chloi Rad (27 October 2015). "No Man's Sky Release Window Announced". IGN.
  7. ↑ 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.
  8. ↑ Wilson (16 July 2015). "How 4 Designers Built A Game With 18.4 Quintillion Unique Planets". Fast Company. Retrieved 9 August 2015.

External links

This article is issued from Wikipedia - version of the Wednesday, February 03, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.