How to use Perlin noise in terrain generation

Started by
12 comments, last by Mekuri 11 years, 7 months ago
So basically I am trying to make some 2d side scrolling terrain, (like Terraria). So far I've managed nicely with some simple terrain, but I'm taking the next step. Online I found some code, using the Simplex Noise. I figured I'd try it out and try to implement it to get a good idea on how it works.
The results I get are.. useless.. Just random blocks here and there.. Now the way I see it I've totally misunderstood how to implement this for terrain generation (works fine for picture generation).
First, here's the code for the Noise class, it's a bit lengthy, but I thought I should include all of it:


/// <summary>
/// Implementation of the Perlin simplex noise, an improved Perlin noise algorithm.
/// Based loosely on SimplexNoise1234 by Stefan Gustavson <http://staffwww.itn.liu.se/~stegu/aqsis/aqsis-newnoise/>
///
/// </summary>
public class Noise
{
/// <summary>
/// 1D simplex noise
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
public static float Generate(float x)
{
int i0 = FastFloor(x);
int i1 = i0 + 1;
float x0 = x - i0;
float x1 = x0 - 1.0f;
float n0, n1;
float t0 = 1.0f - x0 * x0;
t0 *= t0;
n0 = t0 * t0 * grad(perm[i0 & 0xff], x0);
float t1 = 1.0f - x1 * x1;
t1 *= t1;
n1 = t1 * t1 * grad(perm[i1 & 0xff], x1);
// The maximum value of this noise is 8*(3/4)^4 = 2.53125
// A factor of 0.395 scales to fit exactly within [-1,1]
return 0.395f * (n0 + n1);
}
/// <summary>
/// 2D simplex noise
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
public static float Generate(float x, float y)
{
const float F2 = 0.366025403f; // F2 = 0.5*(sqrt(3.0)-1.0)
const float G2 = 0.211324865f; // G2 = (3.0-Math.sqrt(3.0))/6.0
float n0, n1, n2; // Noise contributions from the three corners
// Skew the input space to determine which simplex cell we're in
float s = (x + y) * F2; // Hairy factor for 2D
float xs = x + s;
float ys = y + s;
int i = FastFloor(xs);
int j = FastFloor(ys);
float t = (float)(i + j) * G2;
float X0 = i - t; // Unskew the cell origin back to (x,y) space
float Y0 = j - t;
float x0 = x - X0; // The x,y distances from the cell origin
float y0 = y - Y0;
// For the 2D case, the simplex shape is an equilateral triangle.
// Determine which simplex we are in.
int i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords
if (x0 > y0) { i1 = 1; j1 = 0; } // lower triangle, XY order: (0,0)->(1,0)->(1,1)
else { i1 = 0; j1 = 1; } // upper triangle, YX order: (0,0)->(0,1)->(1,1)
// A step of (1,0) in (i,j) means a step of (1-c,-c) in (x,y), and
// a step of (0,1) in (i,j) means a step of (-c,1-c) in (x,y), where
// c = (3-sqrt(3))/6
float x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed coords
float y1 = y0 - j1 + G2;
float x2 = x0 - 1.0f + 2.0f * G2; // Offsets for last corner in (x,y) unskewed coords
float y2 = y0 - 1.0f + 2.0f * G2;
// Wrap the integer indices at 256, to avoid indexing perm[] out of bounds
int ii = i % 256;
int jj = j % 256;
// Calculate the contribution from the three corners
float t0 = 0.5f - x0 * x0 - y0 * y0;
if (t0 < 0.0f) n0 = 0.0f;
else
{
t0 *= t0;
n0 = t0 * t0 * grad(perm[ii + perm[jj]], x0, y0);
}
float t1 = 0.5f - x1 * x1 - y1 * y1;
if (t1 < 0.0f) n1 = 0.0f;
else
{
t1 *= t1;
n1 = t1 * t1 * grad(perm[ii + i1 + perm[jj + j1]], x1, y1);
}
float t2 = 0.5f - x2 * x2 - y2 * y2;
if (t2 < 0.0f) n2 = 0.0f;
else
{
t2 *= t2;
n2 = t2 * t2 * grad(perm[ii + 1 + perm[jj + 1]], x2, y2);
}
// Add contributions from each corner to get the final noise value.
// The result is scaled to return values in the interval [-1,1].
return 40.0f * (n0 + n1 + n2); // TODO: The scale factor is preliminary!
}

public static float Generate(float x, float y, float z)
{
// Simple skewing factors for the 3D case
const float F3 = 0.333333333f;
const float G3 = 0.166666667f;
float n0, n1, n2, n3; // Noise contributions from the four corners
// Skew the input space to determine which simplex cell we're in
float s = (x + y + z) * F3; // Very nice and simple skew factor for 3D
float xs = x + s;
float ys = y + s;
float zs = z + s;
int i = FastFloor(xs);
int j = FastFloor(ys);[attachment=11149:perlinBug.png]
int k = FastFloor(zs);
float t = (float)(i + j + k) * G3;
float X0 = i - t; // Unskew the cell origin back to (x,y,z) space
float Y0 = j - t;
float Z0 = k - t;
float x0 = x - X0; // The x,y,z distances from the cell origin
float y0 = y - Y0;
float z0 = z - Z0;
// For the 3D case, the simplex shape is a slightly irregular tetrahedron.
// Determine which simplex we are in.
int i1, j1, k1; // Offsets for second corner of simplex in (i,j,k) coords
int i2, j2, k2; // Offsets for third corner of simplex in (i,j,k) coords
/* This code would benefit from a backport from the GLSL version! */
if (x0 >= y0)
{
if (y0 >= z0)
{ i1 = 1; j1 = 0; k1 = 0; i2 = 1; j2 = 1; k2 = 0; } // X Y Z order
else if (x0 >= z0) { i1 = 1; j1 = 0; k1 = 0; i2 = 1; j2 = 0; k2 = 1; } // X Z Y order
else { i1 = 0; j1 = 0; k1 = 1; i2 = 1; j2 = 0; k2 = 1; } // Z X Y order
}
else
{ // x0<y0
if (y0 < z0) { i1 = 0; j1 = 0; k1 = 1; i2 = 0; j2 = 1; k2 = 1; } // Z Y X order
else if (x0 < z0) { i1 = 0; j1 = 1; k1 = 0; i2 = 0; j2 = 1; k2 = 1; } // Y Z X order
else { i1 = 0; j1 = 1; k1 = 0; i2 = 1; j2 = 1; k2 = 0; } // Y X Z order
}
// A step of (1,0,0) in (i,j,k) means a step of (1-c,-c,-c) in (x,y,z),
// a step of (0,1,0) in (i,j,k) means a step of (-c,1-c,-c) in (x,y,z), and
// a step of (0,0,1) in (i,j,k) means a step of (-c,-c,1-c) in (x,y,z), where
// c = 1/6.
float x1 = x0 - i1 + G3; // Offsets for second corner in (x,y,z) coords
float y1 = y0 - j1 + G3;
float z1 = z0 - k1 + G3;
float x2 = x0 - i2 + 2.0f * G3; // Offsets for third corner in (x,y,z) coords
float y2 = y0 - j2 + 2.0f * G3;
float z2 = z0 - k2 + 2.0f * G3;
float x3 = x0 - 1.0f + 3.0f * G3; // Offsets for last corner in (x,y,z) coords
float y3 = y0 - 1.0f + 3.0f * G3;
float z3 = z0 - 1.0f + 3.0f * G3;
// Wrap the integer indices at 256, to avoid indexing perm[] out of bounds
int ii = i % 256;
int jj = j % 256;
int kk = k % 256;
// Calculate the contribution from the four corners
float t0 = 0.6f - x0 * x0 - y0 * y0 - z0 * z0;
if (t0 < 0.0f) n0 = 0.0f;
else
{
t0 *= t0;
n0 = t0 * t0 * grad(perm[ii + perm[jj + perm[kk]]], x0, y0, z0);
}
float t1 = 0.6f - x1 * x1 - y1 * y1 - z1 * z1;
if (t1 < 0.0f) n1 = 0.0f;
else
{
t1 *= t1;
n1 = t1 * t1 * grad(perm[ii + i1 + perm[jj + j1 + perm[kk + k1]]], x1, y1, z1);
}
float t2 = 0.6f - x2 * x2 - y2 * y2 - z2 * z2;
if (t2 < 0.0f) n2 = 0.0f;
else
{
t2 *= t2;
n2 = t2 * t2 * grad(perm[ii + i2 + perm[jj + j2 + perm[kk + k2]]], x2, y2, z2);
}
float t3 = 0.6f - x3 * x3 - y3 * y3 - z3 * z3;
if (t3 < 0.0f) n3 = 0.0f;
else
{
t3 *= t3;
n3 = t3 * t3 * grad(perm[ii + 1 + perm[jj + 1 + perm[kk + 1]]], x3, y3, z3);
}
// Add contributions from each corner to get the final noise value.
// The result is scaled to stay just inside [-1,1]
return 32.0f * (n0 + n1 + n2 + n3); // TODO: The scale factor is preliminary!
}
private static byte[] perm = new byte[512] { 151,160,137,91,90,15,
131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180,
151,160,137,91,90,15,
131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
};
private static int FastFloor(float x)
{
return (x > 0) ? ((int)x) : (((int)x) - 1);
}
private static float grad(int hash, float x)
{
int h = hash & 15;
float grad = 1.0f + (h & 7); // Gradient value 1.0, 2.0, ..., 8.0
if ((h & 8) != 0) grad = -grad; // Set a random sign for the gradient
return (grad * x); // Multiply the gradient with the distance
}
private static float grad(int hash, float x, float y)
{
int h = hash & 7; // Convert low 3 bits of hash code
float u = h < 4 ? x : y; // into 8 simple gradient directions,
float v = h < 4 ? y : x; // and compute the dot product with (x,y).
return ((h & 1) != 0 ? -u : u) + ((h & 2) != 0 ? -2.0f * v : 2.0f * v);
}
private static float grad(int hash, float x, float y, float z)
{
int h = hash & 15; // Convert low 4 bits of hash code into 12 simple
float u = h < 8 ? x : y; // gradient directions, and compute dot product.
float v = h < 4 ? y : h == 12 || h == 14 ? x : z; // Fix repeats at h = 12 to 15
return ((h & 1) != 0 ? -u : u) + ((h & 2) != 0 ? -v : v);
}
private static float grad(int hash, float x, float y, float z, float t)
{
int h = hash & 31; // Convert low 5 bits of hash code into 32 simple
float u = h < 24 ? x : y; // gradient directions, and compute dot product.
float v = h < 16 ? y : z;
float w = h < 8 ? z : t;
return ((h & 1) != 0 ? -u : u) + ((h & 2) != 0 ? -v : v) + ((h & 4) != 0 ? -w : w);
}
}


The way I try to use it is the following:


private void CreatePerlinWorld()
{
world = new Tile[_maxWidth, _maxHeight];
diamond = new float[_maxWidth, _maxHeight];
for (int x = 0; x < world.GetLength(0) - 1; x++)
{
for (int y = 0; y < world.GetLength(1) - 1; y++)
{
diamond[x,y] = Noise.Generate(x, y);
}
}
}
private void GeneratePerlinWorld()
{
for (int x = 0; x < _maxWidth; x++)
{
for (int y = 0; y < _maxHeight; y++)
{
if (diamond[x, y] < 0f)
world[x, y] = new Tile(TileType.None, TileCollision.Passable, ToolType.None);
if (diamond[x, y] >= -0f)
world[x, y] = new Tile(TileType.Dirt, TileCollision.Impassable, ToolType.Pickaxe);
}
}
}


First I run CreatePerlinWorld() followed by GeneratePerlinWorld().
I've attached a screenshot with the results I get.

So my questions are: What am I doing wrong? And what do I have to do to get it right?

Thanks in advance smile.png

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri

Advertisement
What you are doing is a common mistake:


for (int x = 0; x < world.GetLength(0) - 1; x++)
{
for (int y = 0; y < world.GetLength(1) - 1; y++)
{
diamond[x,y] = Noise.Generate(x, y);
}
}


Perlin noise is generated by interpolating values that are generated at integer boundaries. If you sample the noise at integer coordinates, then, you won't get the smooth in-between values you are expecting; what you get instead is basically white noise, as you have discovered.

Something like this might get you better results:

float frequency=1.0f/(float)world.GetLength(0);
for (int x = 0; x < world.GetLength(0) - 1; x++)
{
for (int y = 0; y < world.GetLength(1) - 1; y++)
{
diamond[x,y] = Noise.Generate((float)x*frequency (float)y*frequency);
}
}


You do need to tweak the exact mapping by playing with the frequency value.

A good rule of thumb for choosing frequency is that a Perlin function has 1 feature per unit, where a feature is a hill or valley. So if you want 1 hill, use a frequency equal to your world size dimension. If you want more hills, use a larger value.

As far as using noise in a sane manner to generate terrain, you might check out this article.
While FLeBlanc has a point, I'd argue that a larger problem is the fact that you are only using a single octave of simplex noise. Simplex noise is little more than smoothed white noise - to get interesting results, you need to combine multiple layers of simplex noise into a 'fractal'.

The simplest fractal is probably 'fractal brownian motion':
[source]double noise_fractal_brownian_motion(int octaves, double x, double y, double z) {
const double lacunarity = 1.9;
const double gain = 0.65;

double sum = 0.0;
double amplitude = 1.0;

int i;
for (i = 0; i < octaves; i++) {
sum += amplitude * noise_simplex(x, y, z);

amplitude *= gain;

x *= lacunarity;
y *= lacunarity;
z *= lacunarity;
}

return sum;
}
[/source]
where 'octaves' controls the number of layers in your noise (tweaking 'lacunarity' and 'gain' as needed to modify the result).

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

I don't know that I'd say that was a larger problem. It doesn't matter how many layers of detail you stack on; unless you do your mapping correctly, all you're adding is ever smaller detail that still gets lost in the mapping. The first layer defines the over-all feature size, successive layers are detail. Fix the mapping first, then add more detail.
Thank you both for your quick responses. I will try playing around with the frequency and see what I get. Also, depending on the results I will try with more octaves.

Thanks- Really appreciated, both of you smile.png

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri

Agreed on the integer problem, it gets so many people. Also potentially agreed about octaves. But I wonder if there's an even more fundamental problem. From your screenshot it looks like you're using 2D Perlin noise. Often people use 2D Perlin noise to generate a heightfield for a 3D world. For a side-scrolling platformer I would expect you'd only want 1D Perlin noise, and then to use those values as the height of your hills. I would think that 2D Perlin noise is only applicable if you want to allow mining (like Minecraft/Infiniminer) or if you want to allow caves. Even then, raw 2D Perlin noise is generally not useful as it would create islands floating in space. Instead you'd use 1D Perlin noise to create the general contour of the land, and then subtract 2D Perlin noise from anything that appears under that curve to make caves.

Agreed on the integer problem, it gets so many people. Also potentially agreed about octaves. But I wonder if there's an even more fundamental problem. From your screenshot it looks like you're using 2D Perlin noise. Often people use 2D Perlin noise to generate a heightfield for a 3D world. For a side-scrolling platformer I would expect you'd only want 1D Perlin noise, and then to use those values as the height of your hills. I would think that 2D Perlin noise is only applicable if you want to allow mining (like Minecraft/Infiniminer) or if you want to allow caves. Even then, raw 2D Perlin noise is generally not useful as it would create islands floating in space. Instead you'd use 1D Perlin noise to create the general contour of the land, and then subtract 2D Perlin noise from anything that appears under that curve to make caves.


I've played around with the 2D algorithm for a while, and I think you might be right. I do get some decent terrain when I play around with the frequency, but my "groundlevel" is always flat.

I am getting a better understanding of this by playing around, so I think I'll try throwing myself into doing what you suggested. Thanks a lot :)

Check out the game I am making here - http://www.youtube.com/user/NasarethMekuri

1D noise is useful if you want to do just simple rolling terrain. 2D is useful if you want to do things like caves and overhangs. Again, I refer you to this article written by JTippetts. It's pretty interesting, and I think you can do some cool stuff with it. I hope he doesn't mind me linking to his images, but I think they really help to make the point. (JTippetts, if you don't want me linking to them, let me know and I'll remove them.) The premise of it is this: a function differentiates between ground and sky (anything below a certain level is ground, anything above is sky). Normally this threshold is a flat line at a certain level (Y=0, for example). A 1D noise function is used to push the ground level up or down by a certain amount.

Here is the basic ground/sky:

minecraft_gradient_select.jpg
The white part (which is hard to see, of course, on the white background here) is the ground.

The article talks about using a 1D function to perturb the ground, which would end up looking like this:

minecraft_ground_scaley.jpg

It also talks about using a 2D function to perturb it, which would look like this:

minecraft_gradient_fractal_perturb.jpg

The second one, imo, is "cooler" looking, but it does result in floating islands.

The article also talks about using a second function to impose caves upon the terrain:

minecraft_ground_final_3.jpg

It's really an interesting article, and while it is written sort of centric to his own library, the idea of it should be usable with any library.
A common solution is to use 2D simplex noise of a couple octaves to get some nice random landscape.

Then you use a 3D simplex noise, interpreted as density, to get holes in the landscape. This will make a much more dramatic view, where you can get over hang, etc. Using an inverted 3D density, you can get flying islands if you want that.

3D can of course be used to make caves, which is a side effect of the density interpretation. However, they don't look very good. They are round and not long and windy. With a few tricks, I got some nice caves going, with 3D simplex, see Making caves from Simplex noise.

At last a warning about 3d Simplex: It can be very costly. There are ways to improve the situation, for example using interpolation.

I also use 2D Simplex noise to control vegetation density. A low frequency variant to get forests, and a high frequency to control the individual trees.

The possibilities are unlimited. You can use a 2D low frequency Simplex to interpret as temperature, which would give you different biomes.

What I find very difficult to do, however, is making nice rivers from Simplex algorithms. Of course, there are other ways.
[size=2]Current project: Ephenation.
[size=2]Sharing OpenGL experiences: http://ephenationopengl.blogspot.com/
Very interesting larspensjo, but keep in mind that the OP will have to subtract 1 dimension from all your advice as they are making a 2D side scroller rather than a 3D world.

This topic is closed to new replies.

Advertisement