C++ - Diamond-Square algorithm output is random and noisy

Question

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:

I got this:

And should look like this:

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);
    }
}

}

Answer 1

Your midpoint calculations look wrong. The algorithm should sets the midpoint of that square or diamond to be the average of the four corner points plus a random value. But in your code I see this:

y = rand() % (int)(avg/5);

This basically says, set y to a random number between zero & one fifth of the average of the corners. Instead I would expect to see something like this:

// get a random float in the range 0 to 1
float r = (float)(rand()) / (float)(RAND_MAX);
// scale r to be in the range -magnitude to magnitude
r = (r * 2 * magnitude) - magnitude;
// add the scaled random value to the average of the corners
y = avg + r;

Note: it's possible that this approach will give you y values less than zero. If that's a problem, normalize the data by finding the lowest value & subtracting that amount from each y.