Search code examples
c++algorithmgame-engineterrain

Diamond Square Algorithm creates diagonal cut

I got a little problem with something I'm currently working on in my freetime: I wanted to create a heightmap in c++ via the DSA. But it's not working as I planned. My code is (please ignore the two character comments): 

void DiamondSquareAlgorithm(int x1, int y1, int x2, int y2, float range, unsigned level)
{
    //level = size - 1 when called the first time

    if (level < 1) return;
    float a;
    float b;
    float c;
    float d;
    float e;
    for (int i = x1; i < x2; i += level)
    {
        for (int j = y1; j < y2; j += level)
        {
            //diamond
            a = startArr[i + j * (x2 - x1 + 1)]; //lo
            b = startArr[(i + level) + j * (x2 - x1 + 1)]; //ro
            c = startArr[i + (j + level) * (x2 - x1 + 1)]; //lu
            d = startArr[(i + level) + (j + level) * (x2 - x1 + 1)]; //ru
            e = startArr[(i + level / 2) + (j + level / 2) * (x2 - x1 + 1)] = (a + b + c + d) / 4;
        }
    }

    for (int i = x1; i < x2; i += level)
    {
        for (int j = y1; j < y2; j += level)
        {
            a = startArr[i + j * (x2 - x1 + 1)]; //lo
            b = startArr[(i + level) + j * (x2 - x1 + 1)]; //ro
            c = startArr[i + (j + level) * (x2 - x1 + 1)]; //lu
            d = startArr[(i + level) + (j + level) * (x2 - x1 + 1)]; //ru
            e = startArr[(i + level / 2) + (j + level / 2) * (x2 - x1 + 1)] = (a + b + c + d) / 4;

            //square
            startArr[(i + level / 2) + j * (x2 - x1 + 1)] = (a + b + e) / 3; //o
            startArr[(i + level) + (j + level / 2) * (x2 - x1 + 1)] = (b + d + e) / 3; //r
            startArr[(i + level / 2) + (j + level) * (x2 - x1 + 1)] = (d + c + e) / 3; //u
            startArr[i + (j + level / 2) * (x2 - x1 + 1)] = (a + c + e) / 3; //l
        }
    }
    DiamondSquareAlgorithm(x1, y1, x2, y2, range / 2, (level / 2));
};

The result is always something along the lines of this:

Terrain

Can someone please help me find the obviously critical mistake I made in my code?

Solution

  • I finally found the problem with my code. Most of the stuff above is correct except for one minor thing: it should not be (x2 - x1 + 1). This moves every value one space further in the array. This happens every step and so this diagonal line appears; The correct and working code is

    void DiamondSquareAlgorithm(int x1, int y1, int x2, int y2, float range, unsigned level)
{
    //level = size - 1 when called the first time
    if (level <= 1) return;
    float a;
    float b;
    float c;
    float d;
    float e;
    int width = x2 - x1;
    for (int y = x1; y < x2; y += level)
    {
        for (int x = y1; x < y2; x += level)
        {
            //diamond
            a = startArr[x + y * width]; //lo
            b = startArr[(x + level) + y * width]; //ro
            c = startArr[x + (y + level) * width]; //lu
            d = startArr[(x + level) + (y + level) * width]; //ru
            e = startArr[(x + level / 2) + (y + level / 2) * width] = Fit(((a + b + c + d) / 4) + Random(-1, 1) * range);
        }
    }
    for (int y = x1; y < x2; y += level)
    {
        for (int x = y1; x < y2; x += level)
        {
            a = startArr[x + y * width]; //lo
            b = startArr[(x + level) + y * width]; //ro
            c = startArr[x + (y + level) * width]; //lu
            d = startArr[(x + level) + (y + level) * width]; //ru
            e = startArr[(x + level / 2) + (y + level / 2) * width];

            //square
            startArr[(x + level / 2) + y * width] = Fit(((a + b + e) / 3) + Random(-0.5, 0.5) * range); //o
            startArr[(x + level) + (y + level / 2) * width] = Fit(((b + d + e) / 3) + Random(-0.5, 0.5) * range); //r
            startArr[(x + level / 2) + (y + level) * width] = Fit(((d + c + e) / 3) + Random(-0.5, 0.5) * range); //u
            startArr[x + (y + level / 2) * width] = Fit(((a + c + e) / 3) + Random(-0.5, 0.5) * range); //l
        }
    }
    DiamondSquareAlgorithm(x1, y1, x2, y2, range / 2, (level / 2));
};

    float Fit(float x) is a method that takes a float and compares it to 0 and 1 so there are no values larger than 1 and no values smaller than 0; float Random(float a, float b) simply gives you a random float between two floats. heightfield