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

# Diamond-square algorithm

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