Procedural generation

Last updated
One example of procedural generation, here using L-systems to generate realistic looking tree models. Different models can be generated by changing both deterministic parameters and a random seed. Dragon trees.jpg
One example of procedural generation, here using L-systems to generate realistic looking tree models. Different models can be generated by changing both deterministic parameters and a random seed.

In computing, procedural generation (sometimes shortened as proc-gen) is a method of creating data algorithmically as opposed to manually, typically through a combination of human-generated content 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. Depending on the implementation, advantages of procedural generation can include smaller file sizes, larger amounts of content, and randomness for less predictable gameplay. Procedural generation is a branch of media synthesis.

Contents

Overview

A procedural landscape rendered in Terragen Terragen.jpg
A procedural landscape rendered in Terragen

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]

Procedurally generated textures Tiling procedural textures.jpg
Procedurally generated textures

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 the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. [2]

Particularly in the application of procedural generation with video games, which are intended to be highly replayable, there are concerns that procedural systems can generate infinite numbers of worlds to explore, but without sufficient human guidance and rules to guide these. The result has been called "procedural oatmeal", a term coined by writer Kate Compton, in that while it is possible to mathematically generate thousands of bowls of oatmeal with procedural generation, they will be perceived to be the same by the user, and lack the notion of perceived uniqueness that a procedural system should aim for. [3]

Contemporary application

Tabletop role-playing games

Using procedural generation in games had origins in the tabletop role playing game (RPG) venue. [4] The leading tabletop system, Advanced Dungeons & Dragons , provided ways for the "dungeon master" to generate dungeons and terrain using random die rolls, expanded in later editions with complex branching procedural tables. Strategic Simulations under license from TSR released the Dungeon Master's Assistant, a computer program that generated dungeons based on these published tables. Tunnels & Trolls , published by Flying Buffalo, [5] was designed primarily around solitary play and used similar procedural generation for its dungeons. Other tabletop RPGs borrowed similar concepts in procedural generation for various world elements. [6]

Many online tools for Dungeon Masters now use procedural generation to varying degrees.[ citation needed ]

Video games

Early history

A procedurally generated dungeon map in the videogame NetHack Nethackscreen.gif
A procedurally generated dungeon map in the videogame NetHack

Prior to graphically oriented video games, roguelike games, a genre directly inspired by Dungeons & Dragons adopted for solitaire play, heavily utilized procedural generation to randomly produce dungeons, in the same manner that tabletop systems had done. Such early games include Beneath Apple Manor (1978) and the genre's namesake, Rogue (1980). The procedural generation system in roguelikes would create dungeons in ASCII- or regular tile-based systems and define rooms, hallways, monsters, and treasure to challenge the player. 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. [7]

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

Some games used pseudorandom number generators. These PRNGs 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. [9] 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. [10] 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

Procedural texture using Voronoi tessellation Blender3D VoronoiCrackle.jpg
Procedural texture using Voronoi tessellation

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. [11] [12]

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)." [13]

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

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 .

Procedural generation is also used in space exploration and trading games. Elite: Dangerous , through 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 to create seamlessly loaded 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 , by using procedural generation, is the largest video game in history, featuring a universe of 18 quintillion planets across entire galaxies, which can be explored in flight or on foot. The planets all have their own uniquely diverse terrain, weather, flora, and fauna, as well as a number of space-faring alien species. The same content exists at the same places for all players (thanks to a single random seed number to their deterministic engine), which enables players to meet and share discoveries. [15] [16] [17]

Other applications

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 rapidly generate many 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 to generate many 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. [18]

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

Related Research Articles

<i>NetHack</i> Classical roguelike ASCII graphics computer game released in 1987

NetHack is an open source single-player roguelike video game, first released in 1987 and maintained by the NetHack DevTeam. The game is a fork of the 1982 game Hack, itself inspired by the 1980 game Rogue. The player takes the role of one of several pre-defined character classes to descend through multiple dungeon floors, fighting monsters and collecting treasure, to recover the "Amulet of Yendor" at the lowest floor and then escape.

<span class="mw-page-title-main">Roguelike</span> Subgenre of role-playing video games

Roguelike is a style of role-playing game traditionally characterized by a dungeon crawl through procedurally generated levels, turn-based gameplay, grid-based movement, and permanent death of the player character. Most roguelikes are based on a high fantasy narrative, reflecting their influence from tabletop role-playing games such as Dungeons & Dragons.

<i>Moria</i> (1983 video game) 1983 roguelike video game

The Dungeons of Moria, usually referred to as simply Moria, is a computer game inspired by J. R. R. Tolkien's novel The Lord of the Rings. The objective of the game is to dive deep into the Mines of Moria and kill the Balrog. Moria, along with Hack (1984) and Larn (1986), is considered to be the first roguelike game, and the first to include a town level.

<i>Rogue</i> (video game) 1980 video game

Rogue is a dungeon crawling video game by Michael Toy and Glenn Wichman with later contributions by Ken Arnold. Rogue was originally developed around 1980 for Unix-based minicomputer systems as a freely distributed executable. It was later included in the Berkeley Software Distribution 4.2 operating system (4.2BSD). Commercial ports of the game for a range of personal computers were made by Toy, Wichman, and Jon Lane under the company A.I. Design and financially supported by the Epyx software publishers. Additional ports to modern systems have been made since by other parties using the game's now-open source code.

<span class="mw-page-title-main">Perlin noise</span> Type of gradient noise in computer graphics

Perlin noise is a type of gradient noise developed by Ken Perlin in 1983. It has many uses, including but not limited to: procedurally generating terrain, applying pseudo-random changes to a variable, and assisting in the creation of image textures. It is most commonly implemented in two, three, or four dimensions, but can be defined for any number of dimensions.

In video games, artificial intelligence (AI) is used to generate responsive, adaptive or intelligent behaviors primarily in non-playable characters (NPCs) similar to human-like intelligence. Artificial intelligence has been an integral part of video games since their inception in the 1950s. AI in video games is a distinct subfield and differs from academic AI. It serves to improve the game-player experience rather than machine learning or decision making. During the golden age of arcade video games the idea of AI opponents was largely popularized in the form of graduated difficulty levels, distinct movement patterns, and in-game events dependent on the player's input. Modern games often implement existing techniques such as pathfinding and decision trees to guide the actions of NPCs. AI is often used in mechanisms which are not immediately visible to the user, such as data mining and procedural-content generation.

<span class="mw-page-title-main">Random map</span>

In video games, a random map is a map generated randomly by the computer, usually in strategy games. Random maps are often the core of single and multiplayer gameplay, aside from story based campaigns that are often shipped with the game. Each new game presents an unknown map, providing a new experience to the player, and an even playing field in multiplayer gaming. Random maps typically have a certain theme - for example a naval random map with many small islands, or a 'gold rush' map with a large amount of gold in the center of the map. The type of random map may also influence the game's artificial intelligence, with the AI employing different strategies optimized for each random map.

Procedural 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. The set of rules may either be embedded into the algorithm, configurable by parameters, or the set of rules is separate from the evaluation engine. The output is called procedural content, which can be used in computer games, films, be uploaded to the internet, or the user may edit the content manually. Procedural models often exhibit database amplification, meaning that large scenes can be generated from a much smaller number of rules. If the employed algorithm produces the same output every time, the output need not be stored. Often, it suffices to start the algorithm with the same random seed to achieve this.

<span class="mw-page-title-main">Scenery generator</span> Type of software

A scenery generator is software used to create landscape images, 3D models, and animations. These programs often use procedural generation to generate the landscapes. If not using procedural generation to create the landscapes, then normally a 3D artist would render and create the landscapes. These programs are often used in video games or movies. Basic elements of landscapes created by scenery generators include terrain, water, foliage, and clouds. The process for basic random generation uses a diamond square algorithm.

In video games, an open world is a virtual world in which the player can approach objectives freely, as opposed to a world with more linear and structured gameplay. Notable games in this category include The Legend of Zelda (1986), Grand Theft Auto III (2001) and Minecraft (2011).

<span class="mw-page-title-main">Procedural texture</span> Computer graphics textures that are generated procedurally

In computer graphics, a procedural texture is a texture created using a mathematical description rather than directly stored data. The advantage of this approach is low storage cost, unlimited texture resolution and easy texture mapping. These kinds of textures are often used to model surface or volumetric representations of natural elements such as wood, marble, granite, metal, stone, and others.

<i>The Binding of Isaac</i> (video game) 2011 video game

The Binding of Isaac is a roguelike video game designed by independent developers Edmund McMillen and Florian Himsl. It was released in 2011 for Microsoft Windows, then ported to OS X, and Linux. The game's title and plot are inspired by the Biblical story of the Binding of Isaac. In the game, Isaac's mother receives a message from God demanding the life of her son as proof of her faith, and Isaac, fearing for his life, flees into the monster-filled basement of their home where he must fight to survive. Players control Isaac or one of the 6 other unlockable characters through a procedurally generated dungeon in a roguelike manner, fashioned after those of The Legend of Zelda, defeating monsters in real-time combat while collecting items and power-ups to defeat bosses and eventually Isaac's mother.

SpaceEngine is an interactive 3D planetarium and astronomy software developed by Russian astronomer and programmer Vladimir Romanyuk. It creates a 1:1 scale three-dimensional planetarium representing the entire observable universe from a combination of real astronomical data and scientifically accurate procedural generation algorithms. Users can travel through space in any direction or speed, and forwards or backwards in time. SpaceEngine is in beta status and up to version 0.9.8.0E, released in August 2017, it was available as a freeware download for Microsoft Windows. Version 0.990 beta was the first paid edition, released in June 2019 on Steam. The program has full support for VR headsets.

<i>Dragon Fin Soup</i> 2015 video game

Dragon Fin Soup is a role-playing video game created by the independent development studio Grimm Bros. It is the studio's first title and was released on Microsoft Windows, PlayStation 4, PlayStation 3, and PlayStation Vita. It is influenced by roguelike games and uses procedural generation. The game has two modes: Story mode follows a story and is more like a typical role-playing game, while Survival mode skips the story and focuses on the surviving within the game and constrains players with permadeath—once the player character dies, the game must be restarted from the beginning.

No Man's Sky is a 2016 video game developed by the British development studio, Hello Games. No Man's Sky allows the player to partake in four principal activities—exploration, survival, combat, and trading—in a shared, deterministic, procedurally generated open universe, which contains over 18 quintillion planets each with their own unique environment and flora and fauna.

A roguelike deck-building game is a hybrid genre of video games that combines the nature of deck-building card games with procedural-generated randomness from roguelike games.

<i>Caves of Qud</i> 2015 roguelike role-playing video game

Caves of Qud is an early access roguelike role-playing video game developed by American studio Freehold Games set in an open world that is partially pre-made and partially randomly generated. The game takes place in a post-apocalyptic science fantasy setting and is inspired by the pen-and-paper role-playing games Gamma World and Dungeons & Dragons.

<i>Mistover</i> 2019 video game

Mistover is a 2019 roguelike dungeon crawler role-playing video game developed and published by Krafton for Microsoft Windows, Nintendo Switch, and PlayStation 4. Mistover is set in a ravaged world recovering from a mass invasion of monstrous creatures from another realm, and its storyline follows the journey of a party of adventuring heroes who are on a quest to discover the source of the invasion. Players navigate environments from an isometric perspective with a party of procedurally generated player characters drawn from a roster of eight character classes to fight monsters and acquire loot recovered from the exploration of levels. A phenomenon known as "mist" is prevalent throughout the game world and negatively influences its characters, monsters, and items.

References

  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. Cook, Michael (August 10, 2016). "Alien Languages: How We Talk About Procedural Generation". Gamasutra . Retrieved October 7, 2019.
  4. Brown, Joseph Alexander; Scirea, Marco (2018). "Procedural Generation for Tabletop Games: User Driven Approaches with Restrictions on Computational Resources". SEDA 2018: Proceedings of 6th International Conference in Software Engineering for Defence Applications. International Conference in Software Engineering for Defence Applications. Rome, Italy. pp. 44–54.
  5. ""A Chat with Ken St Andre Part 1"". YouTube.com. Retrieved 6 November 2021.
  6. Smith, Gillian (2015). An Analog History of Procedural Content Generation (PDF). Foundations of Digital Games 2015. Pacific Grove, California. Retrieved October 7, 2019.
  7. Hatfield, Tom (2013-01-29). "Rise Of The Roguelikes: A Genre Evolves". GameSpy . Retrieved 2013-04-24.
  8. "Maze Craze". Atari Mania.
  9. Hiranand, Ravi (2015-06-18). "18 quintillion planets: The video game that imagines an entire galaxy | CNN Business". CNN. Retrieved 2022-12-13.
  10. Francis Spufford (October 18, 2003). "Masters of their universe". Guardian.
  11. Moss, Richard (January 1, 2016). "7 uses of procedural generation that all developers should study". Gamasutra . Retrieved January 1, 2016.
  12. Baker, Chris (9 August 2016). "'No Man's Sky': How Games Are Building Themselves". Rolling Stone . Retrieved 9 August 2016.
  13. Giesen, Fabian (April 8, 2012). "Metaprogramming for madmen". The ryg blog.
  14. Kuo, Ryan (April 19, 2012). "Why Borderlands 2 Has the Most Stylish Guns in Gaming". Wall Street Journal . Retrieved April 21, 2016.
  15. Khatchadourian, Raffi (18 May 2015). "World without end : creating a full-scale digital cosmos". Annals of Games. The New Yorker . Vol. 91, no. 13. pp. 48–57. Retrieved 5 August 2015.
  16. Wilson (16 July 2015). "How 4 Designers Built A Game With 18.4 Quintillion Unique Planets". Fast Company . Retrieved 9 August 2015.
  17. Sam White (2016-08-10). "No Man's Sky: How the biggest game ever made almost never happened". gamesradar. Retrieved 2022-05-07.
  18. "About Massive". Massive Software. Retrieved 12 June 2016.

Further reading