Jump to content
  • Advertisement
Sign in to follow this  
TheDreamTeam

Procedural Map generation

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

If you intended to correct an error in the post then please contact us.

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...:mellow:
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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!