I figured out how to implement a midpoint displacement algorithm to generate a map for my game. I wanted to create an infinitely large world, so I tried to patch two maps together, but they didn't look very seamless. I remembered the Diamond-square algorithm...
On the Wikipedia page for the Diamond-square algorithm it says:
When used with consistent initial corner values this method also allows generated fractals to be stitched together without discontinuities
After reading that I decided to convert my midpoint displacement method into what I believe is a proper diamond-square method. However, it still does not look seamless despite me using "consistent initial corner values."
The method works perfectly otherwise.
Here are two generated maps next to each other:
As you can see, there are major discontinuities (even though it looks like they could almost fit together). What I wrote must not be a "true" diamond-square method, or maybe I am misunderstanding the Wikipedia article.
So in other words my question is this: What is wrong with my code or my understanding that prevents me from stitching together maps?
Thanks a lot!
public static float[][] generateMap(int power, float topLeft, float topRight, float bottomLeft, float bottomRight, float error, float persistence, boolean normalize, long seed){
Random random = new Random(seed);
int size = (int)Math.pow(2, power) + 1;
float[][] data = new float[size][size];
// these are for the normalization at the end.
// does it even do anything?
float min = MathHelper.min(topLeft, topRight, bottomLeft, bottomRight);
float max = MathHelper.max(topLeft, topRight, bottomLeft, bottomRight);
// set the corners to the initial values.
data[0][0] = topLeft;
data[size-1][size-1] = bottomRight;
data[0][size-1] = topRight;
data[size-1][0] = bottomLeft;
for (int i = 0; i < power; i++){
int square = size / (int)Math.pow(2, i);
int half = square / 2;
for (int x = 0; x < size - square; x += square){
for (int y = 0; y < size - square; y += square){
// find the values of the corners of the square.
float tl = data[y][x];
float bl = data[y + square][x];
float tr = data[y][x + square];
float br = data[y + square][x + square];
// find the values of the corners of the diamond (if they exist).
Float xt = (y - square - half >= 0) ? data[y-square-half][x+half] : null;
Float xb = (y + square + half < size) ? data[y+square+half][x+half] : null;
Float xl = (x - square - half >= 0) ? data[y+half][x-square-half] : null;
Float xr = (x + square + half < size) ? data[y+half][x+square+half] : null;
// set the square's center to the average of the square's corners plus a random error.
float centerVal = (tl + bl + tr + br) / 4.0f;
centerVal += ((random.nextFloat() * 2) - 1) * error;
data[y+half][x+half] = centerVal;
// set the diamonds' centers to the average of the diamonds' corners (that exist) plus a random error.
float leftVal = (tl + bl + centerVal + (xl != null ? xl : 0)) / (3.0f + (xl != null ? 1.0f : 0.0f));
leftVal += ((random.nextFloat() * 2) - 1) * error;
data[y+half][x] = leftVal;
float rightVal = (tr + br + centerVal + (xr != null ? xr : 0)) / (3.0f + (xr != null ? 1.0f : 0.0f));
rightVal += ((random.nextFloat() * 2) - 1) * error;
data[y+half][x+square] = rightVal;
float topVal = (tl + tr + centerVal + (xt != null ? xt : 0)) / (3.0f + (xt != null ? 1.0f : 0.0f));
topVal += ((random.nextFloat() * 2) - 1) * error;
data[y][x+half] = topVal;
float bottomVal = (bl + br + centerVal + (xb != null ? xb : 0)) / (3.0f + (xb != null ? 1.0f : 0.0f));
bottomVal += ((random.nextFloat() * 2) - 1) * error;
data[y+square][x+half] = bottomVal;
max = MathHelper.max(max, centerVal, leftVal, rightVal, topVal, bottomVal);
min = MathHelper.min(min, centerVal, leftVal, rightVal, topVal, bottomVal);
}
}
// reduce random error.
error *= persistence;
}
// does this even do anything?
if (normalize) {
float div = max - min;
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
data[i][j] /= div;
}
return data;
}