2D Random Map Generation: Where to start

Where would I start to learn 2D random map generation. I’ve heard about simplex noise, perlin noise, and other noises and I have even looked at the algorithms, but I have absolutely no idea how I would put these methods into a game. And is simplex noise and perlin noise the correct things to use.

The closest I got to random map generation is making a game where it has a 50% chance of one tile and the other. That looks super ugly however. I would want to make a game where the random generation actually looks decent of course, and perhaps seeds? I don’t know. I just need a place to start.

Not enough information… what are you trying to do? 2D? 3D? What style are you going for, etc…

Oh I apologize. 2D Generation of course.

Still not enough information.

Side-view or top-down/birds-eye?
Does the map wrap?

Hey man i have just started this myself and have successfully got it working very well, if you would like the resources i used and wana see the actual class just drop me a message on skype at @mythirdleg35

But if you cant be botherd look up noise generation for 2D images

Those are all implementation details. OP needs to learn to think conceptually and mathematically; once you do that all kinds of applications for things like noise will spring forth unbidden.

Common example: sidescroller-type height maps:

Can be easily accomplished via the midpoint displacement algorithm: (or splines! or whatever you want, etc)
http://www.gameprogrammer.com/fractal.html

This is farther generalized to the diamond-square algorithm for more dimensions.
You can see that both in the link and in the post I made a little while ago:

Other algorithms like Simplex can accomplish the same tasks as these, but may also have additional properties like continuous derivatives, etc. which may be desirable.

For the sidecroller, you could potentially even do a sum of sine waves to get you the wave-y line, it doesn’t matter. All that matters is how you interpret the information.

noise generation class

public class NoiseGenerator {

	
	@SuppressWarnings("unused")
	public static float[][] generateOctavedSimplexNoise(int width, int height, int startX, int startY,int octaves, float roughness, float scale) {
	      float[][] totalNoise = new float[width][height];
	       float layerFrequency = scale;
	       float layerWeight = 1;
	       float weightSum = 0;

	       for (int octave = 0; octave < octaves; octave++) {
	          //Calculate single layer/octave of simplex noise, then add it to total noise
	          for(int x = 0; x < width; x++){
	             for(int y = 0; y < height; y++){
	                totalNoise[x][y] += (float) noise((x+startX) * layerFrequency,(y+startY) * layerFrequency) * layerWeight;
	             }
	          }
	          
	          //Increase variables with each incrementing octave
	           layerFrequency *= 2;
	           weightSum += layerWeight;
	           layerWeight *= roughness;
	           
	       }
	       return totalNoise;
	   }

	private static int grad3[][] = { { 1, 1, 0 }, { -1, 1, 0 }, { 1, -1, 0 },
			{ -1, -1, 0 }, { 1, 0, 1 }, { -1, 0, 1 }, { 1, 0, -1 },
			{ -1, 0, -1 }, { 0, 1, 1 }, { 0, -1, 1 }, { 0, 1, -1 },
			{ 0, -1, -1 } };
	private static int grad4[][] = { { 0, 1, 1, 1 }, { 0, 1, 1, -1 },
			{ 0, 1, -1, 1 }, { 0, 1, -1, -1 }, { 0, -1, 1, 1 },
			{ 0, -1, 1, -1 }, { 0, -1, -1, 1 }, { 0, -1, -1, -1 },
			{ 1, 0, 1, 1 }, { 1, 0, 1, -1 }, { 1, 0, -1, 1 }, { 1, 0, -1, -1 },
			{ -1, 0, 1, 1 }, { -1, 0, 1, -1 }, { -1, 0, -1, 1 },
			{ -1, 0, -1, -1 }, { 1, 1, 0, 1 }, { 1, 1, 0, -1 },
			{ 1, -1, 0, 1 }, { 1, -1, 0, -1 }, { -1, 1, 0, 1 },
			{ -1, 1, 0, -1 }, { -1, -1, 0, 1 }, { -1, -1, 0, -1 },
			{ 1, 1, 1, 0 }, { 1, 1, -1, 0 }, { 1, -1, 1, 0 }, { 1, -1, -1, 0 },
			{ -1, 1, 1, 0 }, { -1, 1, -1, 0 }, { -1, -1, 1, 0 },
			{ -1, -1, -1, 0 } };
	private static int p[] = { 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 };
	// To remove the need for index wrapping, double the permutation table
	// length
	private static int perm[] = new int[512];
	static {
		for (int i = 0; i < 512; i++)
			perm[i] = p[i & 255];
	}
	// A lookup table to traverse the simplex around a given point in 4D.
	// Details can be found where this table is used, in the 4D noise method.
	private static int simplex[][] = { { 0, 1, 2, 3 }, { 0, 1, 3, 2 },
			{ 0, 0, 0, 0 }, { 0, 2, 3, 1 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 1, 2, 3, 0 }, { 0, 2, 1, 3 }, { 0, 0, 0, 0 },
			{ 0, 3, 1, 2 }, { 0, 3, 2, 1 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 1, 3, 2, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 1, 2, 0, 3 }, { 0, 0, 0, 0 },
			{ 1, 3, 0, 2 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
			{ 2, 3, 0, 1 }, { 2, 3, 1, 0 }, { 1, 0, 2, 3 }, { 1, 0, 3, 2 },
			{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 2, 0, 3, 1 },
			{ 0, 0, 0, 0 }, { 2, 1, 3, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 2, 0, 1, 3 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 3, 0, 1, 2 }, { 3, 0, 2, 1 },
			{ 0, 0, 0, 0 }, { 3, 1, 2, 0 }, { 2, 1, 0, 3 }, { 0, 0, 0, 0 },
			{ 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 3, 1, 0, 2 }, { 0, 0, 0, 0 },
			{ 3, 2, 0, 1 }, { 3, 2, 1, 0 } };

	// This method is a *lot* faster than using (int)Math.floor(x)
	private static int fastfloor(double x) {
		return x > 0 ? (int) x : (int) x - 1;
	}

	private static double dot(int g[], double x, double y) {
		return g[0] * x + g[1] * y;
	}

	private static double dot(int g[], double x, double y, double z, double w) {
		return g[0] * x + g[1] * y + g[2] * z + g[3] * w;
	} // 2D simplex noise

	public static double noise(double xin, double yin) {
		double n0, n1, n2; // Noise contributions from the three corners
		// Skew the input space to determine which simplex cell we're in
		final double F2 = 0.5 * (Math.sqrt(3.0) - 1.0);
		double s = (xin + yin) * F2; // Hairy factor for 2D
		int i = fastfloor(xin + s);
		int j = fastfloor(yin + s);
		final double G2 = (3.0 - Math.sqrt(3.0)) / 6.0;
		double t = (i + j) * G2;
		double X0 = i - t; // Unskew the cell origin back to (x,y) space
		double Y0 = j - t;
		double x0 = xin - X0; // The x,y distances from the cell origin
		double y0 = yin - 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
		double x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed
									// coords
		double y1 = y0 - j1 + G2;
		double x2 = x0 - 1.0 + 2.0 * G2; // Offsets for last corner in (x,y)
											// unskewed coords
		double y2 = y0 - 1.0 + 2.0 * G2;
		// Work out the hashed gradient indices of the three simplex corners
		int ii = i & 255;
		int jj = j & 255;
		int gi0 = perm[ii + perm[jj]] % 12;
		int gi1 = perm[ii + i1 + perm[jj + j1]] % 12;
		int gi2 = perm[ii + 1 + perm[jj + 1]] % 12;
		// Calculate the contribution from the three corners
		double t0 = 0.5 - x0 * x0 - y0 * y0;
		if (t0 < 0)
			n0 = 0.0;
		else {
			t0 *= t0;
			n0 = t0 * t0 * dot(grad3[gi0], x0, y0); // (x,y) of grad3 used for
													// 2D gradient
		}
		double t1 = 0.5 - x1 * x1 - y1 * y1;
		if (t1 < 0)
			n1 = 0.0;
		else {
			t1 *= t1;
			n1 = t1 * t1 * dot(grad3[gi1], x1, y1);
		}
		double t2 = 0.5 - x2 * x2 - y2 * y2;
		if (t2 < 0)
			n2 = 0.0;
		else {
			t2 *= t2;
			n2 = t2 * t2 * dot(grad3[gi2], 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 70.0 * (n0 + n1 + n2);
	}

	double noise(double x, double y, double z, double w) {

		// The skewing and unskewing factors are hairy again for the 4D case
		final double F4 = (Math.sqrt(5.0) - 1.0) / 4.0;
		final double G4 = (5.0 - Math.sqrt(5.0)) / 20.0;
		double n0, n1, n2, n3, n4; // Noise contributions from the five corners
		// Skew the (x,y,z,w) space to determine which cell of 24 simplices
		// we're in
		double s = (x + y + z + w) * F4; // Factor for 4D skewing
		int i = fastfloor(x + s);
		int j = fastfloor(y + s);
		int k = fastfloor(z + s);
		int l = fastfloor(w + s);
		double t = (i + j + k + l) * G4; // Factor for 4D unskewing
		double X0 = i - t; // Unskew the cell origin back to (x,y,z,w) space
		double Y0 = j - t;
		double Z0 = k - t;
		double W0 = l - t;
		double x0 = x - X0; // The x,y,z,w distances from the cell origin
		double y0 = y - Y0;
		double z0 = z - Z0;
		double w0 = w - W0;
		// For the 4D case, the simplex is a 4D shape I won't even try to
		// describe.
		// To find out which of the 24 possible simplices we're in, we need to
		// determine the magnitude ordering of x0, y0, z0 and w0.
		// The method below is a good way of finding the ordering of x,y,z,w and
		// then find the correct traversal order for the simplex we’re in.
		// First, six pair-wise comparisons are performed between each possible
		// pair
		// of the four coordinates, and the results are used to add up binary
		// bits
		// for an integer index.
		int c1 = (x0 > y0) ? 32 : 0;
		int c2 = (x0 > z0) ? 16 : 0;
		int c3 = (y0 > z0) ? 8 : 0;
		int c4 = (x0 > w0) ? 4 : 0;
		int c5 = (y0 > w0) ? 2 : 0;
		int c6 = (z0 > w0) ? 1 : 0;
		int c = c1 + c2 + c3 + c4 + c5 + c6;
		int i1, j1, k1, l1; // The integer offsets for the second simplex corner
		int i2, j2, k2, l2; // The integer offsets for the third simplex corner
		int i3, j3, k3, l3; // The integer offsets for the fourth simplex corner
		// simplex[c] is a 4-vector with the numbers 0, 1, 2 and 3 in some
		// order.
		// Many values of c will never occur, since e.g. x>y>z>w makes x<z, y<w
		// and x<w
		// impossible. Only the 24 indices which have non-zero entries make any
		// sense.
		// We use a thresholding to set the coordinates in turn from the largest
		// magnitude.
		// The number 3 in the "simplex" array is at the position of the largest
		// coordinate.
		i1 = simplex[c][0] >= 3 ? 1 : 0;
		j1 = simplex[c][1] >= 3 ? 1 : 0;
		k1 = simplex[c][2] >= 3 ? 1 : 0;
		l1 = simplex[c][3] >= 3 ? 1 : 0;
		// The number 2 in the "simplex" array is at the second largest
		// coordinate.
		i2 = simplex[c][0] >= 2 ? 1 : 0;
		j2 = simplex[c][1] >= 2 ? 1 : 0;
		k2 = simplex[c][2] >= 2 ? 1 : 0;
		l2 = simplex[c][3] >= 2 ? 1 : 0;
		// The number 1 in the "simplex" array is at the second smallest
		// coordinate.
		i3 = simplex[c][0] >= 1 ? 1 : 0;
		j3 = simplex[c][1] >= 1 ? 1 : 0;
		k3 = simplex[c][2] >= 1 ? 1 : 0;
		l3 = simplex[c][3] >= 1 ? 1 : 0;
		// The fifth corner has all coordinate offsets = 1, so no need to look
		// that up.
		double x1 = x0 - i1 + G4; // Offsets for second corner in (x,y,z,w)
									// coords
		double y1 = y0 - j1 + G4;
		double z1 = z0 - k1 + G4;
		double w1 = w0 - l1 + G4;
		double x2 = x0 - i2 + 2.0 * G4; // Offsets for third corner in (x,y,z,w)
										// coords
		double y2 = y0 - j2 + 2.0 * G4;
		double z2 = z0 - k2 + 2.0 * G4;
		double w2 = w0 - l2 + 2.0 * G4;
		double x3 = x0 - i3 + 3.0 * G4; // Offsets for fourth corner in
										// (x,y,z,w) coords
		double y3 = y0 - j3 + 3.0 * G4;
		double z3 = z0 - k3 + 3.0 * G4;
		double w3 = w0 - l3 + 3.0 * G4;
		double x4 = x0 - 1.0 + 4.0 * G4; // Offsets for last corner in (x,y,z,w)
											// coords
		double y4 = y0 - 1.0 + 4.0 * G4;
		double z4 = z0 - 1.0 + 4.0 * G4;
		double w4 = w0 - 1.0 + 4.0 * G4;
		// Work out the hashed gradient indices of the five simplex corners
		int ii = i & 255;
		int jj = j & 255;
		int kk = k & 255;
		int ll = l & 255;
		int gi0 = perm[ii + perm[jj + perm[kk + perm[ll]]]] % 32;
		int gi1 = perm[ii + i1 + perm[jj + j1 + perm[kk + k1 + perm[ll + l1]]]] % 32;
		int gi2 = perm[ii + i2 + perm[jj + j2 + perm[kk + k2 + perm[ll + l2]]]] % 32;
		int gi3 = perm[ii + i3 + perm[jj + j3 + perm[kk + k3 + perm[ll + l3]]]] % 32;
		int gi4 = perm[ii + 1 + perm[jj + 1 + perm[kk + 1 + perm[ll + 1]]]] % 32;
		// Calculate the contribution from the five corners
		double t0 = 0.6 - x0 * x0 - y0 * y0 - z0 * z0 - w0 * w0;
		if (t0 < 0)
			n0 = 0.0;
		else {
			t0 *= t0;
			n0 = t0 * t0 * dot(grad4[gi0], x0, y0, z0, w0);
		}
		double t1 = 0.6 - x1 * x1 - y1 * y1 - z1 * z1 - w1 * w1;
		if (t1 < 0)
			n1 = 0.0;
		else {
			t1 *= t1;
			n1 = t1 * t1 * dot(grad4[gi1], x1, y1, z1, w1);
		}
		double t2 = 0.6 - x2 * x2 - y2 * y2 - z2 * z2 - w2 * w2;
		if (t2 < 0)
			n2 = 0.0;
		else {
			t2 *= t2;
			n2 = t2 * t2 * dot(grad4[gi2], x2, y2, z2, w2);
		}
		double t3 = 0.6 - x3 * x3 - y3 * y3 - z3 * z3 - w3 * w3;
		if (t3 < 0)
			n3 = 0.0;
		else {
			t3 *= t3;
			n3 = t3 * t3 * dot(grad4[gi3], x3, y3, z3, w3);
		}
		double t4 = 0.6 - x4 * x4 - y4 * y4 - z4 * z4 - w4 * w4;
		if (t4 < 0)
			n4 = 0.0;
		else {
			t4 *= t4;
			n4 = t4 * t4 * dot(grad4[gi4], x4, y4, z4, w4);
		}
		// Sum up and scale the result to cover the range [-1,1]
		return 27.0 * (n0 + n1 + n2 + n3 + n4);
	}
}

then this is how you use it

first pull the data

float[][] newTiles = NoiseGenerator.generateOctavedSimplexNoise(width, height,
					startx, starty, 5, 0.4F, 0.003f);

then do some if statments like this


for(int x = 0;x< newTiles.length; x++){
			for(int y = 0;y< newTiles[0].length; y++){
				if(newTiles[x][y]<0.00F){
					if(newTiles[x][y]<-0.35F){
						newTileIDs[x][y] = Tile.DEEP_WATER.getID();
					}else{
						newTileIDs[x][y] = Tile.WATER.getID();
					}
					
				}else{
					newTileIDs[x][y] = Tile.GRASS.getID();
				}
			}
		}

if you want to see a actual example just ask

Could you also use cosine waves to generate such terrain? I remember reading an article that explained how Fingersoft created their levels for Hill Climb Racing, I am sure it mentioned something like that.

I ninja’d you.

Is that Longarmx’s noise generator?

EDIT: Nevermind, I remember seeing someone post that and it was him, however he is not the original owner.

I cant recall where i got the generator from but all i know is its works great :smiley: you get a output like this

I would prefer 2D Top-Down Tile-Based generation. Or just Tile-Based in general.

Which that is? :stuck_out_tongue: the image i just showen was only a representation

What happens if you interpret each pixel in the image as a tile? Voila.

Thats what i do, that was just a screenshot of my map xD

This was done with the diamond-square algorithm, which has the advantage of wrapping.

More examples at full resolution: http://imgur.com/a/kmGTc

Nice! i know i can get my map/game looking like that with the gen im running but im working on all the map storage and performance at the beginning to make development easier

I have looked and i cant seem to find a good example of how to use this algorithm, where dod you go?

There are plenty of examples on google.