Thread: Generating random 2D mountains/terrain

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    45

    Post 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.

  2. #2
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    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.
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    45
    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?

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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;
      }
    }
    Last edited by EVOEx; 04-12-2009 at 05:20 AM.

  5. #5
    60% Braindead
    Join Date
    Dec 2005
    Posts
    379
    Quote Originally Posted by Flaug View Post
    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.
    Code:
    Error W8057 C:\\Life.cpp: Invalid number of arguments in function run(Brain *)

  6. #6
    Registered User
    Join Date
    Apr 2008
    Posts
    890
    This should probably be in the games forum. Oh, and...

    Let me google that for you

  7. #7
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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/

  8. #8
    Registered User
    Join Date
    Apr 2009
    Posts
    45
    Thank you all for your replies. They have been most helpful!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Generating random letters
    By ominub in forum C Programming
    Replies: 6
    Last Post: 04-29-2009, 01:12 AM
  2. Generating a random number?
    By Konspiracy in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 12:33 AM
  3. Help generating multiple random numbers
    By d-dub in forum C++ Programming
    Replies: 7
    Last Post: 10-30-2006, 01:00 PM
  4. Replies: 7
    Last Post: 09-26-2005, 05:09 PM
  5. Generating Random Numbers
    By FromHolland in forum C++ Programming
    Replies: 6
    Last Post: 06-16-2003, 09:05 AM

Tags for this Thread