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

Question

上下文：

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

要求：

我需要一种算法，它以一组格式 (x,y) 或 [index] 生成一组 n^2 条目，描述 nxn 网格中的单元格（其中 n = 2^i，其中 i 是任意的正整数）。

（作为一组，它意味着每个单元格都在一个条目中被提及）
[由算法创建] 的模式应在任何阶段包含零到 none 个“已访问”单元格的聚类。
单元格(0,0)和(n-1,n-1)接近(1,1)，这涉及到聚类的定义

备注我 was/am 试图通过递归构建的类似分形的模式找到解决方案，但在撰写本文时，我的解决方案是查找 table 棋盘模式（黑色单元格列表 + 白色单元格列表单元格）（这很糟糕，但产生的工件比有序列表少）

C、C++、C#、Java 实现（如果有）是首选

Answer 1

您可以使用 linear congruential generator to create an even distribution across your n×n space. For example, if you have a 64×64 grid, using a stride of 47 will create the pattern on the left below. (Run on jsbin) 从亮到暗访问单元格。

该模式没有聚集，但相当均匀。它使用简单的行范围转换，其中

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

您可以通过使 k 成为 space 填充曲线的索引来添加一点随机性，例如 Hilbert curve. This will yield the pattern on the right. (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）

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

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

algorithm

unity3d

multidimensional-array

generator

theory