Логика для случайного изменения порядка оставшихся плиток с использованием массива карты тайлов

Question

Название объясняет большую часть вопроса.
У меня есть сетка плитки, которая представлена ​​2D-массивом. Некоторые плитки помечены как пустые (но они существуют в массиве, для определенных продолжений использования), в то время как другие находятся в нормальном состоянии.

Мне нужно изменить порядок оставшихся (непустых) плиток в сетке, чтобы все (или большинство) находились в другой непустой позиции. Если бы я просто перебрал все непустые позиции и поменял плитку на другую случайную, я мог бы уже автоматически переупорядочить многие из них (поменялись местами).

Так что мне было интересно, есть ли какая-то техника, которой я мог бы следовать, чтобы удовлетворительно переупорядочить сетку с минимальным циклом. Есть намеки?

Answer 1

public void RandomizeGrid<T>(T[,] grid, Func<T,bool> isEmpty)
{
    // Create a list of the indices of all non-empty cells.  
    var indices = new List<Point>();
    int width = grid.GetLength(0);
    int height = grid.GetLength(1);
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if (!isEmpty(grid[x,y])) // function to check emptiness
            {
                indices.Add(new Point(x,y));
            }
        }
    }

    // Randomize the cells using the index-array as displacement.
    int n = indices.Count;
    var rnd = new Random();
    for (int i = 0; i < n; i++)
    {
        int j = rnd.Next(i,n); // Random index i <= j < n
        if (i != j)
        {
            // Swap the two cells
            var p1 = indices[i];
            var p2 = indices[j];
            var tmp = grid[p1.X,p1.Y];
            grid[p1.X,p1.Y] = grid[p2.X,p2.Y];
            grid[p2.X,p2.Y] = tmp;
        }
    }
}

Answer 2

Удовлетворяет ли это вашим потребностям («удовлетворительно» немного расплывчато), чтобы гарантировать, что каждый непустой элемент мозаики был заменен одним другим непустым элементом мозаики один раз?

Скажем, у вас есть список:

(1,4,7,3,8,10)

мы можем записать признаки списка

(0,1,2,3,4,5)

и выполните N случайных перестановок индексов, чтобы перетасовать его - возможно, некоторые числа сдвигаются, а некоторые нет.

(5,1,3,2,4,0)

Затем возьмите их попарно как последовательность перестановок в нашем исходном списке.

(8,10,3,7,1,4)

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