[Перевод] Генерирование полигональных карт для игр26.02.2017 11:33

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

Во многих процедурных генераторах карт, в том числе и некоторых моих предыдущих проектах, для генерирования карты высот используются функции шума (midpoint displacement, фракталы, diamond-square, шум Перлина и т.д.). Здесь я их не применял. Вместо неё я использовал структуру графов для моделирования элементов, определяемых ограничениями геймплея (высота, дороги, течение рек, места квестов, типы монстров) и функции шума для моделирования того, что не ограничивается геймплеем (форма побережья, расположение рек и деревьев).

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

Для начала посмотрите демо! (Flash) Прочитайте, как оно работает, или откройте исходный код. Вот описание процесса:

1. Начинаем со структуры графов, созданной из полигонов. 2. Размечаем её. 3a. Вывод в полигоны. 3b. При необходимости вывод в тайлы.

В каждом проекте есть свои геймплейные ограничения. Для этогоRealm of the Mad God проекта ограничения частично взяты из Realm of the Mad God. Это многопользовательская RPG, в которой игроки начинают игру в одиночестве на побережье, а затем объединяются на вершине горы для битвы с боссами. Высота напрямую соотносится со сложностью и должна монотонно увеличиваться. И это ключевое ограничение дизайна. С другой стороны, высота в Minecraft не ограничивается подобным образом, поэтому для этой игры подходит функция шума. В многопользовательской Age of Empires расположение ресурсов ограничено так, чтобы был баланс между игроками. В Minecraft распределение ресурсов не ограничено. Создавая собственный генератор карт, подумайте, какие аспекты вашей карты должны быть заданы умышлено, а какие должны отличаться на разных картах. Все сведения, представленные в этой статье, можно использовать вместе или по отдельности для вашего собственного проекта генератора.

Полигоны

Первый шаг — генерирование полигонов. Простейший способ сделать это — использовать сетку шестиугольников и немного исказить её, чтобы она выглядела необычно. Такой подход работает (и техники из этой статьи будут работать, если вы используете искажённую сетку), но я хотел применить что-нибудь ещё более необычное, поэтому я подобрал случайные точки и сгенерировал полигоны Вороного, которые используются во множестве случаев, в том числе и для создания карт. Wiki по диаграмме Вороного неполная, но в ней есть полезная информация. Я использую библиотеку as3delaunay nodename, в которой есть реализация алгоритма Форчуна.

Вот пример случайных точек (красных) и созданных на их основе полигонов:

Формы и размеры полигонов довольно неравномерны. Случайные числа более «неуклюжи», чем обычно ожидают люди. Я хотел добиться чего-то более близкого к полуслучайному «синему шуму» или к псевдослучайности, а не к случайным точкам. Я приблизился к нужному результату с помощью варианта алгоритма Ллойда, который является довольно простым способом более равномерного распределения случайных точек. Алгоритм Ллойда заменяет каждую точку центроидом полигона. В моём коде я едва усредняю углы (см. improveRandomPoints). Вот результат двойного применения аппроксимации алгоритмом Ллойда:

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

Размеры полигонов улучшены перемещением центров полигонов. Тот же подход применим для улучшения длин рёбер. Перемещая углы усреднением близлежащих центров, мы получаем более равномерные длины рёбер, однако это ухудшает размеры полигонов. См. функцию improveCorners в коде. Однако перемещённые углы теряют свойства диаграммы Вороного. Эти свойства не используются в моём генераторе карт, но не забывайте об этом, если захотите использовать их в игре. Можно или улучшить длины рёбер, или сохранить свойства расстояний Вороного.

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

Представление карты

Я представляю карту в виде двух связанных графов: узлов и рёбер. Первый граф содержит узлы каждого полигона и рёбра между соседними полигонами. Он представляет собой триангуляцию Делоне, полезную при работе с соседними точками (например, при нахождении пути). Второй граф содержит узлы углов каждого полигона и рёбра между углами. Он содержит формы полигонов Вороного. Этот граф полезен для всего, относящегося к формам (например, для рендеринга границ).

Два графа связаны. Каждый треугольник в триангуляции Делоне соответствует углу полигона в диаграмме Вороного. Каждый полигон в диаграмме Вороного соотвествует углу в треугольнике Делоне. Каждое ребро в графе Делоне соответствует ребру в графе Вороного. Это видно из следующей диаграммы:

Полигоны A и B смежные, поэтому в графе смежности есть (красное) ребро между A и B. Чтобы они были смежными, между ними должно быть ребро полигона. (Синее) ребро полигона соединяет углы 1 и 2 в графе форм Вороного. Каждое ребро в графе смежности соответствует ровно одному ребру в графе формы.

В триангуляции Делоне треугольник A-B-C соединяет три полигона, и может быть представлен углом 2. Поэтому углы триангуляции Делоне являются полигонами в диаграмме Вороного, и наоборот. Вот более крупный пример, показывающий взаимосвязи: центры полигонов Вороного показаны красным, а углы — синим, рёбра Вороного — белым, а триангуляция Делоне — чёрным:

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

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

В коде директория graph/ содержит три класса: Center, Corner и Edge:

Center.neighbors — это множество смежных полигонов
Center.borders — множество граничащих рёбер
Center.corners — множество углов полигонов
Edge.d0 и Edge.d1 — полигоны, соединённые ребром Делоне
Edge.v0 и Edge.v1 — углы, соединённые ребром Вороного
Corner.touches — множество полигонов, касающихся этого угла
Corner.protrudes — множество рёбер, касающихся угла
Corner.adjacent — множество углов, соединённых с этим углом.

Острова

Следующий шаг — отрисовка береговой линии. Границы карты должны быть водой, но другие полигоны можно пометить как воду или сушу с помощью любого выбранного вами способа. Условием береговой линии является соседство суши и воды.

Вот пример разделения мира на сушу и воду:

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

Radial использует для создания круглого острова синусоиды
Perlin использует для управления формой шум Перлина
Square заполняет всю карту сушей
Blob рисует мой логотип.

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

Код устанавливает значение суши/воды и для центров, и для углов полигонов:

Назначаем воду/сушу для углов установкой Corner.water на основании IslandFunction.
Назначаем воду/сушу полигонам, устанавливая Center.water, если часть углов имеет набор воды.

Простая заливка начиная с границы карты может определить, какие из областей воды являются океанами (соединёнными с границами) и озёрами (окружёнными сушей):

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

Устанавливаем Center.ocean для любого полигона, соединённого с границами карты через водные полигоны. Если Center.water установлен, а .ocean — нет, то область является озером.
Устанавливаем Center.coast, если полигон является сушей, но имеет границу с океаном. Прибрежные области позже будут отрисовываться как пляжи.
Устанавливаем Corner.ocean, если угол окружён полигонами океана.
Устанавливаем Corner.coast, если угол касается полигонов океана и суши.
Сбрасываем Corner.water, чтобы сохранить целостность с окружающей областью.

Высота

Наиболее реалистично было бы сначала определить высоты, а затем определить береговую линию как границу, где высота достигает уровня моря. Вместо этого я начну в обратном порядке. Возьму хорошую береговую линию, и начну буду отталкиваться от неё. Я определю высоту как расстояние от побережья. Изначально я пробовал сделать высоты в центрах полигонов, но установка высот в углах оказалась удобнее. Рёбра, соединяющие углы, могут служить в качестве долин и хребтов. После вычисления высоты углов (Corner.elevation) высота полигона (Center.elevation) рассчитывается как среднее от высоты углов. См. функции Map.assignCornerElevations и Map.assignPolygonElevations.

Для полигонов воды расстояние не вычисляется. Во-первых, потому, что я хотел, чтобы озёра были плоскими, а не наклонными, во-вторых, так вокруг озёр получаются долины, что помогает направить реки к озёрам.

Возникла одна проблема с этим простым определением: у некоторых островов было слишком много гор, а у других слишком мало. Чтобы исправить это, я перераспределил высоты, чтобы они соответствовали нужному распределению, при котором было бы больше суши с малой высотой (побережье), чем с большой высотой (горы). Сначала я отсортировал углы по высоте, а затем сбросил x высоты каждого из них, чтобы они соответствовали нужной функции распределения: y(x) = 1 - (1-x)^2. В функции Map.redistributeElevations координата y — это положение в отсортированном списке, а x — нужная высота. С помощью формулы корней квадратного уравнения можно вычислить значение x. При этом сохраняется порядок, т.е. высота всегда повышается при перемещении от берега к горам.

При перемещении из любой точки вниз мы обязательно придём к океану. На этой диаграмме показано направление самого крутого спуска с каждого угла, хранящееся в Corner.downslope:

Следуя по стрелкам спуска вниз, мы постепенно придём к океану. Это будет полезно для рек, но может также пригодиться и для вычисления водоразделов и других характеристик.

У меня высота выполняет две основные цели:

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

Кроме того, в играх можно найти собственное применение данным о высотах. Например, в Realm of the Mad God высоты используются для распределения монстров.

Этот расчёт высот подходит для простых островов, именно это мне и нужно было для Realm of the Mad God. Для генерирования континентов потребуется изменить этот шаг, чтобы сгенерировать один или несколько горных массивов, которые не обязательно находятся в центре, а также отдельных вулканов.

Реки

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

Форма острова определяет расположение областей воды и суши. Озёра — это полигоны воды, не являющиеся океанами. Реки используют показанные выше направления спуска. Я выбрал случайные местоположения углов в горах, а потом спустился по Corner.downslope к океану. Река протекает от угла к углу:

Я пробовал пускать и между центрами, и между углами полигонов, но выяснил, что граф углов создаёт гораздо более красивые реки. Кроме того, озёра остаются плоскими, так что высоты рядом с озёрами обычно меньше. Поэтому реки естественно втекают и вытекают из озёр. Несколько рек могут иметь общую часть устья. При каждом протекании реки через ребро я увеличиваю объём воды, хранящийся в Edge.river, на 1. Во время рендеринга ширина реки является квадратным корнем от объёма. Такой подход прост и работает хорошо.

Влажность

Поскольку я выполняю процесс в обратном направлении, мне не нужно, чтобы влажность определяла наличие рек. Однако влажность может быть полезна при разграничении биомов (пустынь, болот, лесов и т.д.). Так как реки и озёра должны формироваться в областях с высокой влажностью, я решил, что влажность будет уменьшаться с увеличением расстояния до пресной воды. Corner.moisture определяется как a^k, где a < 1 (например, 0,95), а k — расстояние. К сожалению, в Map.assignCornerMoisture есть параметры настройки, которые мне пришлось подстраивать, чтобы карты выглядели убедительно:

Как и в случае с высотами, я перераспределил влажность, чтобы она соответствовала нужному распределению. В этом случае я хотел, чтобы было примерно одинаковое количество сухих и влажных областей. Нужная функция распределения равна y(x) = x, поэтому код перераспределения очень прост. Я сортирую углы по влажности, а затем назначаю влажность каждого угла позиции угла в отсортированном списке. См. код в Map.redistributeMoisture.

В этом генераторе карт влажность используется только для биомов. Однако в играх можно найти данным о влажности другие применения. Например, в Realm of the Mad God влажность и высота используются для распределения растительности и монстров.

Биомы

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

ОКЕАН — это любой полигон воды, соединённый с границей карты
ОЗЕРО — любой полигон воды, не соединённый с границей карты. ЗАМЁРЗШЕЕ озеро — это озеро на большой высоте (низкая температура). ТОПЬ — озеро на малой высоте
ПЛЯЖ — любой полигон суши рядом с океаном

Для всех полигонов суши я начал с диаграммы Уиттакера и адаптировал её под свои нужды:

Зона высоты	Зона влажности
6 (влажно)	5	4	3	2	1 (сухо)
4 (высоко)	`СНЕЖНАЯ`	`ТУНДРА`	`БЕЗ РАСТИТЕЛЬНОСТИ`	`ИССОХШАЯ`
3	`ТАЙГА`	`ПОКРЫТАЯ КУСТАРНИКОМ`	`УМЕРЕННАЯ ПУСТЫНЯ`
2	`УМЕРЕННЫЙ ДОЖДЕВОЙ ЛЕС`	`УМЕРЕННЫЙ ЛИСТВЕННЫЙ ЛЕС`	`ЛУГА`	`УМЕРЕННАЯ ПУСТЫНЯ`
1 (низко)	`ТРОПИЧЕСКИЙ ДОЖДЕВОЙ ЛЕС`	`СЕЗОННЫЙ ТРОПИЧЕСКИЙ ЛЕС`	`ЛУГА`	`СУБТРОПИЧЕСКАЯ ПУСТЫНЯ`

Вот результат:

Эти биомы выглядят хорошо в демо, но у каждой игры будут свои потребности. Например, в Realm of the Mad God эти биомы игнорируются и используются собственные (на основании высоты и влажности).

Шумные рёбра

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

Вспомните, что ранее у нас было два графа: один для углов Вороного (1, 2 на диаграмме ниже) и рёбер (синие линии), а другой для центров полигонов (A, B) и рёбер Делоне (красные линии) между ними:

Я хотел сделать оба типа линии шумными, чтобы они не пересекали линии от других полигонов. Кроме того, я хотел чтобы они были и шумными, и правдоподобными. Я понял, что точки code>A, 1, B и 2 формируют четырёхугольник, и можно ограничить отклонения отрезка линии этим четырёхугольником:

Я разделил четырёхугольник ещё на четыре четырёхугольника. Два можно было использовать для красного ребра (Делоне), и два для синего ребра (Вороного). Поскольку линии остаются в выделенном им пространстве и соединяются в центре, они никогда не пересекутся. Так мы ограничили их. Учтите, что четырёхугольник может быть невыпуклым. Чтобы разделить его правильно, я разделил его от середины ребра Вороного вместо деления в пересечении рёбер Вороного и Делоне.

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

Это гарантирует нам, что шумные линии не будут излишне ограничены. (Интересно, могут ли эти четырёхугольники быть полезными в игровой механике?)

Можно использовать любой алгоритм шумных линий, удовлетворяющий этим ограничениям. Я решил рекурсивно подразделить четырёхугольники и соединить отрезки линий в маленьких четырёхугольниках в полное ребро. Алгоритм находится в NoisyEdges.as, функция buildNoisyLineSegments. В результате рёбра полигонов становятся искривлёнными:

Настроить шумность можно в трёх местах:

Результатами рекурсивной функции становятся отрезки меньше определённой длины. У меня есть пример длины отрезка 7, длины отрезка 4 и длины отрезка 1. В демо карты я использовал размер отрезка 1 для рек и побережий, 3 в местах встречи биомов, и 10 во всех остальных случаях.
Существует соотношением между тем, какое пространство отдаётся под красные четырёхугольники (рёбра Делоне) и синие четырёхугольники (рёбра Вороного). Я выбрал в NoisyEdges.NOISY_LINE_TRADEOFF соотношение 0,5.
В NoisyEdges.subdivide есть диапазон случайных чисел. В моём демо выбран диапазон 0,2–0,8, но он может быть в пределах 0,0–1,0. Кроме того, случайные числа не обязательно выбирать линейно. Больше визуального шума получается, если избегать промежутка около 0,5.

Оказалось, что шумные рёбра сильно влияют на внешний вид карты, особенно рек и береговых линий.

Больше шума

Обычно мне нравится шум в игровом арте, и я хотел добавить ещё немного шума в карты. В реальной игровой карте шум может отражать растительность или небольшие вариации рельефа. В демо (mapgen2.as) я заполнил экран текстурой случайного шума, поместив поверх карты шумное растровое изображение. Также я сгладил границы между соседними полигонами, поэтапно смешав цвета:

Вот результат рендеринга с 16 000 полигонов, шумными рёбрами, наложенной шумной текстурой и простым освещением:

Плавные переходы между биомами

Ещё один способ смешения биомов на границах полигонов — создание градиентов на основе высоты и влажности каждого угла с попиксельным назначением биомов:

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

Искажённые переходы между биомами

Ещё один способ сделать карту менее полигональной — исказить карты высоты и влажности:

Добавить шум Перлина или случайный шум к высоте и влажности каждого пикселя.
Сэмплировать ближайшие точки с помощью Перлина или случайного шума для изменения координаты.

Вот пример того, чего этим можно добиться:

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

Демо

Для исследования сгенерированных карт я написал на Flash демо:

Попробовать демо!

Исходный код

Я разместил исходники на Actionscript под лицензией MIT, они доступны на github. Если вы можете читать Java или Javascript, то, думаю, разберётесь и с Actionscript. Я не ожидаю, что код сразу же станет полезным для всех, но он может быть хорошей отправной точкой, если вы хотите использовать эти техники для создания собственных игровых карт.

Map.as — это базовая система генерирования карт
graph/*.as — представление графов (полигоны, рёбра, углы)
mapgen2.as — демо с рендерингом и GUI
Roads.as — модуль, добавляющий дороги вдоль контурных линий
Lava.as — модуль, добавляющий разломы с лавой на рёбрах с большой высотой
NoisyEdges.as используется в демо для создания шумных рёбер

Диаграммы в этой статье созданы из 300 полигонов, по умолчанию в демо используется 2000 с максимумом в 8000. Часть кода для создания диаграмм не проверялась, потому что это «быстрый и грязный» код, написанный только для диаграмм этой статьи, и в остальном бесполезный.

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

Проекты, исследующие другие алгоритмы

Энди Гейни (Andy Gainey) экспериментировал с диаграммами Вороного на сфере и решил вместо этого создать карту из подразделённых икосаэдров с тектоническими плитами, воздушными потоками, температурой, влажностью и биомами. Меня спрашивали, как расширить мой генератор карт для создания континентов: для этого стоит изучить проект Энди.
В генераторе карт Мартина О'Лири (Martin O«Leary) с прекрасным объяснением используются диаграммы Вороного с другим генератором рельефа, симуляцией эрозии, стилизованным рендерером, генерированием городов/регионов, генератор названий и алгоритм размещения меток. Скотт Тёрнер (Scott Turner) дополнил его затенением, контурными линиями и розами ветров, но на сентябрь 2016 года исходный код недоступен. Райан Гай (Ryan Guy) создал проект на основе работы Мартина.
Мигель Сеперо (Miguel Cepero) из Voxel Farm вдохновился на создание политической карты с ландшафтом на основе областей Вороного, а также генератор карт с использованием тектонических плит и альтернативой применению диаграмм Вороного.
Томми Уотерс (Tommy Waters) исследует тектонику плит. Он показывает, как создаёт континенты, а не только острова, так что горные массивы находятся не всегда в центре масс суши.
ylcorcronlth исследует вычисление влажности на основе случайного блуждания
Кори Ли (Cory Lee) создал генератор политических карт с помощью областей Вороного.
Джесс Морган (Jesse Morgan) воспользовался идеями, взятыми из этого генератора карт и создал генератор городов (страница проекта и исходный код)
В Sword & Scroll используется генератор карт Вороного для создания политических областей (земель баронов)
Филл Списс (Phill Spiess) тоже использует в своём проекте диаграммы Вороного с шумными рёбрами, но подробностей не рассказывает.
Кристоф Ле Безнерэ (Christophe Le Besnerais) создал Javascript-версию с расширенной моделью водных потоков. luckylooke написал версию для Phaser.io.
У Каэлана Кутера (Kaelan Cooter) есть генератор мировой карты из шестиугольников с высотами, влажностью, биомами, дождями, водоносными пластами и территориями.

Другие проекты

PolyWorld основан на Java-коде Коннора Кларка и теперь является частью игры Terasology (см. это видео).
В Conquest эти техники используются для создания некоторых игровых карт.
В Besiege эти техники применяются для процедурного генератора карт.
В TerraFirmaCraft 2 техники используются для игры с сеткой шестиугольников.

Этот генератор карт не был предназначен для прямого использования, но в Welsh Piper (таблицы встреч с монстрами, Minocra), Kingdoms in Trevail, Cresta и других (1, 2, 3, 4, 5, 6) играх генератор карт используется для создания карт. Нажмите кнопку «export PNG», чтобы экспортировать файл PNG 2048×2048, который затем можно адаптировать в Photoshop по цвету, стилю и добавить разметку.

Приложение: Дополнительные функции карт

Модули

Я пробовал структурировать представление карт, чтобы модули могли размечать их без создания зависимости от кода. Модуль GUI mapgen2.as зависит от Map.as (базового модуля) и Roads.as (побочного модуля), но Maps.as не зависит от Roads.as. Каждый полигон, ребро и угол в графе имеют индекс, который можно использовать в качестве ключа во внешней таблице. В Roads.as есть массив road, индексированный по индексу рёбер.

Там, где базовый код карты может ссылаться на edge.river как базовое на поле, модуль делать этого не может. Вместо этого модуль ссылается на локальную переменную road[edge.index]. Это срабатывает и для центров, и для углов полигонов. При этом базовый код остаётся чистым.

У меня есть три модуля: Roads, Lava и NoisyEdges.

Дороги

В Realm of the Mad God не используется большинство функций этого генератора карт, но для неё я создал генератор дорог. Я заметил, что в игре пользователи естественным образом исследуют реки. Реки приводят игроков в горы, где они погибают. Я хотел построить дороги, расположенные под нужными углами к рекам.

Я вычислил линии контуров вдоль углов. Там, где уровень контура меняется, находится дорога. Это довольно простой алгоритм, который подходит в большинстве случаев, но иногда создаёт маленькие петли:

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

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

Лава

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

Приложение: Возможности по улучшению

Абстрактный рендеринг

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

Водоразделы

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

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

Думаю, что водоразделы могли бы быть полезны, чтобы давать названия большим областям. В демо на карте примерно 1000 полигонов суши. Для игровой карты было бы неплохо иметь меньшее количество областей с названиями, чем сгруппированных вместе полигонов. Например горы XYZ могут располагаться выше долины XYZ, по которой может протекать река XYZ. Игроки смогут понять, что все эти топонимы связаны. В этом проекте я продвинулся не сильно, но могу рано или поздно вернуться к нему.

Непроходимые границы

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

Анализ рельефа

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