7
\$\begingroup\$

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: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;

}

\$\endgroup\$
  • 3
    \$\begingroup\$ If you're willing to change algorithms once more, sampling from a noise function like Perlin Noise will not have this problem. \$\endgroup\$ – Chaosed0 Oct 20 '15 at 13:52
  • \$\begingroup\$ @Chaosed0 Not to mention it generally looks better, and gives you more control over the result by weighting the relative contributions from multiple frequencies. \$\endgroup\$ – bcrist Feb 5 '16 at 2:47
6
\$\begingroup\$

Before Diamond-Square begins, you'll have to make sure the outermost boundaries (and the maximum number of potential midpoints generated therein) are set equal on either side of the map (in x and y). Only then can you begin full generation of the centre with something approaching a seamless wrap. What they meant by "consistent" is "all outermost corners and edges need the same values", because when wrapping, they are all, in essence, the same point (origin). Set initial corners to zero, then elaborate the left edge using 1D midpoint displacement, copy that to the right edge, then do same with top and bottom (by the end, the corners must still all be zero, but those between can be anything). Alternatively, you can just set all boundary points to zero. Now you have the map "frame", so when running Diamond-Square, don't touch boundary points - just use them.

I say approaching because mind you, this may still not lead to a desirable result (depending on your point of view), since the operation of the Diamond-Square algorithm does not, by default, handle the concept of continuity across wrap boundaries. So it looks somewhat contrived, IIRC. If this is a problem, either find a way to do some sort of smoothing across boundaries, perhaps by picking random local maxima / minima on either side of the boundary and expanding these across the boundary, or look at other algorithms for your terrain generation... or lose the wrap requirement.

\$\endgroup\$
1
\$\begingroup\$

In my own bit of code (just to learn procedural terrain generation), instead of trying to stitch together two maps (eg. two 64x64 maps), I create one larger map (eg. 128x128, which wraps), and then throw away the bottom portion. This leaves me with a 64x128 map that wraps horizontally but not vertically (which is what I want).

\$\endgroup\$
1
\$\begingroup\$

I've thought about this, that is, creating matching heightmaps using diamond-square. I don't know how well this will work, as I've never tried implementing it, but here's my theoretical postulation:

For every point along an edge, if the adjacent map portion exists, make the point equal to the adjacent edge point.

What it looks like right now is that you're only setting the corners to the adjacent map's corners, but not following through for the other points. Because every other point is random, the rest of the edge is not guaranteed to line up. But if you were to insert an additional check that says, "am I an edge? ok, does an adjacent edge on another map portion exist? ok, it does, I am now that value instead of this random one" you should be able to get it to line up exactly.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.