# Procedural Map generation

This topic is 2570 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

So the last few days i have been working on a 2d tile procedural map generator for my opengl android engine similar to what games such as terraria have. after looking at a couple of algorithems i chose to go with Perlin noise. It is working great for creating things like caves but i cant get it to work for hills. The attached image just shows the top layer. I have searched the forums and the internet and havent found a anwser. If you would please look over my code and tell me what is wrong, that would be of much help! Thanks in advance! Also, no matter how i change it, it seems like the right top and right bottom corners are always square unlike the left side which changes...
EDIT: The picture shows about 4 chunks...

The code in which i use(coded in java):

public class RandomWorld extends BaseObject{ public int WorldSizeX = 50; public int WorldSizeY = 10; public int tilesizex = 50; public int tilesizey = 50; public boolean toprow = false; public int chunksx = 10; public int chunksy = 1; public int chunkwidth = 20; public int chunkheight = 10; public float mapsizex; public float mapsizey; public int counter = 0; public String file; public ArrayList<String> savefile = new ArrayList<String>(); boolean flip = false; float seed = 0; public RandomWorld() { } public void create() { this.savefile.clear(); for(int y = 0; y < chunksy; y++) for(int x = 0; x < this.chunksx; x++) this.addChunk(x,y); this.saveMap("test.cam"); this.mapsizex = chunksx * 50 * chunkwidth; this.mapsizey = chunksy * 50 * chunkheight; } float[][] GenerateWhiteNoise(int width, int height) { Random random = new Random((long) (Math.round(Math.random() * 100 * Math.random() * 10))); //Seed to 0 for testing float[][] noise; noise = new float[width][height]; for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { noise[j] = (float)random.nextDouble() % 1; } } return noise; } float[][] GenerateSmoothNoise(float[][] baseNoise, int octave) { int width = baseNoise.length; int height = baseNoise[0].length; float[][] smoothNoise; smoothNoise = new float[width][height]; int samplePeriod = 1 << octave; // calculates 2 ^ k float sampleFrequency = 1.0f / samplePeriod; for (int i = 0; i < width; i++) { //calculate the horizontal sampling indices int sample_i0 = (i / samplePeriod) * samplePeriod; int sample_i1 = (sample_i0 + samplePeriod) % width; //wrap around float horizontal_blend = (i - sample_i0) * sampleFrequency; for (int j = 0; j < height; j++) { //calculate the vertical sampling indices int sample_j0 = (j / samplePeriod) * samplePeriod; int sample_j1 = (sample_j0 + samplePeriod) % height; //wrap around float vertical_blend = (j - sample_j0) * sampleFrequency; //blend the top two corners float top = CosineInterpolate(baseNoise[sample_i0][sample_j0], baseNoise[sample_i1][sample_j0], horizontal_blend); //blend the bottom two corners float bottom = CosineInterpolate(baseNoise[sample_i0][sample_j1], baseNoise[sample_i1][sample_j1], horizontal_blend); //final blend smoothNoise[j] = CosineInterpolate(top, bottom, vertical_blend); } } return smoothNoise; } float Interpolate(float x0, float x1, float alpha) { return x0 * (1 - alpha) + alpha * x1; } float CosineInterpolate(double y1,double y2,double mu) { double mu2; mu2 = (1-Math.cos(mu*Math.PI))/2; return(float)(y1*(1-mu2)+y2*mu2); } float[][] GeneratePerlinNoise(float[][] baseNoise, int octaveCount) { int width = baseNoise.length; int height = baseNoise[0].length; float[][][] smoothNoise = new float[octaveCount][][]; //an array of 2D arrays containing float persistance = 0.25f; //generate smooth noise for (int i = 0; i < octaveCount; i++) { smoothNoise = GenerateSmoothNoise(baseNoise, i); } float[][] perlinNoise; perlinNoise = new float[width][height]; float amplitude = 1.0f; float totalAmplitude = 0.0f; //blend noise together for (int octave = octaveCount - 1; octave >= 0; octave--) { amplitude *= persistance; totalAmplitude += amplitude; for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { perlinNoise[j] += smoothNoise[octave][j] * amplitude; } } } //normalisation for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { perlinNoise[j] /= totalAmplitude; } } return perlinNoise; } public void addChunk(int chunknumberx, int chunknumbery) { ///Magic number = 5 float perlineNoise[][] = this.GeneratePerlinNoise(this.GenerateWhiteNoise(chunkwidth, chunkheight), 8); //System.out.println("Perline noise:" + perlineNoise[1][5]); this.counter++; Chunk chunk = new Chunk(); chunk.number = counter; String layer = null; for(int y = 0; y < perlineNoise[0].length; y++) { for(int x = 0; x < perlineNoise.length; x++) { if(perlineNoise[x][y] * 1000 < 725 && perlineNoise[x][y] * 1000 > 630) { Tile tile= null; float per = (float) Math.random(); if(per < 0.01) tile = new RedTile(); else tile = new GreenTile(); tile.setChunk(counter); tile.setPosition(new Vector2(x * 50 + chunknumberx * 50 * perlineNoise.length, -y * 50 + chunknumbery * 50* perlineNoise[0].length)); //this.addChild(tile); chunk.addChild(tile); layer = "Bottom"; } System.out.println("Perline noise:" + perlineNoise[x][y] * 1000); } } this.addChild(chunk); System.out.println("Chuck:" + this.counter + " Done! " + layer); } }

##### Share on other sites
I forget the name of the algorithm but here is the pseudo code for how it would work:

 Algorithm (left point, right point) While the distance between points has rooms for 1 point in between Middle point x = (left x + right x) / 2 middle point y = (left y + right y) / 2 + random height random height = random height / 2 Repeat this algorithm with Left and Middle Repeat this algorithm with Middle and Right. 

Because the random height addition is halved each time this should create rolling hills. Good luck.

##### Share on other sites
JBarrios: that is a midpoint displacement algorithm.

DreamTeam: I would stick with perlin noise over trying a different algorithm like that suggested by JBarrios. A good way to generate terrain from perlin noise is to treat the noise value as density. If a certain tile's value is less than 0 then treat it as empty space. If it's greater than 0 then that spot is solid ground. It looks like you might be doing something like that in your addChunk() method? Well here's something I've found useful. Add a number to each tile's value based on its height, so that tiles at the bottom of the map are solid more often than tiles at the top. That should give you solid ground at the bottom. As you go higher up, tile values drop until they reach some threshold and start becoming empty space. The perlin noise should then give you a nice hilly surface between the ground and sky.

Another option that might be simpler is to use 1-dimensional perlin noise to generate a height map. If your noise generator produces values from -1 to 1 then you can do something like: (newvalue = (oldvalue + 1) * 1000). That would give you a line of noise with values from 0 to 2000. You can use those values as the height of ground in each column of the map.

##### Share on other sites
Thanks for the replys! I am currently trying your first approach suspense, based on topic i found on stackexhange(I think thats the websites name). The problem is, is that no matter how i change the numbers, most of them up being above or below 0 so the chunk is either a complete block or its a floating island. Im also not sure if im adding weight right. Here is my code:

float[][] GeneratePerlinNoise(float[][] baseNoise, int octaveCount) { int width = baseNoise.length; int height = baseNoise[0].length; float[][][] smoothNoise = new float[octaveCount][][]; //an array of 2D arrays containing float persistance = 0.25f; //generate smooth noise for (int i = 0; i < octaveCount; i++) { smoothNoise = GenerateSmoothNoise(baseNoise, i); } float[][] perlinNoise; perlinNoise = new float[width][height]; float amplitude = 1f; float totalAmplitude = 0.0f; //blend noise together for (int octave = octaveCount - 1; octave >= 0; octave--) { amplitude *= persistance; totalAmplitude += amplitude; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { perlinNoise[j] += smoothNoise[octave][j] * amplitude; } } } //normalisation for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { perlinNoise[j] /= totalAmplitude; //Add weight if(perlinNoise[j] < 0) perlinNoise[j] += 0.1; } } return perlinNoise; }

EDIT: because of the weird values i tried using a different implementation of Perlin Noise. The one i was using was from http://devmag.org.za/2009/04/25/perlin-noise/ and the one im using now is http://freespace.virgin.net/hugo.elias/models/m_perlin.htm. The values are now acting like they should! To do the weight based on height i did:
public double PerlinNoise2D(float x, float y) { double total = 0; float p = 0.1f; float n = 9 - 1; for(int i = 0; i < n; i++) { float frequency = 0.1f*i; float amplitude = p*i; total = total + InterpolatedNoise(x * frequency, y * frequency) * amplitude; } total += y/10; <--- the line i added return total; }

Its not perfect but its way better! The picture shows 3 chunks.

##### Share on other sites
I've been doing something similar in 3D, here are some resources that could help you out.

http://www.gamedev.net/blog/33/entry-2227887-more-on-minecraft-type-world-gen/
http://accidentalnoise.sourceforge.net/minecraftworlds.html

They're by the same guy, and he doesn't show any code examples (he uses his own noise library, accidental noise, which is quite hard to understand), but it should help you out. I don't have much time at the moment because I have a lecture in half an hour but I can show you some of my code if you still need help.

1. 1
Rutin
69
2. 2
3. 3
4. 4
5. 5

• 21
• 10
• 33
• 20
• 9
• ### Forum Statistics

• Total Topics
633421
• Total Posts
3011794
• ### Who's Online (See full list)

There are no registered users currently online

×