Mine Sweeper: улучшить алгоритм случайного поиска?

Question

Вот мой код для создания сетки со случайным образом генерировать мины. Проблема в том, что мины настолько размыты, поэтому, когда я считаю мин для не-минных ячеек, они в основном имеют значение 1, 2 и почти не имеют значения 4, 5, 6, 7. Как улучшить этот алгоритм?

Предположим, что количество столбцов, строк и мин является постоянным.

var r = new Random();
int columns, rows, TotalMine;
int[,] grid = new int[columns, rows];

int MineCount = 0;
int X = 0;
int Y = 0;

// Add Mines (This is so simple, it cause the problem)
while (MineCount++ < TotalMine)
{
    do
    {
        X = r.Next(columns);
        Y = r.Next(rows);
    }
    while (grid[X, Y] == -1);

    grid[X, Y] = -1; // -1 = have mine
}

Answer 1

Ваш алгоритм прекрасно работает и будет создавать мины со случайным разбросом (при условии, что ГСЧ достаточно хорош).

Одним из способов улучшения, который я мог бы себе представить, было бы использование алгоритма Game of Life для удаления крайностей, например, для загроможденных полей, где одно поле окружено 7 или 8 минами.

Просто переберите все поля и подсчитайте количество мин (то есть рассчитайте номера полей). Если это 7 или 8, удалите одну случайную шахту рядом с ней.

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

Вы также можете смешать обе идеи:

• Создайте стол или доску размером с игровое поле со случайным распределением значений (true или же false).
• Сделайте несколько итераций с алгоритмом Game of Life для создания некоторого паттерна (вы должны получить "островки" или случайные структуры).
• Размещайте свои мины только в пределах областей, которые установлены false (или же true - что бы вы ни выбрали).