8
\$\begingroup\$

I have implemented a rough interpretation of the Diamond-Square algorithm in C++ to create some semi-realistic fractal terrain, but the output just seems like a random y value at each point rather than smooth rocky shapes. I have altered parameters but feel like an outside look at the code might help me understand the issue. Here are examples of the output:

As a bitmap (top-down) with height variation lowered:

What it should look like (this is loaded from a file):

The code:

//Diamond-square algorithm
HeightMap::HeightMap(float maxY) {
//type = GL_POINTS; 
//type = GL_LINES;
numVertices = RAW_WIDTH*RAW_HEIGHT; //256^2 squares => 257^2 vertices
numIndices = (RAW_WIDTH - 1)*(RAW_HEIGHT - 1) * 6; //each square is 2 triangles (6 indices)
vertices = new Vector3[numVertices];
textureCoords = new Vector2[numVertices];
indices = new GLuint[numIndices];
colours = new Vector4[numVertices];

int cornerA, cornerB, cornerC, cornerD; //Identify corners
cornerA = 0;
cornerB = RAW_WIDTH - 1;
cornerC = RAW_WIDTH*RAW_HEIGHT - RAW_WIDTH;
cornerD = RAW_WIDTH*RAW_HEIGHT - 1;

//Create vertices
for (int x = 0; x < RAW_WIDTH; ++x) {
    for (int z = 0; z < RAW_HEIGHT; ++z) {
        int offset = (x * RAW_WIDTH) + z;
        float y = 0; //Start with vertices set flat
        if (offset == cornerA ||
            offset == cornerB ||
            offset == cornerC ||
            offset == cornerD) {
            vertices[offset] = Vector3(x * HEIGHTMAP_X, maxY/2, z * HEIGHTMAP_Z); //Initialise corners to mid height
            std::cout << "Corners: " << offset << std::endl;
        }

        if (vertices[offset] == Vector3(0, 0, 0)) {
            vertices[offset] = Vector3(x * HEIGHTMAP_X, y * HEIGHTMAP_Y, z * HEIGHTMAP_Z);
        }
        //  textureCoords[offset] = Vector2(x * HEIGHTMAP_TEX_X, z * HEIGHTMAP_TEX_Z);
    }
}

Vector3 tl, tr, bl, br;
tl = vertices[cornerA];
tr = vertices[cornerB];
bl = vertices[cornerC];
br = vertices[cornerD];

float roughness = 1.0f;

Square square = Square(tl, tr, bl, br);
diamondSquare(vertices, numVertices, square, roughness);

//Colour
for (int x = 0; x < RAW_WIDTH; ++x) {
    for (int z = 0; z < RAW_HEIGHT; ++z) {
        int offset = (x*RAW_WIDTH) + z;
        float shade;
        if (vertices[offset].y > 0) {
            shade = 1 - 1.0f / (vertices[offset].y / maxY * 2);
        }
        else {
            shade = 0.1f;
        }
        colours[offset] = Vector4(shade, shade, shade, 1.0f);
        //Colour any vertex that hasn't been passed over red
        if (vertices[offset].y == maxY / 2 + 100) {
            colours[offset] = Vector4(1, 0, 0, 1);
        }
    }
}

//Create indices
numIndices = 0;
for (int x = 0; x < RAW_WIDTH - 1; ++x) {
    for (int z = 0; z < RAW_HEIGHT - 1; ++z) {
        int a = (x*(RAW_WIDTH)) + z;
        int b = ((x + 1)*(RAW_WIDTH)) + z;
        int c = ((x + 1)*(RAW_WIDTH)) + (z + 1);
        int d = (x*(RAW_WIDTH)) + (z + 1);

        indices[numIndices++] = c;
        indices[numIndices++] = b;
        indices[numIndices++] = a;
        indices[numIndices++] = a;
        indices[numIndices++] = d;
        indices[numIndices++] = c;

    }
}
BufferData();

}

void HeightMap::squareStep(Vector3 vertices[], int len, Vector3 tl, Vector3 tr, Vector3 bl, Vector3 br, float mid, float roughness) {
for (int i = 0; i < len; i++) {
    Vector3 top = (tl + tr) / 2;
    Vector3 bot = (bl + br) / 2;
    Vector3 left = (tl + bl) / 2;
    Vector3 right = (tr + br) / 2;
    top.y = 0;
    bot.y = 0;
    left.y = 0;
    right.y = 0;
    if (vertices[i] == top ||
        vertices[i] == bot ||
        vertices[i] == left ||
        vertices[i] == right) {
        float y = rand() % (int)(mid/5);
        y *= roughness;
        vertices[i] = Vector3(vertices[i].x, mid + y, vertices[i].z); //Set Diamond centre points to mid height + rand
        std::cout << "Square: " << vertices[i];
    }
}

}

float HeightMap::diamondStep(Vector3 vertices[], int len, Vector3 tl, Vector3 tr, Vector3 bl, Vector3 br, float roughness) {
float avg;
float y;
    for (int i = 0; i < len; i++) {
        Vector3 corners = (tl + tr + bl + br) / 4;
        avg = corners.y;
        y = rand() % (int)(avg/5);
        y *= roughness;
        corners.y = 0;
        if (vertices[i] == corners) {
            vertices[i] = Vector3(vertices[i].x, avg + y, vertices[i].z);         //Set Square centre point to avg height of corners + rand
            std::cout << "Diamond: " << vertices[i];
        }
    }
return avg + y;

}

void HeightMap::diamondSquare(Vector3 vertices[], int numVertices, Square s, float roughness) {
Vector3 tl = s.tl;
Vector3 tr = s.tr;
Vector3 bl = s.bl;
Vector3 br = s.br;
float mid = diamondStep(vertices, numVertices, tl, tr, bl, br, roughness);
squareStep(vertices, numVertices, tl, tr, bl, br, mid, roughness);
roughness *= 0.75f;
if (s.width > 2 * HEIGHTMAP_X) {
    std::vector<Square> squares = s.split();
    for (int i = 0; i < 4; i++) {
        diamondSquare(vertices, numVertices, squares[i], roughness);
    }
}

}

\$\endgroup\$
  • 1
    \$\begingroup\$ In the method diamondSquare, the diamond-Step and the square-Step seem to operate on the same corners. But actually you are supposed to perform the square-step four times, once for each of the sub-squares generated by the previous diamond-step. And then the square-step should do the same and perform four diamond-steps. But there are quite a lot of other things which smell in that code, like the for-loop in diamondStep which discards and rewrites the return value of the function in every iteration. \$\endgroup\$ – Philipp Apr 27 '16 at 20:29
  • 4
    \$\begingroup\$ When I implemented DS for the first time, I made sure to make the process interactive so I could see exactly what was happening at each step, starting with the four corners of the entire space and working its way through each subsequent iteration. Modify data, modify vertices accordingly, rinse, repeat. I suggest you do this, as recursive algorithms can otherwise be difficult to keep track of. \$\endgroup\$ – Engineer Apr 27 '16 at 20:33
  • \$\begingroup\$ How did you decide to decrease the step size by roughness *= 0.75f;? \$\endgroup\$ – Roflo Apr 27 '16 at 20:57
  • \$\begingroup\$ I need to correct my previous comment: You are only supposed to perform one diamond-step for each square-step, not four. But you are still supposed to perform four square-steps after each diamond-step. I would expect a proper implementation to have diamondStep call squareStep and then squareStep call diamondStep until the desired iteration depth is reached. \$\endgroup\$ – Philipp Apr 27 '16 at 21:12
1
\$\begingroup\$

I think usually you would include the height of the middle point in the square step (and do the diamond step first. which) would slightly affect how spiky it looks making it a more gradual slope. Did you try it with the random offset decreased?

It also seems that as long as the heights are positive there is no chance for the height offset to be negative so the higher the points, the higher the offset making it more spiky.

I made a fairly simple program with this algoritihm giving okay results and instead of basing the random offset off the average of the heights, I made it affected by the current gridwidth.

\$\endgroup\$
-3
\$\begingroup\$

To Fix height randomness you can implement Perlin Noise.

Which generating height based on the adjecent heights and thus you got very smooth results.

Here is some Implementation on C++

\$\endgroup\$
  • 2
    \$\begingroup\$ This is not an answer to the question \$\endgroup\$ – Bálint Apr 24 '17 at 10:47
  • 1
    \$\begingroup\$ Welcome to gamedev.SE. Please note that this is a question&answer community. We only answer questions as they were written. This question is explicitly asking about a problem with implementing the diamond-square algorithm. "Use a completely different algorithm" is not a good answer to such a question. \$\endgroup\$ – Philipp Apr 24 '17 at 13:25
  • 1
    \$\begingroup\$ Diamond Square algorithm and Perlin Noise are two different algorithms for generating coherent noise. You wouldn't use one to create the other. \$\endgroup\$ – MichaelHouse Apr 24 '17 at 18:08

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.