Algorithm for visiting all grid cells in pseudo-random order that has a guaranteed uniformity at any stage

Question

Context:

I have a hydraulic erosion algorithm that needs to receive an array of droplet starting positions. I also already have a pattern replicating algorithm, so I only need a good pattern to replicate.

The Requirements:

I need an algorism that produces a set of n^2 entries in a set of format (x,y) or [index] that describe cells in an nxn grid (where n = 2^i where i is any positive integer).

(as a set it means that every cell is mentioned in exactly one entry)
The pattern [created by the algorism ] should contain zero to none clustering of "visited" cells at any stage.
The cell (0,0) is as close to (n-1,n-1) as to (1,1), this relates to the definition of clustering

Note I was/am trying to find solutions through fractal-like patterns built through recursion, but at the time of writing this, my solution is a lookup table of a checkerboard pattern(list of black cells + list of white cells) (which is bad, but yields fewer artifacts than an ordered list)

C, C++, C#, Java implementations (if any) are preferred

Daniel B · Accepted Answer

I have solved the problem myself and just sharing my solution:

here are my outputs for the i between 0 and 3:

power: 0
ordering:
0
matrix visit order:
0

power: 1
ordering:
0 3 2 1
matrix visit order:
0       3
2       1

power: 2
ordering:
0 10 8 2 5 15 13 7 4 14 12 6 1 11 9 3
matrix visit order:
0       12      3       15
8       4       11      7
2       14      1       13
10      6       9       5

power: 3
ordering:
0 36 32 4 18 54 50 22 16 52 48 20 2 38 34 6
9 45 41 13 27 63 59 31 25 61 57 29 11 47 43 15
8 44 40 12 26 62 58 30 24 60 56 28 10 46 42 14
1 37 33 5 19 55 51 23 17 53 49 21 3 39 35 7
matrix visit order:
0       48      12      60      3       51      15      63
32      16      44      28      35      19      47      31
8       56      4       52      11      59      7       55
40      24      36      20      43      27      39      23
2       50      14      62      1       49      13      61
34      18      46      30      33      17      45      29
10      58      6       54      9       57      5       53
42      26      38      22      41      25      37      21

the code:

public static int[] GetPattern(int power, int maxReturnSize = int.MaxValue)
{
    int sideLength = 1 << power;
    int cellsNumber = sideLength * sideLength;
    int[] ret = new int[cellsNumber];
    for ( int i = 0 ; i < cellsNumber && i < maxReturnSize ; i++ ) {
        // this loop's body can be used for per-request computation
        int x = 0;
        int y = 0;
        for ( int p = power - 1 ; p >= 0 ; p-- ) {
            int temp = (i >> (p * 2)) % 4; //2 bits of the index starting from the begining
            int a = temp % 2; // the first bit
            int b = temp >> 1; // the second bit
            x += a << power - 1 - p;
            y += (a ^ b) << power - 1 - p;// ^ is XOR
            // 00=>(0,0), 01 =>(1,1) 10 =>(0,1) 11 =>(1,0) scaled to 2^p where 0<=p 
        }
        //to index
        int index = y * sideLength + x;
        ret[i] = index;
    }
    return ret;
}

I do admit that somewhere along the way the values got transposed, but it does not matter because of how it works.

After doing some optimization I came up with this loop body:

int x = 0;
int y = 0;

for ( int p = 0 ; p < power ; p++ ) {
    int temp = ( i >> ( p * 2 ) ) & 3;
    int a = temp & 1;
    int b = temp >> 1;

    x = ( x << 1 ) | a;
    y = ( y << 1 ) | ( a ^ b );
}
int index = y * sideLength + x;

(the code assumes that c# optimizer, IL2CPP, and CPP compiler will optimize variables temp, a, b out)

Algorithm for visiting all grid cells in pseudo-random order that has a guaranteed uniformity at any stage

Answers (2)

Related Questions