Генерируйте равные области на гекс карте

Возьмем, к примеру, большую (шестнадцатеричная) шестнадцатеричную карту, как я могу разделить ее на N областей связанных гексов для моделирования стран?

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

Вы пробовали алгоритм Ллойда ? Процедура довольно проста и будет генерировать достаточно регулярно выглядящие области (в зависимости от того, сколько итераций вы выполняете).

1. Начните с карты с пустыми гексами.
2. Выберите N гексов наугад. Они будут представлять «центр масс» для каждой страны.
3. Пометьте каждый гекс центральным гексом, к которому он ближе всего ( диаграмма Вороного ). Страна i - это множество всех гексов, ближайших к гексу i-го центра.
4. Вычислить новый центр масс для каждой страны.
5. Повторите шаги 3 и 4 столько раз, сколько вы хотите сгладить сгенерированные области.

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

Один простой способ, которым вы можете попробовать.

1. Случайно выберите nгексы. Каждый начнет группу.
2. Для каждой группы попробуйте расширить начальный гекс в случайном направлении.
3. Если все гексы вокруг выбранного гекса заняты, отметьте как постучавший, измените гекс.
4. Повторяйте до тех пор, пока каждая группа не станет 20 гекса длиной или не будет больше места для расширения (все гексы постукивают)

Я не проверял, но это должно генерировать острова и избегать длинных тонких скобок. Кроме того, скорее всего, будут соседние границы, но не обязательно, что каждая будет соприкасаться с другой, эта плотность будет зависеть от значения n.
Некоторые группы также могут быть загнаны в угол другими и могут достигать размера менее 20, вы можете обеспечить увеличенное пространство, порождая стартовые гексы на минимальном расстоянии друг от друга.
Проверьте и настройте по мере необходимости.


Кроме того, не связанные с этой проблемой, но очень, очень полезные для работы с гексами, посетите эту страницу: http://www.redblobgames.com/grids/hexagons/#basics.
Она объединяет всю гексагональную информацию в одном месте с хороший визуальный

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

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

Шаблон стратегии может быть использован для переключения алгоритмов в зависимости от того, какой тип страны вам нужен. http://en.wikipedia.org/wiki/Strategy_pattern т.е. хотите ли вы такую ​​тонкую береговую линию, как Чили? Или вы хотите что-то более круглое и сдержанное?

Свойства графика также могут позволить вам настроить то, что вы хотите, чтобы конечная «страна» была похожа: http://en.wikipedia.org/wiki/Eccentricity_(graph_theory)

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

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

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

Мой первоначальный подход к проблеме должен был бы «развивать» (а не «расти») ваши регионы:

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

Теперь сколько угодно, запустите следующий псевдокод:

Pick a random hex A from the boundary list;
Pick a random neighbor B of this hex from a different country;
if (A's country has more hexes than B's country has) {
  change hex A to belong to B's country;
} else if (B's country has more hexes than A's country has) {
  change hex B to belong to A's country;
} else {
  flip a coin to decide which to change;
}
if ( the changed hex's old country has become disconnected ) {
  undo and reject this move;
} else {
  update the boundary list around the changed hex and its neighbors;
}

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

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

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