Generating random 2D mountains/terrain

Does anyone have past knowledge on this (generating random 2D terrain using an algorithm)?

This is probably a stupid post, but, I'm desperate now. I've been trying to write (relatively simple) code to generate (and draw) random fractal terrain in a window sized 800 x 600- But I have failed at all attempts.

I've looked all over the web for the general idea and I found this: Generating Random Fractal Terrain.

My first problem is that I don't have a great idea on how to create "line segments". I've tried making an array with a start (x) position and an end (x) position... But that isn't working very well. If you want to see my code, I will post it (but it is kind of long, not to mention embarrassing).

I'm not necessarily looking for the whole code to be written out- I just need a push in the right direction (mainly on how to get the "line segments" going).

Any and all help would be appreciated!
Thanks in advance.

Unfortunantly I don't have my old code with me but the logic is really simple.

I broke apart my window into a grid and wrote a bunch of random floating point numbers into a file - one for each segment of the grid.

Then I wrote an algorithim to *smooth* the terrain; I wrote it so that any number after the first couldn't deviate by an amount greater than .03 (abstract constant) if the random number was greater and out of the range of .03; I'd add .03 to it; if it was lower I'd subtract. You need to perform this for all rows then all colums (So you get x/y smoothing)

Sometimes this creates a surface which is to flat; in which case you should 'draw' a raw across the one axis and randomly bend it; then 'drag' it across the opposite axis. to create a single sheet of mountain. Then you create rays for every line of the opposite axis and make a maximum % deviation. This will create a much better effect.

To draw the raw; just represent each point in your grid with a floating point number with a range (usually 0.0-1.0) starting all points at the midpoint; then pick a point in the array to 'bend' with a random % of bending (+/-) and bend the entire ray past the point you picked based on a % of the % of bending (so it's smooth) pick a couple of points with a minimum distance apart too. To do the opposite axis smoothing rays you need to pick a % max deviation and just randomly bend the ray again - MAKING SURE that the Y deviation is no greater than a certain perfect based on the adjacent Y.

Sorry I don't have the code; hopefully the explination made sense.

Thank you for the reply- it more or less made since.

In the second part of your post, are you saying to basically create an array of points across the x axis and bend it (displace the points) randomly, then drag it up the y axis to a certain degree?

I have some code I written. It was written in a hurry and it's really, really ugly. But if you get to understand it, you'll understand the basic algorithm.

The program uses this function, then smooths it using Gaussian blur. Then it creates a texture for the environment (really easy, blending several colors based upon height, so it doesn't look great).

While it's a really bad program, made as quickly as possible, and it's quite ugly, it displays how powerful the simple algorithm is. Taking this and spending some more time on fixing it would make the result a lot better looking. Which is quite doable with improvising, and I will definitely do it soon enough. Anyways, here's a screenshot:

http://img17.imageshack.us/img17/7963/worldt.png

EDIT: Ah, damn, I only just noticed you were talking about 2D, not 3D. 2D is quite similar to this, except that you only need a single step per displacement.

Code:

---

void Terrain::generateFractal(HeightMap &hm, double smoothness)
{
  unsigned int width, depth;
  width = hm.getWidth();
  depth = hm.getDepth();
 
  // The terrain width/height must be in the format (1<<x)+1
  if(width <= 1 ||depth != width || ((width-1) & (width-2))) {
    DEBUG("Invalid width/depth of terrain for fractal terrain generation: must be equal and a power of 2 plus one.");
    return;
  }
 
  int delta_step = width-1;
  double disposition_multiplier = 1.0/pow(2, smoothness);
  double disposition = HeightMap::max_height;
  while(delta_step > 1) {
    // Do the square step
    for(unsigned int left_x = 0; left_x < width - 1; left_x += delta_step) {
      for(unsigned int top_z = 0; top_z < depth - 1; top_z += delta_step) {
        int right_x = left_x + delta_step, bottom_z = top_z + delta_step;
        int center_x = (left_x + right_x) / 2, center_z = (top_z + bottom_z) / 2;
        double avg_height, new_value;
        HeightMap::height_type new_height;

        // Calculate the height of the center-point
        avg_height = hm.getHeight(left_x, top_z)/4.0 + hm.getHeight(right_x, top_z)/4.0 + hm.getHeight(left_x, bottom_z)/4.0 + hm.getHeight(right_x, bottom_z)/4.0;
        new_value = avg_height + ((rand() % (int)(2*disposition)) - disposition);
        if(new_value > HeightMap::max_height)
          new_value = HeightMap::max_height;
        else if(new_value < HeightMap::min_height)
          new_value = HeightMap::min_height;

        hm.setHeight(center_x, center_z, new_value);
      }
    }
   

    // Do the diamond step
    for(unsigned int left_x = 0; left_x < width - 1; left_x += delta_step) {
      for(unsigned int top_z = 0; top_z < depth - 1; top_z += delta_step) {       
        int right_x = left_x + delta_step, bottom_z = top_z + delta_step;
        int center_x = (left_x + right_x) / 2, center_z = (top_z + bottom_z) / 2;
        double avg_height, new_value;
        HeightMap::height_type new_height;

        // Loop through the four diamond points
        const int dx[] = { -1, 0, 1, 0 };
        const int dz[] = { 0, -1, 0, 1 };
        for(unsigned int dir = 0; dir < 4; dir++) {
          int diamond_x, diamond_z;
          diamond_x = center_x + dx[dir] * delta_step / 2;
          diamond_z = center_z + dz[dir] * delta_step / 2;
         
          // Get the surrounding points and find the average of them
          unsigned int num_points = 0;
          avg_height = 0;
          for(unsigned int avg_dir = 0; avg_dir < 4; avg_dir++) {
            int avg_x, avg_z;
            avg_x = diamond_x + dx[avg_dir] * delta_step / 2;
            avg_z = diamond_z + dz[avg_dir] * delta_step / 2;
            if(avg_x < 0 || avg_z < 0 || avg_z >= depth || avg_x >= width)
              continue;
             
            num_points++;
            avg_height += hm.getHeight(avg_x, avg_z);
          }
         
          avg_height /= num_points;
         
         
          // Now, calculate a random offset
          new_value = avg_height + ((rand() % (int)(2*disposition)) - disposition);
          if(new_value > HeightMap::max_height)
            new_value = HeightMap::max_height;
          else if(new_value < HeightMap::min_height)
            new_value = HeightMap::min_height;

          hm.setHeight(diamond_x, diamond_z, new_value);
        }
      }
    }
 
   
    // Do the next step with less disposition
    delta_step /= 2;
    disposition *= disposition_multiplier;
  }
}

---

Quote:

---

Originally Posted by Flaug

Thank you for the reply- it more or less made since.

In the second part of your post, are you saying to basically create an array of points across the x axis and bend it (displace the points) randomly, then drag it up the y axis to a certain degree?

---

Sort of; you drag it so it fills an array of points on the covering the whole screen. So if you have a 10x10 grid; you'd fill points [0], [10], [20]... ect with the same point (So you really only create 1 bending in motion in the X axis). Then you switch perspective and gather the line across the Y axis and randomly bend it by a random % (should be rather small). Depending on your % of bending about the Y axis; you may need to take into account adjacent X particles as well.

Evo's algorithim is quite nice too; his will give a better random distribution but may not smooth as cleanly.

This should probably be in the games forum. Oh, and...

Let me google that for you

Another easy approach is to use a mixture of Gaussian (normal) distributions. Randomly choose k points on your grid to be the centre (mean) of a 2D Gaussian (these will be the peaks of hills), then generate the points around the grid by sampling from each Gaussian and multiplying the result. You'll get nice smooth hills this way.

You should be able to easly find code for generating points from a 2D Gaussian, the equation is pretty straight forward.


edit: example http://www.cs.uiuc.edu/homes/yyz/research/neurosurf/

Thank you all for your replies. They have been most helpful!