Paul's picture

I have gotten a few requests about this:  How do seeds work?  What kind of sourcery is behind generating a humongous world from just 1 word. Well tighten your math belt for this ride can be rough.

There are essentially 2 ways to do procedural terrain generation:  

* Generate a blank canvas and add features to it like mountains and trees and houses and stuff.  This would allow you to have perfect structures,  but it is very complicated when a feature is generated right between chunks, especially chunks that are not loaded yet.

* Generate each voxel separately based on a math function without knowing it is part of something bigger.  The key here is that the math function needs to be written in such way that it can generate voxels in a way that look like structures. This is the approach I took. The whole terrain generation is thus just 1 function:  f(seed,x,y,z)  that returns a block.  

I could write books on this subject, but let's start by giving a big picture of how it works, and on subsequent articles I could dig a little deeper on each part.

The easiest way to explain it that I can find is by showing the structure of a terrain generation in layers.  A layer uses the data provided by the lower layer in order to calculate what it returns. The very basic structure is this:

Terrain Generation
Simplex noise
Pseudo-random number generator
Seed

The seed

At the lowest level,  we have the seed.  The seed is what the user enters,  it can be any random string.

Pseudo random number generator

The pseudo random number generator (PRNG) is a function that receives the seed and a coordinate and returns a number. It should have the following properties:

* Given the same seed and coordinates it always returns the same number,  so it is not true random.

* Given 2 different seeds (even if just 1 bit),  it should generate completely diferent results

* It should behave in such way that 2 coordinates don't seem to have any correlation, for example [PRNG(seed,x,y,z), PRNG(seed,x,y,z+1), PRNG(seed,x,y,z+2), PRNG(seed,x,y,z + 3), ...]  should look like a completely random sequence of numbers.

Simplex noise

The simplex noise, is a masterpiece algorithm from Ken Perlin.  The idea of the simplex noise is to create a function that is continuous and derivable over any number of dimensions, with the result between 0 and 1.  To get an idea,  this is what simplex noise generates on a 2 dimension plane:

I changed the reference implementation for simplex noise to use my PRNG function.  So the result is that 2 different seeds would produce a different simplex noise.

Continuous means that if you move slightly on any axis,  the value changes only slightly. A non continuous function would have jumps, and lines that cut across.

Derivable means that it does not have sharp edges,  but it is always smooth at any point.

Terrain Generation

Look at the simplex noise picture above.  Imagine that white is high and black is low.  Now you are picturing mountains and valleys.  

But if that was all I did,  you would never get caves, and the mountains would be all the same size and very regular. It would look very bad,  kind of like this:

 

And you would spit in my face if that was the terrain that block story generated.

A particularly useful technique for generating realistic terrain is called fbm (fractal brownian motion).  It evaluates noise functions several times at different frequencies and amplitudes, to generate mountains with features.  A 2d fbm looks like this:

 

Note it is much more rich than a plain simplex node.  And you can see big mountains with hills in them.

Here is an fbm generated terrain:

 

 

Now,  before I dig deeper into any one of these layers,  let's hear it:  what would you like to know more about?

Great explanation

The layers of generation, the way you presented, remind me of the layers of a TCP/IP stack, and how each one builds and expands on the level before it - the reverse-pyramid design. I would love to see behind the curtain on cave/tunnel system generation.

 

I would like to hear more.

I would like to hear more.

wow yeah

Thats great. Thanks

Dont fool with a jedi master son. he he