用于以伪随机顺序访问所有网格单元的算法，该算法在任何阶段均具有保证的一致性

Question

上下文：

我有一个水力侵蚀算法，需要接收液滴起始位置的数组。我已经有一个模式复制算法，所以我只需要一个[[good模式即可复制。

要求：

我需要一种算法，该算法以一组格式（x，y）或[索引]生成一组n ^ 2个条目，这些条目描述nxn网格中的单元（其中n = 2 ^ i，其中i是任何正整数） 。

（作为一个集合，它意味着每个单元格都在一个条目中被提及）
• [由算法创建的模式在任何阶段都应包含零到零的“访问过的”单元簇。
• [（0,0）像（1,1）一样接近（n-1，n-1），这与聚类的定义有关

注意

我/我试图通过递归建立的类似分形的图案来寻找解决方案，但是在撰写本文时，我的解决方案是一个棋盘图案的查找表（黑色单元格列表+白色单元格列表）（不好，但生成的工件少于有序列表）

首选C，C ++，C＃，Java实现（如果有）

已解决！！，寻找我自己的答复。

Answer 1

您可以使用linear congruential generator在您的n×n空间中创建均匀分布。例如，如果您具有64×64的网格，则跨度为47将在下面的左侧创建图案。 （Run on jsbin）从浅到深访问细胞。

该模式不会聚类，但是相当统一。它使用一个简单的行范围转换，其中

k = (k + 47) mod (n * n)
x = k mod n
y = k div n

您可以通过使k成为诸如Hilbert curve之类的填充曲线的索引来增加一些随机性。这将产生右侧的图案。 （Run on jsbin）
您可以在jsbin链接中查看代码。

Answer 2

我已经自己解决了这个问题，只是分享了我的解决方案：

这是我的0到3之间的i的输出，

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

代码：
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;
}

我确实承认价值观在转置过程中的某个地方，但这并不重要，因为它是如何工作的。
经过一些优化后，我想到了这个循环体：
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;

（代码假定c＃优化器，IL2CPP和CPP编译器将优化变量temp，a，b out）