# Implementing the midpoint displacement algorithm in Java

Thanks for taking the time to read this first off. I want to say that I have always been very interested in generating random terrain and since I'm new to any sort of graphical programming, I decided to start as simple as I could get.

I am trying to implement the midpoint displacement algorithm to make fractal type mountains. I've read the most common resources on it and understand the concept but that hasn't made it any easier. I suppose I have some more general questions about how I would store data effectively, but this is the code I have come up with. The code is pretty awful but it produces numbers and I've tried to make lines with the different points in openGL but I'm getting some pretty crazy results. I'm using the idea discussed on the start of this page. http://www.gameprogrammer.com/fractal.html

import java.util.Random;

public class MidPointGenerator {

private static double[] heightmap;
private static double randrange;
private static int iterations;
private static double roughness;
private static int n;

public MidPointGenerator(double s, int i, double h){
n = (int)(Math.pow(2, i) + 1); // size of the array
heightmap = new double[(int)n];
randrange = s;
iterations = i;
roughness = Math.pow(2,-h);
midPoint(0, n-1, randrange,0,i);
}

public static void midPoint(int left, int right, double range, int i, int goal){

if(i == goal){
return;
}

int mp = (left + right) / 2;
double mpheight;

if(heightmap[left] < heightmap[right]){
mpheight = ((heightmap[right] - heightmap[left]) / 2.0) + heightmap[left];
heightmap[mp] = mpheight + random(range);
}
if(heightmap[right] < heightmap[left]){
mpheight = ((heightmap[left] - heightmap[right]) / 2.0) + heightmap[right];
heightmap[mp] = mpheight + random(range);
}
if(heightmap[right] == heightmap[left]){
heightmap[mp] += random(range);

midPoint(left, mp, range * roughness, i+1, goal);
midPoint(mp, right, range * roughness, i+1, goal);

}

public static double random(double range){
//Returns a random number from -s to s.
Random random = new Random();
double randNum =  range - ((2*range) * random.nextDouble());
return randNum;
}

public static void displayHeights(){
for(int i = 0; i < heightmap.length; i++){
System.out.println(heightmap[i]);
}
}

public double getHeightValue(int index){
if(index == n ){
return 0;
}
return heightmap[index];
}

public int getIterations(){
return n;
}

}


So this at least runs, stores the height values in a 1D array thats size depends on the number of iterations I want to do. How can I make my code much more logical and perhaps there is a much better way of implementing this. I was more concerned about just getting something that compiled and ran successfully. I'm convinced the way I'm approaching this is flawed and there is a much better way.

Any criticism is welcomed! Thanks, Ryan

-

.... Hrm...

import java.util.Random;


I'm assuming this is sufficient for your needs. In the future, it may be preferable to create your own interface, that you can supply different implementations for.

public class MidPointGenerator {

private static double[] heightmap;
private static double randrange;
private static int iterations;
private static double roughness;
private static int n;


What does n represent? Most of the other variables are named okay (although randrange should probably be deviation, or similar).
Mutable class-level variables should (almost always) die. Especially since:

public MidPointGenerator(double s, int i, double h){
n = (int)(Math.pow(2, i) + 1); // size of the array
heightmap = new double[(int)n];
randrange = s;
iterations = i;
roughness = Math.pow(2,-h);
midPoint(0, n-1, randrange,0,i);
}


You set them in the instance constructor! So, they're really instance variables! If I were attempting to use your class, I might end up mighty confused as to behavior, when attempting to use two different instances. Also, your parameter names are terrible - they don't tell me at all what they're used for. And don't use end-of-line comments.

public static void midPoint(int left, int right, double range, int i, int goal){

if(i == goal){
return;
}


What does i represent? The only time such short variables are ever really acceptable is as indices during iterators (maybe). This method is static because it's operating on class-level variables (which should be instance-level), but there's no good reason for it to be flagged public as well.

    int mp = (left + right) / 2;
double mpheight;

if(heightmap[left] < heightmap[right]){
mpheight = ((heightmap[right] - heightmap[left]) / 2.0) + heightmap[left];
heightmap[mp] = mpheight + random(range);
}
if(heightmap[right] < heightmap[left]){
mpheight = ((heightmap[left] - heightmap[right]) / 2.0) + heightmap[right];
heightmap[mp] = mpheight + random(range);
}
if(heightmap[right] == heightmap[left]){
heightmap[mp] += random(range);

}  // <- Missing?


I'm assuming, given other indentation, that the brace (}) belongs here. Compiler error otherwise.

    midPoint(left, mp, range * roughness, i+1, goal);
midPoint(mp, right, range * roughness, i+1, goal);

}

public static double random(double range){
//Returns a random number from -s to s.
Random random = new Random();


You're creating a new Random object each time you enter this object (and not using the variable you created earlier...). Depending on how your program runs, you may have multiple instances of Random with the same seed value, causing them to generate the same output; while occasionally random generators should return the same output, getting them in this fashion is undesirable. Same comments about public and static.

    double randNum =  range - ((2*range) * random.nextDouble());
return randNum;
}


random.nextDouble() returns an evenly distributed value in the range [0, 1). The result of the math, though, is not evenly distributed along (-range, range); at least, I don't think so (anybody else know better? help?). You can generate double-ended integer ranges (with Random.nextInteger(upper)), which doesn't really help here. You may need a new random generator, if you're going to get 'correct' results - what you have may be good enough for your current purposes.

public static void displayHeights(){
for(int i = 0; i < heightmap.length; i++){
System.out.println(heightmap[i]);
}
}


Same comments about public and static. Really, you should be using a for-each loop. Oh, and not printing out to the console directly, but that's probably forgivable here.

public double getHeightValue(int index){
if(index == n ){
return 0;
}
return heightmap[index];
}

public int getIterations(){
return n;
}


I'm assuming that these methods are for whatever needs to inspect the state of the map after you're done constructing it (hence the public), given it's not used anywhere in your code. You really ought to be returning some sort of array/collection, though (probably a copy of heightmap), which should be easier to work with.

Ah, I think this is more along the lines of how I would have done it:

public class MidPoint {

private static final Random RANDOM = new Random();

private final double[] heightmap;

private MidPoint(double[] heightmap) {
this.heightmap = heightmap;
}

private double[] getHeightmap() {
return Arrays.copyOf(heightmap, heightmap.length);
}
}


This is the basic class definition (static creation methods in a second). Because the class now represents the end state, I felt it was appropriate to change the name. The constructor is private, because it doesn't make much sense for it to be manually created. And the end heightmap should be accessed as a copy, so that the result can be safely shared. It's also being output as the array, not as by-index, which you may find easier to work with.

private static double random(double range) {
return range - ((2 * range) * RANDOM.nextDouble());
}


I just tightened this up a little, was all. It might not be 'perfect', but I personally don't know of a better way to set this up, if the variation is an issue. Actually, this method makes (temporary) testing really easy - just have it return a constant value!

private static double getMidpoint(double a, double b) {
return ((a - b) / 2) + b;
}


Helper method, to remove code duplication.

private static double getOffset(double current, double left, double right) {
final int comparison = Double.compare(left, right);

if (comparison < 0) {
return getMidpoint(left, right);
} else if (comparison > 0) {
return getMidpoint(right, left);
} else {
return current;
}
}


... Mathematically speaking, the greater/less than shouldn't be necessary (because the midpoint calculation gives correct results either way). The problem comes in that the way doubles (and limited-precision numbers of all types) are represented won't necessarily always give the same results.

private static void midPoint(double[] heightmap, int iteration, int limit, int left, int right, double range, double deviation) {
if (iteration == limit) {
return;
}

final int midpoint = ((right - left) / 2) + left;

heightmap[midpoint] = (getOffset(heightmap[midpoint], heightmap[left], heightmap[right]) + random(range));

final double adjusted = range * deviation;

midPoint(heightmap, iteration + 1, limit, left, midpoint, adjusted, deviation);
midPoint(heightmap, iteration + 1, limit, midpoint, right, adjusted, deviation);
}


Recursive method. Things have mostly just been extracted to helper methods. The only big difference is the way the midpoint is retrieved, which was changed so that with larger iterations (because of the squaring from iterations) they won't overflow.

private static double[] getMidPoints(final int iterations, final double range, final double roughness) {
final double[] heightmap = new double[(int) Math.pow(2, iterations) + 1];
final double deviation = Math.pow(2.0, roughness);

midPoint(heightmap, 0, iterations, 0, heightmap.length - 1, range, deviation);

return heightmap;
}


Setup for entire process, returning the finished array.

public static MidPoint generate(final int iterations, final double range, final double roughness) {

if (iterations >= 31) {
throw new IllegalArgumentException("Too many iterations, must be 30 or less");
}

if (Double.isNaN(range) || Double.isInfinite(range) || !(range > 0.0)) {
throw new IllegalArgumentException("Range must be a positive value greater than 0");
}

if (Double.isNaN(roughness) || Double.isInfinite(roughness) || !(roughness > 0.0)) {
throw new IllegalArgumentException("Roughness must be a positive value greater than 0");
}

return new MidPoint(getMidPoints(iterations, range, roughness));
}


And... The static generator method, returning the final value object. The biggest thing here was the error checking.

Oh, the results always have 0.0 at the start and end of the set of midpoints, which makes me think something is up, but I have no idea what. Unfortunately, I don't know what you're trying to implement, so I can't tell if something is wrong. And no, it's not something I introduced - yours gets that too (constant values for the random get the same results).

-