Решение для классического "Блокбастера"

Question

В Великобритании на протяжении 80-х и 90-х годов (я полагаю, и 70-х годов) существовала классическая телевизионная программа под названием «Блокбастер», в которой были показаны шестиугольники в сотовой сетке, например (извините за размытое изображение!)

_{(источник: ukgameshows.com )}

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

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

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

Я закончил тем, что в основном закодировал огромную петлю грубой силы, которая до сих пор не уловила все возможные случаи. Поэтому мне пришлось нажать кнопку на экране организатора конференции, чтобы позволить им быстро объявить победителя, если логика не обнаружит его! Разговор о грязном взломе ...

Теперь я вспоминаю эту головоломку, которую мне пришлось решить, и мне интересно, кто-нибудь из вас захочет предложить более элегантное решение? Конечно, языковая независимость (все, включая псевдокод с радостью приняты).

Редактировать Хорошо хранить ваши данные так, как вы хотите. Я вставил его в массив.

Answer 1

Простой графический алгоритм под названием Flood fill может сделать это.

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

Для каждого игрока проходите все ячейки; если ячейка принадлежит игроку и смежна с одной, если ее шесть сторон от ячейки, «помеченной» этой процедурой заполнения, то ячейка также помечается. Повторно пройдитесь по всем ячейкам и снова, пока ячейки не будут помечены текущим игроком. Вот некоторый псевдокод:

for player in players:
  # those on the starting edge that the player owns get 'marked'
  for cells in cells.start_edge(player):
    if cell.owner = player:
      cell.mark = player
  do:
    count = 0
    for cell in cells:
      if cell.mark == None && cell.owner == player:
        for adjacent in cell.neighbours:
          if adjacent.mark == player
            cell.owner = player
            count += 1
            break
  while count
  for cell in cells.stop_edge(player):
     if cell.mark == player
       player won!!

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

Answer 2

Хитрость заключается в назначении координат каждому блоку.

Что вы можете сделать, так это представить себе простую квадратную сетку 4x4 с координатами x в диапазоне от 0 до 4 и y от 0 до 3.

Алгоритм рисования отвечает за смещение нечетных ячеек х (1 и 3) на половину шестиугольного радиуса, чтобы они правильно совмещались.

Подумайте о isAdjacent(other) методе для каждой ячейки. В квадратной сетке вы можете обосновать isAdjacent с помощью тривиальной проверки: if self.x == other.x & plusmn; 1 и self.x == other.x & plusmn; 1. Есть 8 соответствующих комбинаций -1, 0, 1 для x, -1, 0, 1 для y, которые нужно проверить.

В гексагональной сетке смежность немного отличается. Если self.y == other.y & plusmn; 1 и self.x == other.x является его частью. Но смежность x зависит от того, в каком столбце находится self. Если x является четным столбцом (0, 2, 4), то соседняя ячейка находится в нечетном столбце, что означает self.y == other.y или self.y == other.y + 1. Аналогично, если x нечетный столбец (1, 3), то соседняя ячейка находится в четном столбце. Я оставлю это на ваше усмотрение, чтобы поработать с остальной частью Соседства.

"А как насчет краев"? Легко. Включите их в свой метод grid.get(). Для координат вне пределов вернуть специальную пустую ячейку, которая никогда не занята. Это делает сравнение проще.

Хорошо, учитывая isAdjacent() как мне найти подключенный путь, горизонтальный или вертикальный?

На самом деле вы хотите, чтобы две формы перечисления были смежными. Вы хотите создать enum_adjacent_vert(y_offset) и enum_adjacent_horiz(x_offset). Для перечисления вертикально смежных получим три значения (self.x-1, self.y+y_offset), (self.x, self.y+y_offset), (self.x+1, self.y+y_offset). Чтобы перечислить соседние по горизонтали, укажите два значения, если self.x находится в нечетном столбце: (self.x+x_offset, self.y), (self.x+x_offset, self.y+1). Если self.x находится в четном столбце: (self.x+x_offset, self.y), (self.x+x_offset, self.y-1).

Это относительно просто. Учитывая крайнюю ячейку, вы хотите пройти "поперек" или "вниз" по доске к соседним ячейкам в определенном направлении.

Допустим, вы идете слева направо (увеличивая х). Вы хотите найти соседнюю ячейку в списке enum_adjacent_horiz. Чтобы перейти сверху вниз (с увеличением y), вы найдете соседнюю ячейку в списке enum_adjancent_vert.

Answer 3

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

• Вы можете рассматривать доску как ненаправленный «график». Узлы - это ячейки, и у них есть ребра, если они являются соседними ячейками.
• Стороны также являются узлами на графе, и у них есть ребра для соседних с ними ячеек
• Возьмите подграф графа узлов, которые вы можете использовать (включая верх и низ, если проверяете этого игрока)
• Проверьте, соединены ли верх и низ с помощью DFS