Procedural Generation

Procedural Generation is content generation algorithmically, often on the fly.  In order to separate this from solely a random number generator, my research has led me to add three additional qualifiers that are often present.  The first is Rules, which are bounds that contain and shape the randomness.  For example, a rule might be that all procedurally generated rooms must have at least one door.  Next is Guidlines, which most often take the form of weighted actions or components.  For example, filling a section of a room with furniture might be more common than filling it with supplies.  Finally, there are Goals, which are what the procedural generation is designed to do.  For example, generate a room.

Procedural Generation is used in a massive variety of ways, two of which are maze and terrain generation.  There are a number of terrain generation algorithms, a smattering of which can be found here, which can be used not only to generate mazes of multiple dimensions(2D, 3D, hyper and above) but solve them as well.  Further, each algorithm uniquely creates mazes.  For example, some algorithms generate perfect mazes, which have no inaccessible areas, while others focus on specific types of corridors or directions.

Terrain generation can also be done in a number of ways, two of which are the Mid Point Displacement algorithm–also known as the Diamond-Square or Plasma algorithm) and Particle Deposition algorithm.  The first works recursively, finding the center of the terrain, dividing it into four squares via points from the center, finding the centers of those squares, which are then further divided.  The height of each point is then influenced by a random number, which decreases each time the function is called.  The process repeats until there are no points remaining to be influenced.  The Particle Deposition algorithm works by selecting a random point, changing its height, and then moves to a random neighbor to repeat the process for however many iterations.  The process can be further altered by using the ‘Roll’ method, which checks to see if a random neighbor of the current point has a lower height value than the current point, and if so, influences the neighbor, rather than the current point.  The Roll method often causes points that have been influenced to be more uniform to one another.

A final, and complex, means of procedural generation is Perlin Noise.  Developed by Ken Perlin while working on the original Tron movie, Perlin Noise is a pseudorandom generator that can scale into multiple dimensions and be used in a variety of ways, such as terrain or texture generation.  It is important to note that Ken Perlin more recently developed Simplex Noise, which is nearly identical to Perlin Noise, but much more efficient when scaling into higher dimensions–O(n2) vs. Perlin Noise’s O(2n).  Perlin and Simplex Noise are pseudorandom because once seeded, a given point will always return the same random number, even if used multiple times in the random number generator.  In the first dimension, Perlin and Simplex Noise can generate random points that appear very similar to audio waves.  In the second dimension, the noise appears similar to TV static, though application of Fractional Brownian Motion will smooth  the result into appearing like a cloud or gas.  The third and fourth dimensions often see the inclusion of the z-axis and time, which higher dimensions adding additional properties as needed.  Effectively, the algorithms work by altering a given point by gradient vectors, dependent on the number of dimensions.  More detailed information can be found in the sources below.

Maze Information:

Maze algorithm examples: http://www.jamisbuck.org/mazes/

Types of mazes and algorithms: http://www.astrolog.org/labyrnth/algrithm.htm

Terrain Information:

Example of Diamond-Square algorithm: http://paulboxley.com/blog/2011/03/terrain-generation-mark-one

Fractal Terrain and height maps: http://www.gameprogrammer.com/fractal.html

Spherical Landscape generation: http://freespace.virgin.net/hugo.elias/models/m_landsp.htm

Mid Point, Particle Deposition, and Smoothing algorithms: http://www.lighthouse3d.com/opengl/terrain/index.php3?introduction

Perlin and Simple Noise Information:

Using Perlin Noise in Games: http://devmag.org.za/2009/04/25/perlin-noise/

Intro to Perlin Noise: http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

Math and desription of Perlin Noise: http://staffwww.itn.liu.se/~stegu/simplexnoise/simplexnoise.pdf

An example of animating Perlin Noise: http://www.sjeiti.com/perlin-noise-versus-simplex-noise-in-javascript-final-comparison/

The math of Perlin Noise: http://webstaff.itn.liu.se/~stegu/TNM022-2005/perlinnoiselinks/perlin-noise-math-faq.html

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s