7 Replies Latest reply: Sep 8, 2010 9:46 AM by 843853 RSS

    Diamond-square algorithm

    843853
      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
          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
            Do you have a question, or...
            • 3. Re: Diamond-square algorithm
              843853
              Nope, no questions, just something I wanted to share.
              • 4. Re: Diamond-square algorithm
                796262
                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
                  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
                    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
                      Thanks