Terrain Generation I --- Noise

Introduction

In this series of posts, I'll describe my methods and experience writing a terrain generator for Minecraft using the craftbukkit world generator API -- (the generator itself will be written agnostic of any specific framework or library - so a port to Forge or even to a similar type of game may be possible)

This is the first time I've written anything remotely like this, so, if you'd like, please give feedback on what you liked or didn't, and any thoughts on how you think the post could be better.

edit: 300th post!

Terrain Generation I --- Noise

If you visit any online resource about terrain or world generation, chances are good that it will mention Perlin noise and associated "Coherent Randomness" algorithms. Perlin noise is in fact used in a critical role in MInecraft's native generator, as Notch describes in Terrain Generation, Part 1 (of 1). This project will be no different.

Perlin noise generation is a technique first engineered to reduce the memory requirements of textures in early computer graphics. This - and similar coherent randomness algorithms -- are useful because they allow us to specify things such as the period (the scale of the noise, in the context of a terrain generator, will allow the generated noise form the basis of things of all scales, from tiny hills to entire continents) and the amplitude (the "height" of the noise). By composing multiple noise generators, it will be possible to generate a world.

Because I want this generator to work similarly to Minecraft's world generator, there are a couple of unique requirements:

"Infinite" generation: The noise generator should able to generate noise without any built in limits, terrain should not repeat. Technical limits are OK (the same type of limit at the root of Minecraft's fabled "8 times the surface of the earth" claim)
Realtime arbitrary generation order: Minecraft terrain is generated on the fly, as the player explores the world, this means that terrain chunks can be generated at any order, at any time, across different play sessions, Minecraft versions, Java versions, generator versions, or even devices.

Makin' some noise

For this project I've implemented a type of closely related algorithm known as value noise (slightly simpler than Perlin noise - in both implementation and efficiency - but sufficient for the purposes of this project)

As decribed on the wiki, value noise works by generating a grid or lattice of randomized value points, then interpolating between the values in order to create a smooth, randomized surface.

Grid points. As you can see, each grid point generates a value and the surface is interpolated between those values

The interpolation is relatively simple, the real trick here is the grid point value generation.

To Infinity...

Perlin noise, in it's original form is slightly unsuited to this task, due to the fact that the values used at the grid points are precomputed. A grid of points are generated, if the noise is sampled outside of the grid, the pattern is simply repeated; this has the advantage of being fast - requiring only an array lookup instead of a random number generation - but has the disadvantage of creating a repeating pattern.

In light of the requirements above, grid values will need to be effectively infinite in number, generated on the fly, have no visible patterns or repeats, and be reproducible across program runs. In short we need a function of the format:

 noise(seed, grid x, grid y, grid z)  ->  value

the seed will be an integer value that will be stored across program runs.

After some experimentation, my solution is as follows.


noise(seed, x, y, z)
 a <- cantor(y, z)
 b <- cantor(x, a)
 c <- cantor(seed, b)
 result <- randomize(c)

randomize(k)

is this 64 bit linear congruential pseudo-random number generator - this algorithm takes an input and multiplies it by a huge number, "shooting" it past the 64 bit overflow value (the largest possible 64 bit value) causing it to "overflow", resulting in a number that (by casual inspection) is unrelated to the original value.This is not the best RNG function, nor is this the intended use case for it, but it is fast and seems to produce good results (visually).

cantor(k1, k2)

is the cantor pairing function. As mentioned in the wikipedia article, this function takes two positive integers and combines them into a single positive integer, with each pair of numbers resulting in a unique result.

The algorithm combines all of the grid coordinates together (with some spicyness from the seed value) into a unique integer using repeated application of the cantor pairing function, that value is then "randomized" using the linear congruential generator to obtain the final randomized value.

My first images using this method looked like this:

Uh-oh, symmetry. I had forgotten that the cantor pairing function was designed for positive integers only. Adding a function to "interleave" the inputs into positive integers fixed the problem.

for the record: the cantor pairing function:


interleave(k)  ->  -2 * k      k < 0
                -> 2 * k + 1     k >= 0

cantor(k1, k2)
 k1' <- interleave(k1)
 k2' <- interleave(k2)
 result <- ((k1' + k2') * (k1' + k2' + 1)) / 2 + k2'

The final result? A seeded, infinite, (as far as I can tell) unrepeating noise generator (with basically zero memory imprint)

A bit square looking, mostly because of the way that I am interpolating between the values. I think it compliments Minecraft's blocky aesthetic.

I love it LOUD!

What can be created using noise generators? I won't talk about the main terrain generation yet (mostly because I am still experimenting), however I will describe the "secret sauce" that makes all this worth while.

The secret ingredient? Fractals.

Not quite

source

In my experience, discussion of fractals in relation to terrain generation tends to be slightly mystical: "How do you make realistic looking terrain?" "fractals". The reality is quite simple: real landscapes have varying levels of detail, this detail tends to be self-similar (Hills look like down-scaled mountains, lumpy coastlines resolve into smaller bumps as you zoom in). Self-similarity is the defining feature of a fractal.

In practice this generally means we use an approximation of Fractal brownian motion. A fractal brownian surface has the prominance (amplitude, or strength) of features be inversely proportional to the frequency (or size) of said features - if a feature is twice the frequency (half as large) it will have half the strength, at 3 times the frequency (1 third scale) it will have 1/3 strength, and so on). The general trend that emerges is that the surface as a whole is dominated by the largest features (in the context of a terrain generator, continents) which are in turn "perturbed" by smaller scale features like coastline bumps, inlets, islands, lakes and other interesting features.

First, assemble a couple of generators, double the frequency for each successive generator

Halve the amplitude of each successive generator.

sum them all together and you get this, pretty cool, right? It really masks the "square" appearance of the noise.

Just for fun, add a simple gradient and a "sea level".

Not all that impressive. We're not done yet, of course.

Next Time

Infinite seeded Voronoi cells using the same techniques as used to make the value noise generator. Also: the basic high-level bones of the generator: continents! mountain ranges! climate! I'll explain how my generator will be different from Minecraft's native terrain generator.

I'm also planning on putting the WIP project up on my Github, I'll have a link on a later post.

If you have any questions, ask and I'll answer as well as I can.

Thanks for reading!

Terrain Generation I --- Noise

Completed

Ongoing

Upcoming