Why doesn't my gradient noise generator work?

Question

I tried to make a program that generates gradient noise for terrain generation. It's supposed to print array of numbers between 40 and 99 but it stops on this part:

    for(int k=16; k>1; k/=2)
        for(int y=Y; y<Y+16; y+=k+1)
            for(int x=X; x<X+16; x+=k+1)
            {
                tab[y+k/2][x]=rand()%(max(tab[y][x],tab[y+16][x])-min(tab[y][x],tab[y+16][x]))+min(tab[y][x],tab[y+16][x]);
                tab[y][x+k/2]=rand()%(max(tab[y][x],tab[y][x+16])-min(tab[y][x],tab[y][x+16]))+min(tab[y][x],tab[y][x+16]);
                tab[y+k/2][x+k/2]=rand()%(max(tab[y][x],tab[y+16][x+16])-min(tab[y][x],tab[y+16][x+16]))+min(tab[y][x],tab[y+16][x+16]);
            }

When I remove content of the loop it doesn't stop. It compiles well but returns -1 (0xFFFFFFFF)

Here is whole code:

#include<ctime>
#include<iostream>
using namespace std;
const short int Size=8;
short int tab[Size*16+1][Size*16+1];
void chunk(int X, int Y)
{
    srand(time(NULL));
    for(int k=16; k>1; k/=2)
        for(int y=Y; y<Y+16; y+=k+1)
            for(int x=X; x<X+16; x+=k+1)
            {
                tab[y+k/2][x]=rand()%(max(tab[y][x],tab[y+16][x])-min(tab[y][x],tab[y+16][x]))+min(tab[y][x],tab[y+16][x]);
                tab[y][x+k/2]=rand()%(max(tab[y][x],tab[y][x+16])-min(tab[y][x],tab[y][x+16]))+min(tab[y][x],tab[y][x+16]);
                tab[y+k/2][x+k/2]=rand()%(max(tab[y][x],tab[y+16][x+16])-min(tab[y][x],tab[y+16][x+16]))+min(tab[y][x],tab[y+16][x+16]);
            }
}
int main()
{
    srand(time(NULL));
    for(int i=0; i<Size; i+=16)
        for(int j=0; j<Size; j+=16)
            tab[16*i][16*j]=rand()%(100-40)+40;
    for(int x=0; x<Size*16+1; x+=16)
        for(int y=0; y<Size*16+1; y+=16)
            chunk(x,y);

    return 0;
}

Edit: It didn't work because of

rand()%(max(tab[y][x],tab[y+16][x])-min(tab[y][x],tab[y+16][x]))

elements in array could be equal. I also did some stupid mistakes while reading array which led to exceeding it's size. Now it runs without errors but shows some numbers below 40 which is't supposed to happen. Here is code after edits:

#include<ctime>
#include<iostream>
using namespace std;
const short int Size=1;
short int tab[Size*16+1][Size*16+1];
void chunk(int X, int Y)
{
    for(int k=16; k>1; k/=2)
        for(int y=Y; y<Y+16; y+=k)
            for(int x=X; x<X+16; x+=k)
            {
                if(Y!=Size*16)
                    if(tab[y][x]==tab[y+k][x])
                        tab[y+k/2][x]=tab[y][x];
                    else
                        tab[y+k/2][x]=rand()%(max(tab[y][x],tab[y+k][x])-min(tab[y][x],tab[y+k][x]))+min(tab[y][x],tab[y+k][x]);
                if(X!=Size*16)
                    if(tab[y][x]==tab[y][x+k])
                        tab[y+k/2][x]=tab[y][x];
                    else
                        tab[y][x+k/2]=rand()%(max(tab[y][x],tab[y][x+k])-min(tab[y][x],tab[y][x+k]))+min(tab[y][x],tab[y][x+k]);
                if(X!=Size*16||Y!=Size*16)
                if(tab[y][x]==tab[y+k][x+k])
                    tab[y+k/2][x]=tab[y][x];
                else
                    tab[y+k/2][x+k/2]=rand()%(max(tab[y][x],tab[y+k][x+k])-min(tab[y][x],tab[y+k][x+k]))+min(tab[y][x],tab[y+k][x+k]);
            }
}
int main()
{
    srand(time(NULL));
    for(int i=0; i<=Size*16; i+=16)
        for(int j=0; j<=Size*16; j+=16)
            tab[j][i]=rand()%60+40;
    for(int x=0; x<=Size*16; x+=16)
        for(int y=0; y<=Size*16; y+=16)
            chunk(x,y);

    for(int a=0; a<Size*16; a++){
        for(int b=0; b<Size*16; b++)
        {
            cout<<tab[b][a]<<' ';
            if(tab[b][a]<10)
                cout<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

edit 2: Algorithm writes pseudo-random value between two chosen values every 16 rows and columns into the array. Then it jumps every 16 cells to put a pseudo-random value between cells which are already filled like this:

XOOOOOOO+OOOOOOF
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
+OOOOOOO+OOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOO
FOOOOOOOOOOOOOOF

X - cell that's being checked F - filled cells + - cells to fill 0 - empty cells Algorithm fills "+" cells with pseudo-random value between values of "X" cell and "F" cell. When algorithm jumps over all "F" cells it goes again with jump half as long as before, and existing "+" cells become "F" cells. It continues until jump length is equal 1, which means array is full.

Relevant question : [srand() — why call it only once?](https://stackoverflow.com/questions/7343833/srand-why-call-it-only-once). Because `srand` appears in your function, when you call your function in a loop, it's likely each call of the functions will generate the exact same result as they will likely be executed during the same unit of time as returned by `time(NULL)`. — François Andrieux, May 04 '20 at 17:38
Your `tab` initialization is broken. `Size` is 8 but you increment your loop variables by 16, so the loops will always execute exactly once with `i` and `j` equal to zero. I'm not sure why you then multiple `i` and `j` by 16 to access the table elements, but it looks awfully like you forgot you already increment your iteration variables by 16. Edit : You probably hit a division by zero by reading from an improperly initialized `tab`. — François Andrieux, May 04 '20 at 17:42
Thanks for including a program to reproduce the problem. When I run your code I get at error `Program received signal SIGFPE, Arithmetic exception.` Is this what you mean by your program "stopping"? Did you try using a debugger? gdb shows the error occurring on line 13: `tab[y+k/2][x]=rand()%(max(tab[y][x],tab[y+16][x])-min(tab[y][x],tab[y+16][x]))+min(tab[y][x],tab[y+16][x]);` — pcarter, May 04 '20 at 17:42
It appears that in line 13, it's doing a rand()%(0) which would cause the error. — pcarter, May 04 '20 at 17:51
Can you please edit your question adding a simple explanation (in english, rather than pseudo-code) of what the algorithm is supposed to do? — Bob__, May 04 '20 at 20:09

score 0 · Answer 1 · answered May 04 '20 at 17:53

Looks like you are blowing out your arrays. at some point you call chunk with a value of X that is Size*16

then in the subroutine you have little x (btw differentiating variable by just capitalization makes code hard to read) going up to X+16 so just doing tab[x, ...] will blow out your array and you have tab[x+16,...]

Bob__ · Answer 2 · 2020-05-05T00:32:29.043

The biggest problem is in the indices calculation, which causes access out of the bounds of the array.

In the following snippet I'll show a possible implementation of the algorithm, assuming that I've understood the question.

#include <algorithm>
#include <array>
#include <iostream>
#include <iomanip>
#include <random>  // <- I won't use srand / rand

/*  Example of fill sequence (in 1D)
                                     start   step
1---------------1---------------1      0      16
1-------2-------1-------2-------1      8      16
1---3---2---3---1---3---2---3---1      4       8
1-4-3-4-2-4-3-4-1-4-3-4-2-4-3-4-1      2       4
154535452545354515453545254535451      1       2

1     <-2->    1     Dependencies 

^     \   /
2       2 
v     /   \

1              1

*/

template <class Gen>
int rand_between(int a, int b, Gen& gen)
{
    if (b < a)
        std::swap(a, b);
    std::uniform_int_distribution dist(a, b);
    return dist(gen);
}

template <class Gen>
int rand_between(int a, int b, int c, int d, Gen& gen)
{
    auto e = std::minmax({a, b, c, d});
    std::uniform_int_distribution dist(e.first, e.second);
    return dist(gen);
}

int main()
{
    std::random_device rd;
    std::seed_seq ss{rd(), rd(), rd()};
    std::mt19937 gen{ss};

    constexpr size_t first_step{ 16 };
    constexpr size_t repetitions{ 2 };
    constexpr size_t size{ first_step * repetitions + 1 };

    std::array<std::array<int, size>, size> m{};

    // First fill
    std::uniform_int_distribution dist(40, 99);
    for (size_t i{0}; i < size; i += first_step)
    {
        for (size_t j{0}; j < size; j += first_step)
        {
            m[i][j] = dist(gen);
        }
    }

    // Inner filling
    size_t half_step{ first_step / 2 };
    size_t step{ first_step };
    while (half_step > 0)
    {
        for (size_t i{0}; i < size; i += step)
        {
            for (size_t j{half_step}; j < size; j += step)
            {
                m[i][j] = rand_between(m[i][j - half_step], m[i][j + half_step], gen);
            }
            if (size <= i + half_step)
                break;
            for (size_t j{0}; j < size; j += step)
            {
                m[i + half_step][j] = rand_between(m[i][j], m[i + step][j], gen);
                if (j + step < size)
                {
                    m[i + half_step][j + half_step] = rand_between(
                        m[i][j], m[i + step][j], m[i][j + step], m[i + step][j + step], gen
                    );
                }
            }
        }
        step = half_step;
        half_step /= 2;
    }

    for (size_t i{0}; i < size; ++i)
    {
        for (size_t j{0}; j < size; ++j)
        {
            std::cout << std::setw(3) << m[i][j];
        }
        std::cout << '\n';
    }
}

Testable here;

Why doesn't my gradient noise generator work?

2 Answers2