Back to General and Gameplay Programming

How to use Perlin noise in terrain generation

Morten · 2012-09-08T18:50:37

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

General and Gameplay Programming Programming

Started by Mekuri September 07, 2012 03:57 PM

12 comments, last by Mekuri 11 years, 7 months ago

riuthamus

8,390

September 08, 2012 12:01 PM

I actually like the idea of the 3d one... so thanks for posting it!

For the OP, we found that perlin worked the best, I would play with it, see if you can create an in game render system that will let you modify values and click GENERATE, this is what we did and it let us find the best results quick.

swiftcoder

18,997

September 08, 2012 12:35 PM

For the OP, we found that perlin worked the best

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

riuthamus

8,390

September 08, 2012 03:40 PM

[quote name='riuthamus' timestamp='1347105672' post='4977958']
For the OP, we found that perlin worked the best

Simplex and perlin noise are pretty much indistinguishable - the one is a further development of the other.

Unless, of course, you learned about perlin noise here, which is wrong (it actually describes 'Value Noise', combined with 'Fractal Brownian Motion').
[/quote]

I never said they were or were not... i simply said what we went with. We have not touched terrain generation in months since we have been focused on character creation, items, crafting, spells, so when we get back to it I will most certainly take a look at the Simplex process. I can tell you, that the main point of my post was that having an in game generation setup was much more helpful than closing, recompiling, and doing it all over again. *shrugs* that is how it has worked for us.... perhaps that wont for you, or anybody else. Simply sharing my thoughts friend!

Mekuri

301

Author

September 08, 2012 06:50 PM

I have been playing around with both 1D and 2D for some time now. I'm still learning as I go, since the math of this is still beyond my full comprehension.

I've managed to do some decent terrain with 1D and then use 2D noise to add some caves and such. I'm not satisfied with the results yet, but I am further than I've been for weeks

Now I need some way to randomize my output, as it seems atm things only change when I change the frequency, and I hope that it isn't the only variable that can change the output, since the results can easly go from good to disaster if the value is changed too much.
Also I think I'll try looking into doing some octaves, since I wouldn't mind the terrain to be slightly more jagged.

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 actually did read about half of that article yesterday, I really liked the first part of it. I did kinda lose focus about halfway through. I think I'll need to read it a few times, but I'll probably wait til I'm over this flu

For the OP, we found that perlin worked the best, I would play with it, see if you can create an in game render system that will let you modify values and click GENERATE, this is what we did and it let us find the best results quick.

That's a good idea, and I think I could save quite a bit of time doing that, and it could also be a useful addition to the final game. - Thanks for the idea.

Thanks a lot for all the input- This really is an interesting, but difficult topic (at least for me

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

How to use Perlin noise in terrain generation

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

How to use Perlin noise in terrain generation

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines