This discussion is archived
7 Replies Latest reply: Sep 8, 2010 7:46 AM by 843853 RSS

Diamond-square algorithm

843853 Newbie
Currently Being Moderated
Hello all,

I came across an interesting article about the diamond-square algorithm and decided to make a Java version. This first version is just an experiment and I intend to make a version that uses float values. I might also try to put in an option to make the wrappability optional.

Here's the page I used as a reference: http://www.gameprogrammer.com/fractal.html

Here's the source code. It's still a bit of a quick-hack class, but I tried to make it as readable as possible.

Part 1:
/**
 * This class creates height maps that can be used for various purposes, such as
 * cloud generation, terrain generation, etc. A height map made by this class is
 * wrappable.<br>
 * <br>
 * <a href=http://www.gameprogrammer.com/fractal.html>Diamond-square algorithm</a>
 * 
 * @author Marcel Veltman
 */
public class DSAlgorithm {

     /**
      * This method uses the seed value to initialize the four corners of the
      * map. The variation creates randomness in the map. The size of the array
      * is determined by the amount of iterations (i.e. 1 iteration -> 3x3 array,
      * 2 iterations -> 5x5 array, etc.).
      * 
      * @param iterations
      *            the amount of iterations to do (minimum of 1)
      * @param seed
      *            the starting value
      * @param variation
      *            the amount of randomness in the height map (minimum of 0)
      * @return a height map in the form of a 2-dimensional array containing
      *         integer values or null if the arguments are out of range
      */
     public static int[][] makeHeightMap(int iterations, int seed, int variation) {
          if (iterations < 1 || variation < 0) {
               return null;
          }
          
          int size = (1 << iterations) + 1;
          int[][] map = new int[size][size];
          final int maxIndex = map.length - 1;

          // seed the corners
          map[0][0] = seed;
          map[0][maxIndex] = seed;
          map[maxIndex][0] = seed;
          map[maxIndex][maxIndex] = seed;

          for (int i = 1; i <= iterations; i++) {
               int minCoordinate = maxIndex >> i;// Minimum coordinate of the
                                                         // current map spaces
               size = minCoordinate << 1;// Area surrounding the current place in
                                               // the map

               diamondStep(minCoordinate, size, map, variation);
               squareStepEven(minCoordinate, map, size, maxIndex, variation);
               squareStepOdd(map, size, minCoordinate, maxIndex, variation);

               variation = variation >> 1;// Divide variation by 2
          }

          return map;
     }

     /**
      * Calculates average values of four corner values taken from the smallest
      * possible square.
      * 
      * @param minCoordinate
      *            the x and y coordinate of the first square center
      * @param size
      *            width and height of the squares
      * @param map
      *            the height map to fill
      * @param variation
      *            the randomness in the height map
      */
     private static void diamondStep(int minCoordinate, int size, int[][] map,
               int variation) {
          for (int x = minCoordinate; x < (map.length - minCoordinate); x += size) {
               for (int y = minCoordinate; y < (map.length - minCoordinate); y += size) {
                    int left = x - minCoordinate;
                    int right = x + minCoordinate;
                    int up = y - minCoordinate;
                    int down = y + minCoordinate;

                    // the four corner values
                    int val1 = map[left][up];   // upper left
                    int val2 = map[left][down]; // lower left
                    int val3 = map[right][up];  // upper right
                    int val4 = map[right][down];// lower right

                    calculateAndInsertAverage(val1, val2, val3, val4, variation,
                              map, x, y);
               }
          }
     }

     /**
      * Calculates average values of four corner values taken from the smallest
      * possible diamond. This method calculates the values for the even rows,
      * starting with row 0.
      * 
      * @param minCoordinate
      *            the x-coordinate of the first diamond center
      * @param map
      *            the height map to fill
      * @param size
      *            the length of the diagonals of the diamonds
      * @param maxIndex
      *            the maximum index in the array
      * @param variation
      *            the randomness in the height map
      */
     private static void squareStepEven(int minCoordinate, int[][] map,
               int size, int maxIndex, int variation) {
          for (int x = minCoordinate; x < map.length; x += size) {
               for (int y = 0; y < map.length; y += size) {
                    if (y == maxIndex) {
                         map[x][y] = map[x][0];
                         continue;
                    }

                    int left = x - minCoordinate;
                    int right = x + minCoordinate;
                    int down = y + minCoordinate;
                    int up = 0;

                    if (y == 0) {
                         up = maxIndex - minCoordinate;
                    } else {
                         up = y - minCoordinate;
                    }

                    // the four corner values
                    int val1 = map[left][y]; // left
                    int val2 = map[x][up];   // up
                    int val3 = map[right][y];// right
                    int val4 = map[x][down]; // down

                    calculateAndInsertAverage(val1, val2, val3, val4, variation,
                              map, x, y);
               }
          }
     }
  • 1. Re: Diamond-square algorithm
    843853 Newbie
    Currently Being Moderated
    Part 2:
         /**
          * Calculates average values of four corner values taken from the smallest
          * possible diamond. This method calculates the values for the odd rows,
          * starting with row 1.
          * 
          * @param minCoordinate
          *            the x-coordinate of the first diamond center
          * @param map
          *            the height map to fill
          * @param size
          *            the length of the diagonals of the diamonds
          * @param maxIndex
          *            the maximum index in the array
          * @param variation
          *            the randomness in the height map
          */
         private static void squareStepOdd(int[][] map, int size, int minCoordinate,
                   int maxIndex, int variation) {
              for (int x = 0; x < map.length; x += size) {
                   for (int y = minCoordinate; y < map.length; y += size) {
                        if (x == maxIndex) {
                             map[x][y] = map[0][y];
                             continue;
                        }
    
                        int left = 0;
                        int right = x + minCoordinate;
                        int down = y + minCoordinate;
                        int up = y - minCoordinate;
    
                        if (x == 0) {
                             left = maxIndex - minCoordinate;
                        } else {
                             left = x - minCoordinate;
                        }
    
                        // the four corner values
                        int val1 = map[left][y]; // left
                        int val2 = map[x][up];   // up
                        int val3 = map[right][y];// right
                        int val4 = map[x][down]; // down
    
                        calculateAndInsertAverage(val1, val2, val3, val4, variation,
                                  map, x, y);
                   }
              }
         }
    
         /**
          * Calculates an average value, adds a variable amount to that value and
          * inserts it into the height map.
          * 
          * @param val1
          *            first of the values used to calculate the average
          * @param val2
          *            second of the values used to calculate the average
          * @param val3
          *            third of the values used to calculate the average
          * @param val4
          *            fourth of the values used to calculate the average
          * @param variation
          *            adds variation to the average value
          * @param map
          *            the height map to fill
          * @param x
          *            the x-coordinate of the place to fill 
          * @param y
          *            the y-coordinate of the place to fill
          */
         private static void calculateAndInsertAverage(int val1, int val2, int val3,
                   int val4, int variation, int[][] map, int x, int y) {
              int avg = (val1 + val2 + val3 + val4) >> 2;// average
              int var = (int) ((Math.random() * ((variation << 1) + 1)) - variation);
              map[x][y] = avg + var;
         }
    
         public static void main(String[] args) {
              final int[][] map = makeHeightMap(9, 128, 128);
              
    //          for (int y = 0; y < map.length; y++) {
    //               for (int x = 0; x < map[y].length; x++) {
    //                    System.out.printf("[%3d]", map[x][y]);
    //               }
    //               System.out.println();
    //          }
              
              javax.swing.JFrame frame = new javax.swing.JFrame();
              javax.swing.JPanel panel = new javax.swing.JPanel(){
                   public void paint(java.awt.Graphics g){
                        super.paint(g);
                        for(int y = 0; y < map.length; y++){
                             for(int x = 0; x < map.length; x++){
                                  int value = map[x][y];
                                  if(value > 255){
                                       value = 255;
                                  }else if(value < 0){
                                       value = 0;
                                  }
                                  java.awt.Color color = new java.awt.Color(value, value, value);
                                  g.setColor(color);
                                  g.fillRect(x, y, 1, 1);
                             }
                        }
                   }
              };
              panel.setPreferredSize(new java.awt.Dimension(map.length, map.length));
              frame.setContentPane(panel);
              frame.setDefaultCloseOperation(javax.swing.JFrame.EXIT_ON_CLOSE);
              frame.pack();
              frame.setVisible(true);
         }
    
    }
    Kind regards,

    X
  • 2. Re: Diamond-square algorithm
    796262 Newbie
    Currently Being Moderated
    Do you have a question, or...
  • 3. Re: Diamond-square algorithm
    843853 Newbie
    Currently Being Moderated
    Nope, no questions, just something I wanted to share.
  • 4. Re: Diamond-square algorithm
    796262 Newbie
    Currently Being Moderated
    XtremeRPGplayer wrote:
    Nope, no questions, just something I wanted to share.
    Okay, cool. Word to the wise though: I'd suggest throwing your code together in an applet or runnable JAR (or better yet, a Web Start), if you want people to play with it. Then provide a link to the source, if that's something you want people to check out. I do something similar on my blog.

    On these forums though, posting your code in SSCCE form should be enough to get people to try it out. Call us lazy, but people are less likely to run code that's in the form you posted.
  • 5. Re: Diamond-square algorithm
    843853 Newbie
    Currently Being Moderated
    Well, this is a single (but big) runnable class (+main()+ is at the bottom). I'll provide later versions in a JAR file, as I don't know anything about Web Start.

    By the way, nice blog.
  • 6. Re: Diamond-square algorithm
    796262 Newbie
    Currently Being Moderated
    XtremeRPGplayer wrote:
    Well, this is a single (but big) runnable class (+main()+ is at the bottom). I'll provide later versions in a JAR file, as I don't know anything about Web Start.
    Well if you can put together a JAR file, then you can put together a Web Start. I think most Java experts prefer a Web Start over a JAR or an applet (disclaimer- I am not a Java expert). [This |http://download.oracle.com/javase/tutorial/deployment/webstart/] tutorial has helped me immensely, or you could also look at how I put my code together.

    Anyway, much luck!
  • 7. Re: Diamond-square algorithm
    843853 Newbie
    Currently Being Moderated
    Thanks