Diamond Square Terrain Generation for large areas

Question

I'm trying to implement the diamond-square terrain generation algorithm in OpenGL.

So far I have a 2D plane (actually a 3D but all Z coordinates are set to 0) made of up to 1024 different squares. The coordinates are organised into 2-dimensional arrays

• Array for x-coordinates: xMap[1024][1024]
• Array for y-coordinates: yMap[1024][1024]
• Array for z-coordinates: zMap[1024][1024] (all = 0 at start; assuming incorrectly for the purpose of the experiment that z is the "vertical" axis in our case)

We have for instance:

Point1 (xMap[1][1], yMap[1][1], zMap[1][1]);

I'm using the following code to generate terrain. The problem I'm having is that while it works as expected on maps as big as 4 X 4 points, it does not work on anything larger. When applied to a 6 X 6 map it will generate the terrain accordingly for the 4 X 4, but will leave the added 2 squares untouched.

This is the code I'm using for generating the terrain:

   void generateLandscapeRec(int xMin, int xMax, int yMin, int yMax, float disp) {

    float nDisp = (float)(disp * (float)pow(2, -(double)roughnes)); // New displacement

    int xMidpnt = (xMin + xMax) / 2;
    int yMidpnt = (yMin + yMax) / 2;

    GLfloat A = zMap[xMin][yMin];
    GLfloat B = zMap[xMax][yMin];
    GLfloat C = zMap[xMin][yMax];
    GLfloat D = zMap[xMax][yMax];

    GLfloat E = (A + B + C + D) / 4 + randDisp(disp); // Midpoint height

    zMap[xMidpnt][yMidpnt] = E; // Set E

    zMap[xMin][yMidpnt] = (A + C + E) / 3 + randDisp(disp);  // F
    zMap[xMidpnt][yMin] = (A + B + E) / 3 + randDisp(disp);  // G
    zMap[xMax][yMidpnt] = (B + D + E) / 3 + randDisp(disp);  // H
    zMap[xMidpnt][yMax] = (C + D + E) / 3 + randDisp(disp);  // I

    if ((xMidpnt - xMin) > 1) { // Subdivide if new midpoint length will be > 1

        generateLandscapeRec(xMin, xMidpnt, yMin, yMidpnt, nDisp);
        generateLandscapeRec(xMidpnt, xMax, yMin, yMidpnt, nDisp);
        generateLandscapeRec(xMin, xMidpnt, yMidpnt, yMax, nDisp);
        generateLandscapeRec(xMidpnt, xMax, yMidpnt, yMax, nDisp);
    }
}

The problem might either be with the algorithm or with the way I'm choosing my points.

Any thoughts and/or help?

Answer 1

I guess you are running into rounding errors. Checking xMidPnt vs. xMin only for recursion will not work if you are using non-power-of-two ranges (like 6x6) and will also not work if your y-range is larger than your x-range. You'll want to use 4 conditions instead, one for each quarter.

if ((xMidpnt - xMin) > 1) || (yMidpnt - yMin > 1))
    generateLandscapeRec(xMin, xMidpnt, yMin, yMidpnt, nDisp);
if ((xMidpnt - xMin) > 1) || (yMax - yMidpnt > 1))
    gnerateLandscapeRec(xMin, xMidpnt, yMidpnt, yMax, nDisp);
...