Procedural generation

Last updated

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.

Computing Activity that uses computers

Computing is any activity that uses computers to manage, process, and communicate information. It includes development of both hardware and software. Computing is a critical, integral component of modern industrial technology. Major computing disciplines include computer engineering, software engineering, computer science, information systems, and information technology.

Algorithm An unambiguous specification of how to solve a class of problems

In mathematics and computer science, an algorithm is a set of instructions, typically to solve a class of problems or perform a computation. Algorithms are unambiguous specifications for performing calculation, data processing, automated reasoning, and other tasks.

Computer graphics Graphics created using computers

Computer graphics are pictures and films created using computers. Usually, the term refers to computer-generated image data created with the help of specialized graphical hardware and software. It is a vast and recently developed area of computer science. The phrase was coined in 1960, by computer graphics researchers Verne Hudson and William Fetter of Boeing. It is often abbreviated as CG, though sometimes erroneously referred to as computer-generated imagery (CGI).

Contents

Overview

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. Dragon trees.jpg
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]

Fractal A self-similar pattern or set in mathematics

In mathematics, a fractal is a subset of a Euclidean space for which the Hausdorff dimension strictly exceeds the topological dimension. Fractals tend to appear nearly the same at different levels, as is illustrated here in the successively small magnifications of the Mandelbrot set; because of this, fractals are encountered ubiquitously in nature. Fractals exhibit similar patterns at increasingly small scales called self similarity, also known as expanding symmetry or unfolding symmetry; if this replication is exactly the same at every scale, as in the Menger sponge, it is called affine self-similar. Fractal geometry lies within the mathematical branch of topology.

Texture mapping method for defining high frequency detail, surface texture, or color information on a computer-generated graphic or 3D model

Texture mapping is a method for defining high frequency detail, surface texture, or color information on a computer-generated graphic or 3D model. Its application to 3D graphics was pioneered by Edwin Catmull in 1974.

Polygon mesh

A polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling. The faces usually consist of triangles, quadrilaterals (quads), or other simple convex polygons (n-gons), since this simplifies rendering, but may also be more generally composed of concave polygons, or even polygons with holes.

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.

<i>The Elder Scrolls II: Daggerfall</i> video game

The Elder Scrolls II: Daggerfall is an open-world action role-playing video game developed and published by Bethesda Softworks. The sequel to The Elder Scrolls: Arena and the second installment in the Elder Scrolls series, it was released on September 20, 1996 for MS-DOS. On July 9, 2009, the game was made available as a free, legal download on Bethesda's website to commemorate the fifteenth anniversary of The Elder Scrolls franchise.

British Isles Group of islands in northwest Europe

The British Isles are a group of islands in the North Atlantic off the north-western coast of continental Europe that consist of the islands of Great Britain, Ireland, the Isle of Man, the Hebrides and over six thousand smaller isles. They have a total area of about 315,159 km2 and a combined population of almost 72 million, and include two sovereign states, the Republic of Ireland, and the United Kingdom of Great Britain and Northern Ireland. The islands of Alderney, Jersey, Guernsey, and Sark, and their neighbouring smaller islands, are sometimes also taken to be part of the British Isles, even though, as islands off the coast of France, they do not form part of the archipelago.

<i>Soldier of Fortune</i> (video game) video game

Soldier of Fortune is a first-person shooter (FPS) video game created by Raven Software and published by Activision on February 29, 2000, for Microsoft Windows. It was later released for the PlayStation 2, as well as the Dreamcast, while Loki Software also made a port for Linux. It was digitally re-released on GOG.com on October 2, 2018, along with its two successors. The player takes on the role of a U.S. mercenary as he trots around the globe hoping to halt a terrorist nuclear weapons plot.

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

Demoscene Computer art subculture

The demoscene is an international computer art subculture focused on producing demos: self-contained, sometimes extremely small, computer programs that produce audio-visual presentations. The purpose of a demo is to show off programming, visual art, and musical skills. Demos and other demoscene productions are shared at festivals known as demoparties, voted on by those who attend, and released online.

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

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

Roguelike subgenre of role-playing video games

Roguelike is a subgenre of role-playing video game characterized by a dungeon crawl through procedurally generated levels, turn-based gameplay, tile-based graphics, 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>Beneath Apple Manor</i> early role-playing video game

Beneath Apple Manor is a roguelike game written by Don Worth for the Apple II and published by The Software Factory in 1978. Higher resolution "Special Editions" were released in 1982 and 1983, through Quality Software, for the Apple II and Atari 8-bit family. It was one of the first video games to use procedural generation.

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

Rogue is a dungeon crawling video game by Michael Toy and Glenn Wichman and later contributions by Ken Arnold. Rogue was originally developed around 1980 for Unix-based mainframe systems as a freely-distributed executable. It was later included in the official 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.

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

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

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

Related Research Articles

<i>Starflight</i> video game

Starflight is a space exploration, combat, and trading role-playing video game created by Binary Systems and published by Electronic Arts in 1986. Originally developed for IBM PC compatibles, it was later ported to the Amiga, Atari ST, Macintosh, and Commodore 64. A fully revamped version of the game was released for the Sega Genesis in 1991.

Perlin noise

Perlin noise is a type of gradient noise developed by Ken Perlin in 1983 as a result of his frustration with the "machine-like" look of computer graphics at the time. He formally described his findings in a SIGGRAPH paper in 1985 called An image Synthesizer. In 1997, Perlin was awarded an Academy Award for Technical Achievement for creating the algorithm:

To Ken Perlin for the development of Perlin Noise, a technique used to produce natural appearing textures on computer generated surfaces for motion picture visual effects.

The development of Perlin Noise has allowed computer graphics artists to better represent the complexity of natural phenomena in visual effects for the motion picture industry.

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.

A 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, as there are innumerable possibilities for how they generate.

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

Infinity is a postponed massively multiplayer online space simulation video game originally intended to be the first game built on the I-Novae engine by I-Novae Studios. While the I-Novae engine has been in development since 2004, development of Infinity never started.

Scenery generator software which could be used to generate landscape

A scenery generator refers to 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 explore and approach objectives freely, as opposed to a world with more linear and structured gameplay. While games have used open-world designs since the 1980s, the implementation in Grand Theft Auto III (2001) set a standard that has been used since.

Value noise

Value noise is a type of noise commonly used as a procedural texture primitive in computer graphics. It is conceptually different from, and often confused with gradient noise, examples of which are Perlin noise and Simplex noise. This method consists of the creation of a lattice of points which are assigned random values. The noise function then returns the interpolated number based on the values of the surrounding lattice points.

Survival games are a subgenre of action video games set in a hostile, intense, open-world environment, where players generally begin with minimal equipment and are required to collect resources, craft tools, weapons, and shelter, and survive as long as possible. Many survival games are based on randomly or procedurally generated persistent environments; more-recently created games are often playable online, allowing multiple players to interact in a single persistent world. Survival games are generally open-ended with no set goals and are often closely related to the survival horror genre, in which the player must survive within a supernatural setting, such as a zombie apocalypse.

Worley noise

Worley noise is a noise function introduced by Steven Worley in 1996. In computer graphics it is used to create procedural textures, that is textures that are created automatically in arbitrary precision and do not have to be drawn by hand. Worley noise comes close to simulating textures of stone, water, or cell noise.

Procedural texture

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>No Mans Sky</i> 2016 action-adventure survival video game

No Man's Sky is an action-adventure survival game developed and published by the indie studio Hello Games. It was released worldwide for the PlayStation 4 and Microsoft Windows in August 2016, and for Xbox One in July 2018. The game is built around four pillars: exploration, survival, combat, and trading. Players are free to perform within the entirety of a procedurally generated deterministic open world universe, which includes over 18 quintillion planets. Through the game's procedural generation system, planets have their own ecosystems with unique forms of flora and fauna, and various sentient alien species may engage the player in combat or trade within planetary systems. Players advance in the game by mining for resources to power and improve their equipment, buying and selling resources using credits earned by documenting flora and fauna, and otherwise seeking out the mystery around the Atlas, an entity at the center of the galaxy.

SpaceEngine is a proprietary 3D astronomy program and game engine developed by Russian astronomer and programmer Vladimir Romanyuk. It creates a three-dimensional planetarium representing the entire 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 is currently freeware for Microsoft Windows. SpaceEngine's latest release, version 0.990, is the first paid release. This has recently been made available for purchase via Steam Early Access.

<i>Dragon Fin Soup</i> action role-playing video game

Dragon Fin Soup is an action 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 for parts of the game. 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.

Map seed

In video games using procedural world generation, the map seed is a (relatively) short number or text string which is used to procedurally create the game world ("map"). This means that while the seed-unique generated map may be many megabytes big, it is possible to reset to the unmodified map, or the unmodified map can be exchanged between players, just by specifying the map seed. An example of a map seed in Minecraft is "-2242547518357798464". Map seeds are a type of random seeds.

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.

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.Cite web requires |website= (help)
  3. Hatfield, Tom (2013-01-29). "Rise Of The Roguelikes: A Genre Evolves". GameSpy . Retrieved 2013-04-24.Cite web requires |website= (help)
  4. "Maze Craze". Atari Mania.
  5. Francis Spufford (October 18, 2003). "Masters of their universe". Guardian.Cite news requires |newspaper= (help)
  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.Cite web requires |website= (help)
  13. "About Massive". Massive Software. Retrieved 12 June 2016.Cite web requires |website= (help)

Further reading