Каковы хорошие алгоритмы для создания границ / областей состояния на 2-х звездных картах?

9

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

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

Звездные системы и их фракция

к этому

Звездные системы с зонами фракций

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

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

Позвольте мне объяснить, что я имею в виду, когда говорю красивее: в нижней части связанного вопроса спрашивающий представляет свой конечный результат после реализации принятого ответа. Моя первая проблема здесь: области для узлов № 6, № 9 и № 12 очень маленькие и странной формы. Кроме того, вместо острых краев я бы предпочел более плавный изогнутый вид.

Мои собственные идеи, в том числе соответствующие недостатки / вопросы, которые я вижу с ними:

  • Создайте многоугольник с выпуклой оболочкой для каждой фракции, затем немного увеличьте его наружу. Проблемы: нет вогнутых функций. Кроме того, как вы справляетесь с перекрытиями?
  • Создайте вороной график для точек, затем используйте ребра полигона вороного между соседними системами различных фракций в качестве границ. Проблема: Большие полигоны по краям карты - как их идентифицировать и исправить?
  • Создайте многоугольник фиксированного размера для каждой точки, объедините все многоугольники для одной фракции (в результате получается один большой, потенциально сложный «полигон фракции»). Затем сделайте что-нибудь, чтобы согласовать перекрывающиеся области между двумя фракциями. Проблемы: как бы я это сделал? Не совсем тривиальный процесс. Что если есть совпадение между более чем двумя фракциями?

Ваша помощь приветствуется.


Приложение: Подумав о первых двух ответах и ​​их подходах к решению проблемы, я понял, что мои требования выше не выполнены.

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

Звездные системы с областями фракций, различными кластерами

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

GRUSE
источник
(мозговой штурм) Вы можете заполнить оставшееся пространство синим шумом (например, диск Пуассона), а затем запустить voronoi, чтобы получить цветовое назначение. Добавленным точкам будет присвоен белый фон.
amitp
@amitp Эй, Амит, это честь, что ты комментируешь здесь! Я почерпнул огромное количество вдохновения и практических знаний, прочитав ваши статьи об играх Red Blob. Больше по теме: Идея создания дополнительных точек имеет смысл, есть какая-то конкретная причина, почему вы упоминаете синий шум конкретно?
Grüse
... Я думаю, потому что это выглядит как более естественное распределение, чем другие звуковые ароматы.
Grüse

Ответы:

16

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

  1. Как вы упомянули, есть пустые области, которые не следует назначать фракции. Вороной создаст большие полигоны, которые простираются до областей, где фракция не должна достигать. Чтобы исправить это, используйте алгоритм синего шума, такой как диск Пуассона, чтобы заполнить незанятое пространство звездами, «принадлежащими никому». Синий шум является случайным, но равномерно распределенным (он также может быть полезен для генерации ваших звездных локаций).
  2. Вороной производит блочные районы. Чтобы получить более округлые ячейки, замените расчет центроцентра Вороного расчетом центроида. Я написал немного об этом здесь с некоторыми изображениями сравнения.
  3. Вороной производит полигоны, но вы хотите круглые области. На каждом углу есть три полигона. Когда все три - одна фракция, вы можете оставить это в покое. Когда две фракции - одна и та же, введите квадратичную кривую Безье, которая сдвигает границу в сторону другой фракции. Когда все три фракции различны, вы можете либо оставить угол в покое, либо ввести три кривые Безье, чтобы отодвинуть все границы друг от друга. Я не уверен, что выглядит лучше.

Вот вывод:

Blobby карта

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

amitp
источник
Это идеально подходит для моего случая использования, большое спасибо! Должен сказать, что столь же впечатляюще и удручающе то, что вы смогли собрать интерактивный пример так быстро, хотя мне, вероятно, потребуется хотя бы несколько дней, чтобы воспроизвести то, что вы здесь представили :) С нетерпением жду этой учебной статьи.
Grüse
4

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

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

Используйте эти детали для создания временной сетки (например, массива), которая приблизительно соответствует пикселям вашей карты. Вы можете построить такую ​​сетку с желаемым разрешением, включая 1: 1.

Затем, используйте уравнение переноса тепла / поля, чтобы перебрать и распространить сильные стороны объектов фракции (тепло) против сильных сторон объектов противника (холодные) для каждой соседней ячейки в сетке.

Промойте и повторите для каждой фракции на вашей карте, создавая отдельные сетки фракций для каждой.

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

Искусство этого процесса - определить, какое влияние должен оказывать каждый объект, и какие игровые элементы вы используете для количественной оценки этого значения.

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


Дополнительная ссылка: дискуссия о происхождении карт влияния .

J'Eight
источник
Этот подход должен быть очевидным, но он никогда не приходил мне в голову. Спасибо, что обратили на это мое внимание! Мысль: мои карты могут быть редкими в определенных областях, в то время как другие области плотно упакованы звездами различной принадлежности рядом друг с другом. Есть ли способ использовать ячейки разных размеров для разных областей? Думая по линии дерева или подобного.
Grüse
2

Вы должны посмотреть на диаграммы Вороного. Вот определение в Википедии:

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

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

В библиотеке FastNoise есть поддержка диаграмм Вороного, поэтому, возможно, вам стоит взглянуть на нее.

Сглаживание областей

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

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

Геометрия манипуляции

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

BadgerBadger
источник
Обратите внимание, что OP уже ссылался на ответ с использованием диаграмм Вороного, поэтому они знают о технике, но попросили конкретных модификаций для изменения внешнего вида границ. Можете ли вы расширить свой ответ, чтобы ответить на эти конкретные запросы?
DMGregory
Извините, неправильно прочитал сообщение
BadgerBadger
Спасибо за изменение вашего ответа! Идея сглаживания интересна. У меня есть две проблемы с подходом Вороного: Один: как мне определить и ограничить «внешние» точки, чтобы границы не растягивались до краев экрана (см. Второе изображение моего вопроса). Два: в малонаселенных районах Вороной не дает больших результатов, потому что полигоны становятся огромными. Может быть, есть очевидное решение тех, которые я не вижу?
Grüse
Будет ли это возможность добавить точки самостоятельно, чтобы создать область? Затем, когда вы визуализируете график, если линия достигает фактического края изображения, вы просто не рисуете его, поскольку он не будет частью игровой области. Вторая проблема должна быть исправлена ​​с помощью сглаживания. Вы можете добавить больше очков, когда они появятся дальше, так что вы сохраняете некоторый постоянный «размер сетки».
BadgerBadger
@BadgerBadger Да, я экспериментирую с добавлением очков прямо сейчас
Grüse