Статьи

Объясненные алгоритмы: тральщик

Ноябрь 13, 2017

В этом блоге объясняются основные алгоритмы известной игры для Windows «Сапер».

Правила игры

  1. Доска представляет собой двухмерное пространство, в котором имеется заранее определенное количество мин.
  2. Клетки имеют два состояния, открытое и закрытое.
  3. Если вы щелкните левой кнопкой мыши на закрытой ячейке:
    1. Ячейка пуста и открыта. 
      1. Если соседние ячейки имеют мои мины, эта открытая ячейка показывает количество соседних мин.
      2. Если соседние ячейки не имеют мин, все соседние ячейки открываются автоматически.
    2. У ячейки есть мина, игра заканчивается FAIL.
  4. Если вы щелкнете правой кнопкой мыши по закрытой ячейке, вы поставите флажок, который показывает, что «я знаю, что у этой ячейки есть моя».
  5. Если вы щелкнете несколько раз (как правой, так и левой кнопкой мыши) на ячейке, которая открыта и имеет хотя бы одну шахту на своих соседях:
    1. Если общее количество флагов соседних ячеек равно количеству ячеек с несколькими щелчками мыши, и прогнозируемые местоположения мин правильные, все закрытые и непомеченные соседние ячейки открываются автоматически.
    2. Если общее количество флагов соседних ячеек равно количеству ячеек с несколькими нажатиями, и хотя бы одно из предсказанных местоположений мины неверно, игра заканчивается FAIL.
  6. Если все ячейки (без мин) открываются с помощью левых и / или мульти-кликов, игра заканчивается УСПЕХОМ.

Структуры данных

Мы можем рассматривать каждую ячейку как структуру пользовательского интерфейса (например, кнопку), которая имеет следующие атрибуты:

  • colCoord = 0 до colCount
  • rowCoord = 0 до rowCount
  • isOpened = true / false (по умолчанию false)
  • hasFlag = true / false (по умолчанию false)
  • hasMine = true / false (по умолчанию false)
  • соседний счет от 0 до 8 (по умолчанию 0, общее количество мин в соседних ячейках)

Итак, у нас есть двумерная структура данных «Button [] [] ячейки» для обработки игровых действий.

Алгоритмы

Перед началом:

  1. Назначьте мины ячейкам случайным образом (установите hasMine = true).
  2. Вычислите значения соседейMineCount для каждой ячейки, у которой есть hasMine = false. (Этот шаг может быть сделан для каждой ячейки, на которую нажали, пока игра продолжается, но она может быть неэффективной.)

Примечание 1: Соседние ячейки должны быть доступны с координатами: 

{(colCoord-1, rowCoord-1),(colCoord-1, rowCoord),(colCoord-1, rowCoord+1),(colCoord, rowCoord-1),(colCoord, rowCoord+1),(colCoord+1, rowCoord-1),(colCoord+1, rowCoord),(colCoord+1, rowCoord+1)}

И не забывайте, что число соседних ячеек может быть 3 (для угловых ячеек), 5 (для краевых ячеек) или 8 (для средних ячеек).

Примечание 2:  Рекомендуется обрабатывать щелчки мыши с помощью действий «отпускание мыши» вместо действий «нажатие / нажатие мыши», в противном случае щелчок влево или вправо можно понимать как множественный щелчок или наоборот.

Щелкните правой кнопкой мыши на ячейке:

  • Если ячейка isOpened = true, ничего не делать.
  • Если ячейка isOpened = false, установите ячейку hasFlag = true и покажите флаг в ячейке. 

Щелкните левой кнопкой мыши на ячейке:

  • Если ячейка isOpened = true, ничего не делать.
  • Если ячейка isOpened = false:
    • Если ячейка hasMine = true, игра окончена.
    • Если ячейка hasMine = false:
      • Если ячейка имеет neighmineCount> 0, установите isOpened = true, покажите соседа в ячейке. Если все ячейки, имеющие hasMine = false, открыты, завершите игру УСПЕХОМ.
      • Если ячейка имеет neighmineCount == 0, установите isOpened = true, вызовите щелчок левой кнопкой мыши на ячейке для всех соседних ячеек, для которых hasFlag = false и isOpened = false.

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

Множественный щелчок (как левый, так и правый) в ячейке:

  • Если ячейка isOpened = false, ничего не делать.
  • Если ячейка isOpened = true:
    • Если ячейка соседаMineCount == 0, нет ничего.
    • Если ячейка соседаMineCount> 0:
      • Если ячейка соседаMineCount! = «Сосед имеет hasFlag = истинное количество ячеек», ничего не делать.
      • Если ячейка соседаMineCount == «сосед имеет hasFlag = истинное количество ячеек»
        • Если все соседние ячейки hasFlag = true не имеют hasMine = true, игра окончена.
        • Если все соседние ячейки hasFlag = true имеют значение hasMine = true (каждый флаг помещается в правильную ячейку), вызовите  щелчок левой кнопкой  мыши на ячейке для всех соседних ячеек, для которых hasFlag = false и isOpened = false.

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

35
Share: