Алгоритм генерации мин тральщик

Делаю клон тральщика. Мой текущий алгоритм генерации мины таков: выбери координату, если на ней нет мины, поставь мину, иначе попробуй еще раз. Я думаю, что это неэффективный алгоритм, особенно на минных полях с высокой плотностью. Я рассматриваю некоторые другие варианты, такие как перетасовка Фишера-Йейтса и тому подобное, но я думаю, что у нее будет много времени для гораздо больших сеток. Я думаю об использовании связанных списков. Какие-либо предложения?


algorithm minesweeper
person userx01    schedule 06.03.2015    source источник
comment
поместите все возможные местоположения в список. перетасуйте список и положите бомбы в первые x мест.   -  person Calum    schedule 06.03.2015
comment
Просто используйте перетасовку Фишера-Йейтса, чтобы рандомизировать индексы, а затем выберите количество мин от 0 до этого числа.   -  person AD.Net    schedule 06.03.2015
comment
ох. Благодарность! попробую те. Но есть ли другие решения, которые могут сократить ненужную работу? Например, действительно ли мне нужно перетасовать ВЕСЬ список? В любом случае, я думаю, что буду придерживаться перетасовки, это проще и управляемее.   -  person userx01    schedule 06.03.2015
comment
@ userx01 вам не нужно перемешивать весь список, вам просто нужно выбрать случайный индекс.   -  person Pham Trung    schedule 06.03.2015

Ответы (1)


arrow_upward
0
arrow_downward

Если у вас есть список/массив, в котором вы можете получить размер списка за постоянное время, вы можете попробовать следующее:

list = List of all fields
N = number of mines
N.times do
  index = random(list.size)
  pick list[index]
  list.remove(index)
end

Сюда:

  • вам не нужно перетасовывать весь список
  • вы избегаете выбора одних и тех же полей 2 раза

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

person dfens    schedule 06.03.2015
comment
Да! Это то, что я ищу. Отличная помощь, спасибо! Кстати, можно ли этого добиться, используя только массивы? (для языков без структур данных) - person userx01; 06.03.2015
comment
Я думаю, что вы ищете скорее вектор, чем список. По умолчанию структура данных чистого списка не имеет метода size() с постоянным временем и метода remove(). - person dfens; 06.03.2015
comment
Допустим, у меня есть массив 2d для минного поля. Затем я составлю еще один список и выберу X индексов, верно? Так что, по крайней мере, я копирую весь массив? - person userx01; 07.03.2015