Алгоритм посещения всех ячеек сетки в псевдослучайном порядке, который имеет гарантированную однородность на любом этапе

Question

Контекст:

У меня есть алгоритм эрозии гидравлики c, который должен получить массив начальных позиций капель. У меня также уже есть алгоритм репликации шаблонов, поэтому мне нужен только шаблон хороший для репликации.

Требования:

Мне нужен алгоритм, который создает набор из n ^ 2 записей в наборе формата (x, y) или [index], которые описывают ячейки в сетке nxn (где n = 2 ^ i, где i - любое положительное целое число) .

• (как набор означает, что каждая ячейка упоминается ровно в одной записи)
• Шаблон [созданный алгоритмом] должен содержать кластеризацию "посещенных" от нуля до нуля. ячейки на любой стадии.
• Ячейка (0,0) настолько близка к (n-1, n-1), насколько и (1,1), это относится к определению кластеризации

Примечание Я пытался / пытался найти решения с помощью фрактальных паттернов, построенных с помощью рекурсии, но на момент написания этого мое решение - это таблица поиска паттерна шахматной доски (список черные клетки + список белых клеток) (что плохо, но дает меньше артефактов, чем упорядоченный список)

C, C ++, C#, Java реализации (если таковые имеются) являются предпочтительными

решено !!!, Ищите мой собственный ответ .

Answer 1

Вы можете использовать линейный конгруэнтный генератор , чтобы создать равномерное распределение по пространству n × n. Например, если у вас есть сетка 64 × 64, использование шага 47 создаст рисунок слева внизу. ( Запустить на jsbin ) Ячейки посещаются от светлого до темного.

Этот шаблон не группируется, но он довольно однороден. Он использует простое преобразование всей строки, где

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

Вы можете добавить немного случайности, сделав k индекс кривой заполнения пространства, такой как Кривая Гильберта . Это даст образец справа. ( Запустить на jsbin )

Вы можете увидеть код в ссылках jsbin .

Answer 2

Я решил проблему сам и просто поделился своим решением:

вот мои выводы для i между 0 и 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

код:

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;
}

Я допускаю, что где-то по пути значения были транспонированы, но это не имеет значения из-за того, как это работает.

После некоторой оптимизации я придумал это тело l oop:

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#, компилятор IL2 CPP и CPP оптимизируют переменные temp, a, b out)