Как найти острова на случайно сгенерированной шестиугольной карте?

Я программирую риск-подобную игру в Codigniter и JQuery. Я придумал способ создавать случайно сгенерированные карты, создавая полный макет плиток, а затем удаляя случайные. Однако иногда это приводит к тому, что я называю островами.

В случае риска вы можете атаковать только одну клетку сверху. Так что, если у одного игрока окажется целый остров, он никогда не сможет проиграть.

Я пытаюсь найти способ проверить карту до того, как игра начнет видеть, есть ли на ней острова.

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

Каждое отсутствующее место также обозначается как «вода».

Мне не разрешено использовать теги изображений: https://imgur.com/xwWzC.gif


hex algorithm map
person J3nnings    schedule 17.08.2009    source источник

Ответы (5)


arrow_upward
8
arrow_downward

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

  • Выберите любую плитку наугад
  • Раскрась это
  • Раскрасьте его соседей
  • Раскрась соседей своих соседей
  • Раскрась своих соседей, соседей, соседей и т. д.

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

person ChrisW    schedule 17.08.2009
comment
Это сработает, но описание не полностью объясняет проблему, в частности, если это так, то это остров. Может быть так, что изначально выбранная плитка является частью острова, а неокрашенные плитки — частью материка. Если вы регенерируете всю карту при обнаружении острова, это нормально, но если вы планируете регенерировать только затронутый регион, это может быть проблемой. - person Imagist; 17.08.2009
comment
@Imagist - я не думаю, что есть какая-то разница между «материк» и «остров»: цель вопроса состоит только в том, чтобы спросить, доступны ли все плитки из любой другой. - person ChrisW; 17.08.2009
comment
@ChrisW Если вы регенерируете всю карту, если обнаружены недоступные плитки, то нет никакой разницы между материком и островом. Если вы регенерируете только часть карты при обнаружении острова, есть большая разница: вам нужно регенерировать меньшую группу недоступных тайлов. - person Imagist; 17.08.2009
comment
@ChrisW Для протокола: я проголосовал за ваш ответ, потому что это лучший способ сделать это. Я просто предупреждаю ОП, что это может быть больше в зависимости от того, как он использует результаты обнаружения. - person Imagist; 17.08.2009
comment
Вы можете подсчитать количество соседей, которых вы раскрашиваете, чтобы определить размер суши. Если есть остров, то его можно раскрасить и посчитать отдельно, и повторить. Затем, когда вы закончите, у вас будет список всех массивов суши и размер каждого из них. - person ChrisW; 17.08.2009

arrow_upward
3
arrow_downward

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

Хотя нам нужно знать, как вы делаете генерацию.

person Noon Silk    schedule 17.08.2009
comment
+1. Каждый раз, когда вы выбираете плитку для удаления, проверяйте, есть ли путь от каждой соседней плитки к каждой другой соседней плитке. - person Nick Johnson; 17.08.2009
comment
Я столкнулся с той же проблемой, что и ОП, и я согласен, что вам гораздо лучше исправить код генерации. - person Dolphin; 21.08.2009

arrow_upward
1
arrow_downward

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

visited = set()
queue = Queue()
r = random tile
queue.add(r)
while not queue.empty():
    current = queue.pop()
    visited.add(current)
    for neighbor in current.neighbors():
        if neighbor not in visited:
            queue.add(neighbor)
if visited == set(all tiles):
    print "No islands"
else:
    print "Island starting at ", r
person hughdbrown    schedule 17.08.2009

arrow_upward
1
arrow_downward

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

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

Это должно (я думаю) выполняться за время O(n), где n — количество тайлов земли.

person tw39124    schedule 17.08.2009
comment
В худшем случае время, вероятно, будет длиться O(n log6 n) раз. - person jmucchiello; 17.08.2009

arrow_upward
0
arrow_downward

Запустите размытое ядро ​​над вашим набором данных.

обработка шестнадцатеричной сетки как изображения (так оно и есть)

значение (x, y) = среднее значение всех плиток вокруг этого (x, y)

это немного разрушит пляжи и устранит острова.

Студенту остается в качестве упражнения запустить ядро ​​обнаружения краев над результирующим набором данных, чтобы заполнить тайлы пляжа.

person Tim Williscroft    schedule 17.08.2009