Diamond Square Algorithm creates diagonal cut

Question

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:

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

I'm not sure about what's the problem. You should try to add the whole code. Something that Im not sure is the size of `startArr` (offset on the calc) and the parameters or the output. could you add the code to: http://ideone.com/ ? — xsami, May 22 '17 at 13:44
Don't undertand what does the block of code from line 11 to 22. Just assigning values to `a, b, c, d, e` — xsami, May 22 '17 at 13:47
The semicolon at the end of the code isn't the issue ? (That shouldn't compile) — xsami, May 22 '17 at 13:50
There are several things going on here. Your algorithm will only work when `x1` and `y1` are zero, otherwise indexing the flat array will not be correct. You should also stop recursig when `level <= 1`; when `level == 1`, you will overwrite the left and top cells. Your first loop, the square, is correct, but the diamond isn't. You need four source cells for the diamond, too, except maybe at the border. Your right and bottom midpoints will be overwritten by subsequent left and top midpoints. — M Oehm, May 22 '17 at 16:59
tale a look at my [Diamond&Square based C++ island generator](https://stackoverflow.com/a/36647622/2521214) — Spektre, May 23 '17 at 05:34
startArr is a 1025×1025 array. I assign a random value between 0 and 1 to each corner. And yes, x1 and y1 are always 0. They'really pretty much redundant variables. — Birkl, May 23 '17 at 06:00
It would really be useful if you showed more code, for example the definition of `startArr`, and how you call your function. Ideally, post a complete small example, maybe only 33x33 or some such. As is, your description of the error is too vague and there are too many things we don't know about your code. — M Oehm, May 23 '17 at 06:44
At the moment, you don't really add offsets via `range`, so your algorithm just interpolates and gives a smooth surface. Instead of making the corner values random, try asigning predefined values like (0, 1, 1, 0) and see how the intrpolation works out. (In thatcase, it should be symmetric, but it isn't.) — M Oehm, May 23 '17 at 06:45

score 0 · Accepted Answer · edited May 23 '17 at 09:07

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

It's good that you have found the error, but it was hard for the community here to find, because you didn't show how the function was called, i.e. what the parameters `x2` and `y2` were, despite being asked for it. (In hindsight, it is obvious from the diagonal thing, but still.) — M Oehm, May 23 '17 at 18:07

Diamond Square Algorithm creates diagonal cut

1 Answers1