Procedural generation

Procedural generation is a widely used term in the production of media; it refers to content generated algorithmically rather than manually. Often, this means creating content on the fly rather than prior to distribution. This is often related to computer graphics applications and video game level design.

Overview

The term procedural refers to the process that computes a particular function. Fractals, an example of procedural generation, dramatically express this concept, around which a whole body of mathematics—fractal geometry—has evolved. 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".

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. Avalanche Studios employed procedural generation to create a large and varied group of tropical islands in great detail for Just Cause.

The modern demoscene uses procedural generation to package a great deal of audiovisual content into relatively small programs. Farbrausch is a team famous for such achievements, although many similar techniques were already implemented by The Black Lotus in the 1990s.

Contemporary application

Video games

Template:Inappropriate tone The earliest 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. For example, 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. 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. 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.

Today, most games include thousands of times as much data in terms of memory as algorithmic mechanics. For example, all of the buildings in the large game worlds of the Grand Theft Auto games have been individually designed and placed by artists. In a typical modern video game, game content such as textures and character and environment models are created by artists beforehand, then rendered in the game engine. As the technical capabilities of computers and video game consoles increases, the amount of work required by artists also greatly increases. First, high-end gaming PCs and current-generation game consoles like the Xbox 360, PlayStation 3, and Wii U are capable of rendering scenes containing many very detailed objects with high-resolution textures in high-definition. This means that artists must invest a great deal more time in creating a single character, vehicle, building, or texture, since players will tend to expect ever-increasingly detailed environments.

Furthermore, the number of unique objects displayed in a video game is increasing. In addition to highly detailed models, players expect a variety of models that appear substantially different from one another. In older games, a single character or object model might have been used over and over again throughout a game. With the increased visual fidelity of modern games, however, it is very jarring (and threatens the suspension of disbelief) to see many copies of a single object, while the real world contains far more variety. Again, artists would be required to complete exponentially more work in order to create many different varieties of a particular object. The need to hire larger art staffs is one of the reasons for the rapid increase in game development costs.

Some initial approaches to procedural synthesis attempted to solve these problems by shifting the burden of content generation from the artists to programmers who can create code which 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 richer experience. The same method would require far more processing power. Since CPUs are constantly increasing in speed, however, the latter 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 which can dramatically change their appearance and distribution.

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.

An indie game that makes extensive use of procedural generation is Minecraft. 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. This has the benefit that every time a new game is made, the world is completely different and will need a different method to be successful, adding replay value.

Other indie games that rely heavily on procedural generation are Dwarf Fortress, in which the whole world is generated, completely with its history, notable people, and monsters.

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.

Noise is extremely important to procedural workflow in film, the most prolific of which is Perlin noise. Noise refers to an algorithm that generates a patterned sequence of pseudorandom numbers.

Software examples

Middleware

• Acropora, a procedural 3D modeling software utilizing voxels to create organic objects and terrain.
• Art of Illusion, an open source and free 3D modeler, has an internal node-based procedural texture editor.
• CityEngine, a procedural 3D modeling software, specialized in city modeling.
• Filter Forge, an Adobe Photoshop plugin for designing procedural textures using node-based editing.
• Grome, aopular terrain and outdoor scenes modeler for games and simulation software.
• Houdini, a procedural 3D animation package. A free version of the software is available.
• Softimage, a 3D computer graphics application that allows node-based procedural creation and deformation of geometry.
• SpeedTree, a middleware product for procedurally generating trees.
• Terragen, a landscape generation software. Terragen 2 permits procedural generation of an entire world.
• World Machine, a powerful node-based procedurally generated terrain software with a plugin system to write new, complex nodes. Exports to Terragen, among other formats, for rendering, as well as having internal texture generation tools.

Space simulations with procedural worlds and universes

• Elite (1984) - Everything about the universe, planet positions, names, politics and general descriptions, is generated procedurally; Ian Bell has released the algorithms in C as Text Elite.
• Starflight (1986)cite needed
• Exile (1988) - Game levels were created in a pseudorandom fashion, as areas important to gameplay were generated.cite needed
• Frontier: Elite II (1993) - Much as the game Elite had a procedural universe, so did its sequel.
• Frontier: First Encounters (1995)
• Mankind (1998) - a MMORTS where everything about the galaxy, systems names, planets, maps and resources is generated procedurally from a simple tga image.
• Noctis (2002)cite needed
• Infinity: The Quest for Earth (In development, not yet released)
• Vega Strike - An open source game very similar to Elite.
• "SpaceEngine" - A free planetarium software. It simulates billions of galaxies each with billions of stars with their own planetary systems. Where humans have no information, content is generated.
• "Witchspace 2" - Space Trading simulation/game. Free form / sandbox play where the player is commander of a spacecraft with an all female crew. The goal of the game is to establish a permanent home. Available on iPad only.

Games with procedural levels

Arcade games

• The Sentinel (1986) - Used procedural generation to create 10,000 unique levels.
• Darwinia (2005) - Has procedural landscapes that allowed for greatly reduced game development time.cite needed

Racing games

• Fuel (2009) - Generates an open world through procedural techniques
• Gran Turismo 5 (2010) - Features randomly generated rally stages
• GRID 2 (2013) - Features a system dubbed "LiveRoutes" that dynamically changes the track by changing the corner layout on a given circuit lap-by-lap.

Role-playing games

• Captive (1990) - Generates (theoretically up to 65,535) game levels procedurally
• Virtual Hydlide (1995)
• Shin Megami Tensei: Persona 3 (2006) - Features procedurally generated dungeons.
• The Elder Scrolls II: Daggerfall (1996)
• Diablo (1998) and Diablo II (2000) - Both use procedural generation for level design. cite needed
• Torchlight - A Diablo clone differing mostly by art style and feel.
• Dwarf Fortress - Procedurally generates a large game world, including civilization structures, a large world history, interactive geography including erosion and magma flows, ecosystems which react with each other and the game world. The process of initially generating the world can take up to half an hour even on a modern PC, and is then stored in text files reaching over 100MB to be reloaded whenever the game is played.
• Dark Cloud and Dark Cloud 2 - Both generate game levels procedurally.
• Hellgate: London (2007)
• The Disgaea series of games use procedural level generation for the "Item World".
• Realm of the Mad God
• Nearly all roguelikes use this technique.

Strategy games

• Majesty:The Fantasy Kingdom Sim (2000) - Uses procedural generation for all levels and scenarios.
• Seven Kingdoms (1997) - Uses procedural generation for levels.cite needed
• Xconq, an open source strategy game and game engine.
• Frozen Synapse - Levels in single player are mostly randomly generated, with bits and pieces that are constant in every generation. Multiplayer maps are randomly generated. Skirmish maps are randomly generated, and allow the player to change the algorithm used.
• Atom Zombie Smasher - Levels are generated randomly.
• Freeciv - Uses procedural generation for levels.

Third-person shooters

• Just Cause (2006) - Game area is over Template:Convert, created procedurally cite needed
• Inside a Star-Filled Sky - All levels are procedurally generated and unlimited in visual detail.

Unknown genres

• Subversion (TBA) - Uses procedural generation to create cities on a given terrain.
• Minecraft - The game world is procedurally generated as the player explores it, with the full size possible stretching out to be nearly eight times the surface area of the Earth before running into technical limits.

Almost entirely procedural games

• Noctis (2000)
• .kkrieger (2004)
• Synth (video game) (2009) - 100% procedural graphics and levels

Games with miscellaneous procedural effects

• ToeJam & Earl (1991) - The random levels were procedurally generated.
• The Elder Scrolls III: Morrowind (2002) - Water effects are generated on the fly with procedural animation by the technique demonstrated in NVIDIA's "Water Interaction" demo.
• RoboBlitz (2006) for XBox360 live arcade and PC
• Spore (2008)
• Left 4 Dead (2008) - Certain events, item locations, and number of enemies are procedurally generated according to player statistics.
• Left 4 Dead 2 (2009) - Certain areas of maps are randomly generated and weather effects are dynamically altered based on current situation.
• Borderlands (2009) - The weapons, items and some levels are procedurally generated based on individual players' current level.
• Star Trek Online (2010) - Star Trek Online procedurally generates new races, new objects, star systems and planets for exploration. The player can save the coordinates of a system they find, so that they can return or let other players find the system.
• Terraria (2011) - Terraria procedurally generates a 2D landscape for the player to explore.
• A common use of procedural generation in video games is to make a few basic character models, than run them through procedural generation software to make diverse character models, thus enabling every character to have his, her, or its own model without the development team having to expend too much resources. An example of a game that does this is the Half-Life 1 total conversion modification Black Mesa, which has a built-in "Face Creation System" exclusively for that purpose.

See also

Template:Organize section

• Emergent gameplay
• Artificial Creativity
• Procedural modeling
• Procedural texture
• Procedural animation
• Scenery generator
• Cellular automata
• Demoscene
• Display hack
• Digital morphogenesis
• Perlin noise
• Random dungeon
• Generative Modelling Language
• Generative art
• Synth video game
• Shape grammar
• Fractal landscape
• Diamond-square algorithm
• L-System
• Iterated function system

External links

• The Future Of Content - Will Wright keynote on Spore & procedural generation at the Game Developers Conference 2005. (registration required to view video).
• Procedural Graphics - an introduction by in4k
• Texturing & Modeling: A Procedural Approach
• 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