Как равномерно распределить гекс сетку между n игроками?

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

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

Вот что я бы сделал:

1. Назначьте все ячейки случайным игрокам. На больших картах это, скорее всего, даст довольно четное количество плиток для всех игроков, на небольших картах вам, вероятно, потребуется внести некоторые исправления.
2. Разбейте куски, которые слишком велики. Проще всего было бы взять все плитки в куски и снова назначить каждую плитку случайным образом.
3. В случае несбалансированного количества ячеек (например, у игрока A есть 24 ячейки, у игрока B - 16), переназначьте пару ячеек от чрезмерно представленных игроков на недостаточно представленных игроков.
4. Проверьте снова на куски. Если на шаге 3 появились новые фрагменты, вернитесь к шагу 2. Если нет, хорошая карта!

Предполагая, что у вас есть шестнадцатеричная карта nячеек и pигроков, где p <= nлучший способ справиться с этим - через круговое распределение через клеточные автоматы (CA).

Инициализация

Случайным образом (и / или с использованием той или иной эвристики, такой как расстояние от центра карты), выберите начальную ячейку для каждого игрока. Так как p <= n, это не должно быть проблемой.

Сотовые автоматы

Вам требуется полная связь между вашими шестнадцатеричными ячейками. Я бы предложил 6-соседний массив на ячейку:

class Cell
{
   //... other members...
   Cell[6] neighbours = new Cell[6];
}

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

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

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

Распределение по кругу

псевдокод:

count number of neutral cells in entire map, minus those starting cells taken by players
while neutral cells remain (or while true)
   for each player
      if player has not yet reached expected territory size in cells
         for each cell already constituting this player's territory
           if territory can grow by one cell into a neutral neighbour
              grow into neighbour
              reduce neutral cell count for entire map by one
              if no more neutral cells remain in map
                 break out of outermost while loop immediately
              else
                 continue to next player immediately
begin game

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

Это обеспечит максимальные размеры «домашних территорий» для каждого игрока. Если вы хотите иметь «островные» территории дополнительно, чтобы выполнить квоту подсчета клеток для этого игрока, то, когда игроку не хватает локального пространства для роста, вы можете выбрать новую начальную ячейку из списка нейтральных ячеек и продолжить тот же процесс "роста", оттуда. Таким образом, вы получите в конечном итоге красивые, согласованные наборы островов для каждого игрока, а не случайный шум.

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

• Начните с назначения цветов для всех ячеек вашей сетки в регулярном шаблоне (например, имейте повторяющийся шаблон «123412341234» в первой строке, затем «341234123412» в следующей и т. Д.). Это может привести к неравномерному распределению цветов , если вашей карта особенно плохо образные, но я предполагаю , что вы начинаете с фиксированной картой, так что вы должны быть в состоянии найти некоторую равнораспределено правильную раскраску этого.
• Затем повторите следующее столько шагов, сколько вам хочется (нет реального критерия «бесполезности», поэтому эксперименты покажут вам, каково минимальное разумное количество шагов):
  • Выберите два элемента сетки наугад
  • Если у них одинаковый цвет, попробуйте еще раз (в противном случае нет никакого смысла, так как тогда обмен будет бесполезным. У вас есть только 1/4 шанса попасть в тот же цвет, и 1/16 шанса попасть в тот же цвет два раза подряд, поэтому вам никогда не придется повторять слишком много)
  • Предварительно поменяйте местами цвета этих двух элементов
  • Проверьте размеры вновь сформированных областей в местах расположения элементов после замены:
    • выполните простую заливку за пределы каждого нового элемента, чтобы определить, насколько велика область этого цвета, которую может сделать своп.
  • Если любой из этих двух регионов больше вашего порога, отмените временный обмен; в противном случае «завершите» замену цветов двух элементов.

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

Кстати, если вы не можете начать с равномерно распределенной обычной раскраски, вы все равно сможете сделать что-то похожее на равнораспределение раскраски: пока ваша раскраска не распределена равномерно, выберите элемент случайным образом; затем, если это один из перепредставленных цветов, временно установите его цвет на один из недопредставленных цветов, а затем убедитесь, что он не создает слишком большой области нового цвета.