Какой алгоритм стоит у поколения тральщиков
Ну, я прошел через множество сайтов, рассказывающих о том, как ее решить, но мне было интересно, как ее создать. Меня не очень интересуют его аспекты кодирования, но я хотел бы узнать больше об алгоритмах, стоящих за ним. Например, когда сетка генерируется из 10 мин или около того, я бы использовал любую случайную функцию, чтобы распределить себя по сетке, но опять же, как мне установить связанные с ним числа и решить, какой ящик открыть? Я не мог сформулировать какой-либо общий алгоритм того, как мне поступить.
3 ответа
Возможно, что-то вроде:
grid = [n,m] // initialize all cells to 0
for k = 1 to number_of_mines
get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine
for x = -1 to 1
for y = -1 to 1
if x = 0 and y = 0 then
grid[mine_x, mine_y] = -number_of_mines // negative value = mine
else
increment grid[mine_x + x, mine_y + y] by 1
Вот-вот так...
** EDIT **
Потому что этот алгоритм мог ] приведет к созданию доски с некоторыми минами, сгруппированными слишком сильно или, что еще хуже, очень рассредоточенными (таким образом скучно решать), вы можете затем добавить дополнительную проверку при создании чисел mine_x и mine_y. Например, чтобы убедиться, что по крайней мере 3 соседние ячейки не являются минами, или даже, возможно, способствовать ограничению количества мин, которые находятся слишком далеко друг от друга, и т. д.
** ОБНОВЛЕНИЕ **
Я взял на себя смелость немного поиграть с JS bin, здесь я придумал функциональную демонстрацию игры Minesweeper.Это просто для демонстрации алгоритма, описанного в этом ответе. Я не оптимизировал случайность генерируемой позиции шахты, поэтому некоторые игры могли быть невозможными или слишком простыми. Кроме того, нет проверки того, сколько мин в сетке, так что вы можете создать сетку 2 на 2 с 1000 мин.... но это приведет только к бесконечному циклу :) Наслаждайтесь!
Вы просто засеиваете мины, после чего проходите каждую ячейку и считаете соседние мины.
Или вы устанавливаете каждый счетчик на 0 и с каждой заполненной шахтой вы увеличиваете счетчики всех соседних ячеек.
Если вы хотите разместить m мин на N квадратах, и у вас есть доступ к генератору случайных чисел, вы просто проходите по оставшимся квадратам и для каждого квадрата вычислите (осталось # мин)/(осталось # квадратов) и поместите мину, если ваше случайное число равно или меньше этого значения.
Теперь, если вы хотите пометить каждый квадрат количеством соседних мин, вы можете просто сделать это напрямую:
count(x,y) = sum(
for i = -1 to 1
for j = -1 to 1
1 if (x+i,y+j) contains a mine
0 otherwise
)
или, если хотите, вы можете начать с массива нулей и увеличивать каждый на единицу в 3x3 площадь с шахтой в центре. (Не помешает пронумеровать квадраты с минами.)
Получается чисто случайная и правильно аннотированная игра про тральщиков. Однако некоторые случайные игры не могут быть веселыми; выбор случайных, но забавных игр — гораздо более сложная задача.