-----------------------------------

Raknarg

Tue Feb 07, 2012 6:57 pm


Square Diamond Fractal Maps

-----------------------------------

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

Wed Feb 08, 2012 7:20 am


Re: Square Diamond Fractal Maps

-----------------------------------

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
[/code]

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)
[/code]

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

Wed Feb 08, 2012 12:41 pm


RE:Square Diamond Fractal Maps

-----------------------------------

Can you pm me?


-----------------------------------

DemonWasp

Fri Feb 10, 2012 11:08 am


RE:Square Diamond Fractal Maps

-----------------------------------

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


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

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

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

Example image, with persistence = 0.8f .
http://i.imgur.com/KWoyu.jpg


-----------------------------------

Raknarg

Fri Feb 10, 2012 6:10 pm


RE:Square Diamond Fractal Maps

-----------------------------------

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

Fri Feb 10, 2012 7:25 pm


RE:Square Diamond Fractal Maps

-----------------------------------

Very nice terrain generation.


-----------------------------------

DemonWasp

Sat Feb 11, 2012 9:49 pm


RE:Square Diamond Fractal Maps

-----------------------------------

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

Sun Feb 12, 2012 10:28 am


RE:Square Diamond Fractal Maps

-----------------------------------

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