Square Diamond Fractal Maps

Raknarg · **Posted:** Tue Feb 07, 2012 6:57 pm

Has anyone successfully used the square diamond algorithm in a fractal height map? If so, I was wondering if you'd let me see it. I'm trying to do it right now, and I'm stuck. I can do it recursively, but if you do that it doesn't fuction properly, because you need to do ALL the squares, then ALL the diamonds, and so on. So I can't solve it, because it seems to use a form of recursion which changes how the the recursion will work everytime it enters a new teir of points :S

POint is, I'm confused. Could anyone show me any source code, or explain the concept of how you would make the algorithm?

DemonWasp · **Posted:** Wed Feb 08, 2012 7:20 am

I did write this exact algorithm recently. The pseudocode explanation is neater:

Pseudocode:

code:

int step_size = (some number, probably GCD(array_x, array_y)) // I used array_x = 2 * step_size, array_y = step_size

while ( step_size >= 1 ) do:
square_step across entire array
diamond_step across entire array
done

Both square_step and diamond_step work the same way:

code:

for x from 0 to array_x by step_size do:
for y from 0 to array_y by step_size do:
(square step or diamond step, as appropriate)

I would attach my code, but I think attachments are disabled in General Discussion. I certainly can't find anything that would let me attach something here.

Raknarg · **Posted:** Wed Feb 08, 2012 12:41 pm

Can you pm me?

DemonWasp · **Posted:** Fri Feb 10, 2012 11:08 am

Actually, I think I'll just embed the Java source. Sorry it took me so long to get back to you. Also, this may be a bit buggy, as I haven't thoroughly tested it.

HeightField.java, which handles storing the heighfield and any "wrapping" necessary.
The most important bits are the get/set methods and the writeImage() method, which outputs a pretty picture of the heightmap (shown from above).

Java:

package midpoint;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;

public class HeightField {

public enum WrapMode {
Bicylindrical {
public int index ( int x, int y, int width, int height ) {
x %= width;
if ( x < 0 ) {
x += width;
}
y %= height;
if ( y < 0 ) {
y += height;
}
return y * width + x;
}
},
/**
   * In the X direction, map as if the world were a cylinder.
   * In the Y direction, if we overflow above, flow down on the opposite
   * side; if we overflow below, flow up on the opposite side.
   * Do the Y direction first so we only need to normalise width once.
   */
Spherical {
public int index ( int x, int y, int width, int height ) {
// Y / Height
if ( y >= height ) {
// height, minus the amount we exceeded height by
y = height - (y % height);
x += width / 2;
} else if ( y < 0 ) {
// 0, plus the amount we were "too low" by
y = - ( y % height );
x += width / 2;
}
if ( y == height ) {
y = height - 1;
}

// X / Width
x %= width;
if ( x < 0 ) {
x += width;
}

return y * width + x;
}
};

public abstract int index ( int x, int y, int width, int height );
}

protected final int width, height;
protected final WrapMode wrap;

/**
   * "Two-dimensional" array, in row-major order.
   */
protected final int[] array;

public HeightField ( int width, int height, WrapMode wrap ) {
this.width = width;
this.height = height;
this.wrap = wrap;
array = new int[width * height];
}

public int get ( int x, int y ) {
return array [ wrap.index ( x, y, width, height ) ];
}

public void set ( int x, int y, int value ) {
array [ wrap.index ( x, y, width, height ) ] = value;
}

public int getWidth() {
return width;
}

public int getHeight() {
return height;
}

public void writeImage ( String fileName ) throws IOException {
writeImage ( new File ( fileName ) );
}

public void writeImage ( File file ) throws IOException {
BufferedImage img = new BufferedImage (
width,
height,
BufferedImage.TYPE_INT_RGB
);

for ( int y = 0; y < height; ++y ) {
for ( int x = 0; x < width; ++x ) {
int h = clamp ( get(x, y), 0, 255 );
int rgb;
if ( h < 128 ) {
rgb = (h << 16) | (h << 8) | 255;
/*
} else if ( h < 128 ) {
rgb = (h + 30) << 16 | (h + 15) << 8 | h;
} else if ( h < 196 ) {
rgb = (h - 128) << 16 | h << 8;
   */
} else {
rgb = (h << 16) | (h << 8) | h;
}
img.setRGB (
//( x + width / 2 ) % width,
x,
y,
rgb
);
}
}

boolean written = ImageIO.write (
img,
"BMP",
file
);

if ( !written ) {
throw new IOException ( "Failed to write image!" );
}
}

/**
   *
   */
protected void normalize ( int bottom, int top ) {
int min = top, max = bottom;
int range = top-bottom;
for ( int i = 0, j = width * height; i < j; ++i ) {
int h = array[i];
min = Math.min(min, h);
max = Math.max(max, h);
}

// Now we know that the entire heightmap lies in [min,max].
// We re-scale so that min->bottom, max->top
float difference = max - min;
for ( int i = 0, j = width * height; i < j; ++i ) {
int h = array[i];
array[i] = Math.round ( range * ( h - min ) / difference );
}
}

protected static int clamp ( int value, int min, int max ) {
if ( value < min ) {
return min;
}
if ( value > max ) {
return max;
}
return value;
}
}

Main.java, which does the actual midpoint-displacement dance. Note that it will do so 10 times (with different levels of "persistence" between steps). Each one will take a couple of seconds to generate (this code isn't particularly optimized).

Java:

package midpoint;

import java.io.IOException;
import java.text.NumberFormat;
import java.util.Random;
import java.util.Scanner;

import midpoint.HeightField.WrapMode;

public class Main {

public static void main(String[] args) throws IOException {

// Configuration
final int HEIGHT_MAX = 255;
final int L = 512;
final int MX = 2 * L;
final int MY = L;

HeightField hf = new HeightField ( MX, MY, WrapMode.Spherical );

long seed;
Scanner in = new Scanner ( System.in );
System.out.println ( "Enter a seed value (0 to "+Long.MAX_VALUE+")" );
seed = in.nextLong();

NumberFormat nf = NumberFormat.getInstance();
nf.setMaximumFractionDigits(1);
nf.setMinimumFractionDigits(1);

for ( float persist = 0.1f; persist < 1; persist += 0.1f ) {
String persistString = nf.format ( persist );

long start = System.currentTimeMillis();
midpointDisplacement ( hf, L, MX, MY, HEIGHT_MAX, persist, seed );
hf.normalize ( 0, 256 );
hf.writeImage ( "hf_"+persistString+".bmp" );
long end = System.currentTimeMillis();

System.out.println (
"DONE [persist = "+persistString+"] " +
"("+(end-start)+" milliseconds)"
);
}
}

protected static void midpointDisplacement (
final HeightField hf,
final int L,
final int MX,
final int MY,
int range,
final float persist,
final long seed
)
{
/*
   * NOTE:
   * A is (x1, y1)
   * B is (x2, y2)
   * A,B,C,D are the original "corner" points
   *
   * G
   *
   * B D
   *
   * H E I
   *
   * A C
   *
   * F
   */

Random r = new Random(seed);

for ( int y = 0; y < MY; y += L ) {
for ( int x = 0; x < MX; x += L ) {
hf.set ( x, y, r.nextInt ( 256 ) );
}
}

int step = L;
int halfStep = L / 2;
int x2, y2, midx, midy;

while ( step >= 1 ) {
// Diamond step across entire array...
for ( int y1 = 0; y1 < MY; y1 += step ) {
for ( int x1 = 0; x1 < MX; x1 += step ) {
x2 = x1 + step;
y2 = y1 + step;
midx = x1 + halfStep;
midy = y1 + halfStep;

final int sum =
hf.get(x1,y1) + hf.get(x1,y2) +
hf.get(x2,y1) + hf.get(x2,y2);

hf.set (
midx,
midy,
sum / 4 + perturb ( r, range )
);
}
}

// Square step across entire array...
for ( int y1 = 0; y1 < MY; y1 += step ) {
for ( int x1 = 0; x1 < MX; x1 += step ) {
x2 = x1 + step;
y2 = y1 + step;
midx = x1 + halfStep;
midy = y1 + halfStep;

/* x1 mx x2
   * G
   *
   * B 4 D y2
   *
   * H 1 E 2 I midy
   *
   * A 3 C y1
   *
   * F
   */
int A = hf.get ( x1, y1 );
int B = hf.get ( x1, y2 );
int C = hf.get ( x2, y1 );
int D = hf.get ( x2, y2 );
int E = hf.get ( midx, midy );
int F = hf.get ( midx, y1 - halfStep );
int G = hf.get ( midx, y2 + halfStep );
int H = hf.get ( x1 - halfStep, midy );
int I = hf.get ( x2 + halfStep, midy );

hf.set ( x1, midy, (A+B+E+H) / 4 ); // 1
hf.set ( x2, midy, (C+D+E+I) / 4 ); // 2
hf.set ( midx, y1, (A+C+E+F) / 4 ); // 3
hf.set ( midx, y2, (B+D+E+G) / 4 ); // 4
}
}

// Prepare for next iteration...
range *= persist;
step /= 2;
halfStep /= 2;
}
}

protected static int perturb ( Random r, int range ) {
if ( range == 0 ) return 0;
return r.nextInt ( range * 2 ) - range;
}
}

Example image, with persistence = 0.8f .
Posted Image, might have been reduced in size. Click Image to view fullscreen.

Raknarg · **Posted:** Fri Feb 10, 2012 6:10 pm

Ok. So could you give me a quick overview on the logic behind the square and diamond steps? So i can understand it better?

Technically I don't know Java, but I've figured a lot of it out, it'd just help if you did that

mirhagk · **Posted:** Fri Feb 10, 2012 7:25 pm

Very nice terrain generation.

DemonWasp · **Posted:** Sat Feb 11, 2012 9:49 pm

I'm not sure I can explain it any more simply (and certainly not today). Have you tried reading: http://gameprogrammer.com/fractal.html ?

Raknarg · **Posted:** Sun Feb 12, 2012 10:28 am

Yes, I understand that. I get the logic behind the concept, but not necessarily the logic behind how you coded it. There is a difference. Like I kindof see it, but it's not really clear

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members