Процедурно генерировать регионы на острове

29

В настоящее время у меня есть острова, которые выглядят так:

остров

И я хочу процедурно разделить его на регионы, например так:

остров с регионами

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

domisum
источник
Как ты получил это изображение острова в первую очередь? Сгенерировали ли вы это, и если да, то как вы этого добились?
Vaillancourt
Я получил это от онлайн-генератора карт.
domisum
Извините за задержку с обновлением моего ответа - домой потребовалось больше времени, чем планировалось изначально. Я добавил несколько иллюстраций и ссылок.
Пикалек
Если вы получили это от онлайн-генератора, вы должны взглянуть на Azgaar's Fantasy Map Generator . У него есть регионы и имена с настраиваемыми параметрами, и WB.SE привет. Это GitHub, так что вы можете проверить их код.
Anoplexian - Восстановить Монику

Ответы:

40

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

Так что, возможно, хорошим подходом было бы моделировать геологию острова и границы выходили из этого?

В Red Blob Games есть несколько хороших статей на эту тему, с хорошими результатами.

Его подход предполагает использование тесселяции Вороного и определение рек как границ между клетками.

Посмотрите другие статьи на его сайте, он много писал на тему создания карт .

остров

Брэм
источник
3
Обратите внимание, что в реальном мире политические или административные подразделения также иногда имеют произвольные разделения, обычно прямые (например, вдоль широтных / продольных линий, линий между горными вершинами и т. Д.).
Пабло Х
2
@PabloH Хороший вопрос, хотя прямые границы кажутся феноменом эпохи постмедиа. Но так как мы не знаем, как будет решаться проблема с операционными процессами, это может быть актуально
Sentry
27

Я бы решил эту проблему с помощью двух проходов диаграмм Вороного:

Первый проход: Разделение региона

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

введите описание изображения здесь

Второй проход: рандомизация границ

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

введите описание изображения здесь

И вот та же самая область, показывающая только окончательные границы:

введите описание изображения здесь

Комментарии о точечной генерации

Что касается генерации точек, мне нравится использовать распределение дисков Пуассона , чтобы получить относительно хорошее и равномерное распределение точек. Другой распространенный вариант - получить аналогично равномерное распределение - использовать алгоритм Ллойда на множестве «обычных» случайных точек. LLoyd's легче кодировать, но он может принять несколько проб и ошибок, чтобы определить, сколько проходов требуется для получения желаемого результата.

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

Финальные заметки

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

Pikalek
источник
1
Для процедурных поэтажных планов это то, что я делаю, создаю диаграмму Вороного из точек внутри региона (острова), строим сетку (она не должна быть прямоугольной, в вашем случае деформированной сеткой), которая охватывает ту же область, затем вычислите логические пересечения сетки и Вороного, вычислите области и назначьте дерево данных (список, зубчатый массив и т. д.), какую бы структуру данных вы ни выбрали, в соответствии с 0,6 процентами от наименьшей ячейки сетки, Вы получите несколько пропущенных ячеек, но вы можете сравнить свою отбракованную сетку с оригиналом, чтобы найти и переназначить свое дерево.
Фелипе Гутьеррес
Вы добавили изображения! Это именно то, что я делаю для другой цели
Фелипе Гутьеррес
4

MineCraft делает это хорошо, и его алгоритм генерации мира был тщательно проанализирован и задокументирован.

Существуют различные описания алгоритма, одно из них здесь: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-algorithm

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

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

Существуют различные онлайн-инструменты для создания карты биома из случайного семени, одним из которых является mineatlas.com . Я предполагаю, что внутри они используют Java-сервер, который использует внутренние классы самого MineCraft; Я не знаю, доступен ли какой-либо их исходный код напрямую.

Гунтрам Блом поддерживает Монику
источник
4

Типичный алгоритм, используемый, например, Azgaar ( исходный код ). Примерно так:

  1. разделите вашу сушу на более мелкие области, например, с помощью триангуляции Делона или вороной клетки.
  2. определить (случайным или иным образом) «стартовые» места для ваших культур, сфер, религий или чего-либо еще, что вы хотите смоделировать.
  3. определить (случайным образом или иным образом) «фактор роста» для каждого из них. Чем больше различий в факторах роста, тем менее однородна ваша итоговая карта.
  4. Теперь выполняйте итерации по своим сферам (и т. Д.) И, в зависимости от фактора роста, заставляйте их распространяться на окружающие пустые тайлы, пока не будет заполнена вся карта.
  5. Вы, вероятно, хотите закончить немного выпрямлением границ, переключая ячейки, которые имеют только одного соседа в своем собственном цвете, и в противном случае окружены другим цветом этого цвета.
Том
источник
3

Если вы заинтересованы в том, чтобы делать это в векторном формате, а не на основе растровых подходов, я недавно написал сообщение в блоге об этом.

http://blog.particracy.com/worlds-and-their-geography/

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

Воутер Ливенс
источник
2

Что за забавный вопрос :) Этот подход основан на использовании ячеек Ворного, но метрика расстояния не совсем евклидова (я использовал степень 1,5 вместо 2,0), и в нее встроена некоторая случайность. Он может перепрыгнуть через воду, что не идеально.

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

Если вам интересно, я могу перейти к более подробной информации и поделиться кодом Python.

карта 1 карта 2

NikoNyrh
источник