Генерирование полигональных карт для игр

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



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

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

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


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

В каждом проекте есть свои геймплейные ограничения. Для этого проекта ограничения частично взяты из 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 рисует мой логотип.

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

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

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

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



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

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

Высота

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

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



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

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

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

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

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

Кроме того, в играх можно найти собственное применение данным о высотах. Например, в 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) и рёбер Делоне (красные линии) между ними:



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



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

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



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

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



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

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

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

Больше шума

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



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

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

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



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

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

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

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

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



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

Демо

Для исследования сгенерированных карт я написал на 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) есть генератор мировой карты из шестиугольников с высотами, влажностью, биомами, дождями, водоносными пластами и территориями.

Похожие алгоритмы на других языках программирования

• Ричард Яницек (Richard Janicek) написал Haxe-версию, компилирующую в Javascript+Canvas с демо. Также он создал Javascript-версию с демо.
• Джефф Террес (Jeff Terrace) написал патчи и утилиту для конвертации XML в COLLADA, а также приложение для просмотра COLLADA на WebGL.
• Алекс Шрёдер (Alex Schröder) работал над Perl-версией, генерирующей выходные данные в SVG.
• Кристофер Гарретт (Christopher Garrett) написал порт Voronoi/Delaunay для iOS.
• Адам Мартин (Adam Martin) поддерживает ветвь порта Voronoi/Delaunay для Unity, форкнутую из порта Джулиана Цейпека (Julian Ceipek).
• Кристоф Гебер (Christophe Guebert) написал версию Java+Processing.
• Баран Кахьяоглу (Baran Kahyaoglu) написал версию под C#/.NET (исходный код), а abhimir создал Unity-версию версии кода Барана, написанной Крисом Хербортом (Chris Herborth).
• У Томми Уотерса (Tommy Waters) есть ещё одна Javascript-версия с исходниками и постом в блоге.
• Егор Харват написал версию под Haxe/NME.
• У Коннора Кларка (Connor Clark) есть Java-версия.
• Kylepixel создал проект на Javascript, в котором для генерирования карты тоже используются области Вороного.
• У Nuclear Horse Studios есть версия для C#/Unity (лицензия MIT).
• Стаффорд Уильямс (Stafford Williams) написал версию для C#/Unity (лицензия MIT).
• У Гарета Хиггинса (Gareth Higgins) есть генератор карт на C#.
• Мартин Кандела Калабуиг создал (Martín Candela Calabuig) версию на C++.
• Тобиас (Tobias) работает над версией для C++
• Спенсер Джадж (Spencer Judge) написал код C++ для гененирования карт с помощью этих техник.
• У BitAlchemists есть версия для Dart.
• У Томаса Р. Колла (Thomas R. Koll) есть порт на Lua, который он использует для Autonomous Planetary Research Individual 50.
• Island — это проект на Scala, использующий техники, похожие на описанные в моей статье.
• PtolemyJS — игровой движок на Javascript со встроенным генератором карт на принципе областей Вороного.
• Джей Стивенс (Jay Stevens) создал версию на C++ для Unreal 4 (лицензия MIT).

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

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

Этот генератор карт не был предназначен для прямого использования, но в Welsh Piper (таблицы встреч с монстрами, Minocra), Kingdoms in Trevail, Cresta и других (1, 2, 3, 4, 5, 6) играх генератор карт используется для создания карт. Нажмите кнопку «export PNG», чтобы экспортировать файл PNG 2048x2048, который затем можно адаптировать в 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. Игроки смогут понять, что все эти топонимы связаны. В этом проекте я продвинулся не сильно, но могу рано или поздно вернуться к нему.

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

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

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

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

Области с названиями

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

Переменная плотность

Можно использовать алгоритм Форчуна для подразделения полигона на меньшие полигоны. Карта, на которой бóльшая часть мира очерчена грубо, а некоторые области более детализированы, может смотреться интересно. В качестве альтернативного подхода мы можем расположить исходные точки с переменной плотностью, чтобы в одних областях было больше полигонов, чем в других. Например, вместо алгоритма Ллойда можно применить избыточную выборку сглаживания.

Улучшение шумных рёбер

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

Приложение: Усовершенствование процесса

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

Если кому-нибудь интересно, как я дошёл до этого, то вот краткая история:

• В декабре 2009 года Роб и Алекс из Wild Shadow Studios спросили, есть ли у меня быстрый способ генерирования карт. Я уже думал над использованием шума Перлина для создания карт, поэтому я попробовал его, и получил хорошие результаты. Рабочий прототип я сделал за день, и ещё месяц ушёл на настройку и подбор вариаций. Большинство вариаций не подходило, и я понял, что у такого подхода есть ограничения. Месяца трудов было достаточно, поэтому я закончил работать с картами и перешёл к другим мелким проектам — графика, анимации, группы монстров, AI для NPC и т.д.
• В июне 2010 года у меня снова появилось вдохновение для работы с картами. Я провёл месяц, записывая идеи на бумаге и пробуя разные прототипы. Я пробовал использовать сетки шестиугольников, шестиугольные бассейны рек, генерирование рек на основе четырёхугольников, вулканов, холмов, эрозии, погодных систем и кое-что ещё. Всё заканчивалось провалом. Однако в процессе я многому научился. Например, триангуляции Делоне мне не подошли, но привели к диаграммам Вороного. Генерирование рек на основе четырёхугольников не сработало, но четырёхугольники пригодились позже, когда я начал работать над шумными рёбрами. Система эрозии не получилась, но некоторые идеи были полезны при работе над реками.
• Посещая курсы по процедурному генерированию контента, я записал ещё несколько идей по генерированию карт. Во время долгих выходных в честь 4 июля я реализовал их, и они сработали отлично. В те выходные я создал полигоны Вороного, представление карты, генерирование островов, шумные рёбра, высоты, биомы, реки и перераспределение высот. Я испытывал чувство потока. И это было потрясающе! Бóльшую часть базовой системы я создал всего за три дня.
• В каждые выходные июля и августа я вносил улучшения, многие из них были довольно значительными. Также я вносил многие изменения, которые не сработали, так что пришлось их удалить. Когда базовые параметры карты стали достаточно хорошими, я сместил акцент на рендеринг и UI карты. После улучшения рендеринга и UI я смог увидеть новые недостатки на карте, и нашёл множество ошибок. Также я выполнил масштабный рефакторинг для упрощения кода, который раньше рос органически.
• К концу августа я осознал, что работаю только над мелкими улучшениями, и решил, что проект готов к сворачиванию. Длинные выходные в честь Дня труда я провёл, записывая результаты в эту статью (и посты). Много времени ушло на создание качественных диаграмм. Диаграммы выявили новые баги, поэтому я перешёл к их устранению, значительно упростив одну функцию (перераспределение высот) и реализовав новую (перераспределение влажности). Кроме того, я переименовал и прокомментировал код, чтобы его проще было объяснять.

Почему я отслеживаю всё это? Потому что пытаюсь улучшить процесс работы с такими небольшими (1-3 месяца) проектами. Вот что я хочу напомнить:

1. Полезно иметь ключевую идею, толкающую весь проект вперёд. Простые карты, которые я делал в январе, были основаны на шуме Перлина. Нынешние карты основаны на диаграммах Вороного. Мне нужно было определиться с выбором и продолжать работу, но это потребовало времени…
2. Прежде чем найти нужную идею, иногда приходилось много экспериментировать. Пока я не додумался до Вороного как до базовой структуры, я работал над идеями около месяца. Мне нужно записывать множество идей.
3. У меня было много неудач. Важно ошибаться быстро, не надо бояться ошибиться. Мне нужно не терять духа.
4. Базовую систему я сделал за три дня. Быстрый прототип может многое рассказать о работоспособности идеи. На ранних стадиях мне нужно сосредоточиться на прототипе и пока забыть про высококачественную систему.
5. На самом раннем этапе более важно изучать систему, чем создавать хороший код. Мне нужно спросить себя, чему я хочу научиться с помощью прототипа.
6. Ошибки иногда пригождаются позже. Нужно сохранять их. Я удалял код сразу после того, как видел его недостатки, но, возможно, мне стоило создавать больше ветвей в git и хранить его там.
7. Возможность наблюдать визуально может сильно помочь в понимании того, что происходит. Я пропустил несколько ошибок в коде, потому что не утруждал себя созданием визуализации части данных. Нужно визуализировать как можно больше.
8. Иногда появляются небольшие отклонения, которые на самом деле означают присутствие ошибок в коде. Часто я от них просто отмахивался. Даже если в тот момент было не время находить и исправлять ошибки, нужно фиксировать их для дальнейшего исследования.
9. Огромную помощь оказало написание постов в блог. Они заставили меня понимать все части системы, рассматривать все данные и обеспечить понимаемость всего кода. Посты вынудили меня подвергать проверке каждый этап генерирования карт и усовершенствовать те, которые сложно объяснить. Нужно начинать писать посты в блог гораздо раньше в процессе работы. Объяснение — хороший способ учиться.

Я учту эти уроки при работе над новыми проектами.

Приложение: Ссылки

Благодарю блог Dungeon League за отличную серию постов по процедурному генерированию карт, Procedural Content Generation wiki за идеи по генерированию карт, неполную Voronoi wiki за полезные ресурсы о диаграммах Вороного.

Спасибо nodename за as3delaunay. Это библиотека Actionscript 3 для генерирования графов Вороного и Делоне. Также большое спасибо polygonal за PM_PRNG, библиотеку случайных чисел, позволившую мне использовать и менять значение seed для воспроизведения множеств псевдослучайных чисел. Я использовал библиотеку OptiPNG для оптимизации PNG-изображений этой статьи.

Триангуляция Делоне и полигоны Вороного изучаются на многих курсах графики. Например, см. Stanford CS 368(PDF). Я также изучил графы относительной смежности и графы Габриэля, но не использовал их.

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

Алгоритм Форчуна — один из алгоритмов, способных превратить множество точек в полигоны Вороного. Это реализовано в as3delaunay. Алгоритм Ллойда используется для улучшения распределения случайных точек. Он уменьшает неравномерность полигонов Вороного. На Voronoi wiki есть неполная информация о представлении графов и представлении рёбер, а также две страницы, которые помогли мне в генерировании рек: реки и водоразделы и кора и скелет.

На веб-сайте Relief Shading есть изображения карт отмывки рельефа, а также инструкции по дизайну затенения и раскраски. Печально, что мне не хватило времени применить эти техники. Также я изучил карты Bing и Google, чтобы понять, как в них отрисовываются разные особенности; см. эту статью, мой пост в блоге и эту статью.

Диаграмма Уиттакера — один из способов прогнозирования общих биомов с заданным климатом. В Википедии есть страница со схемами классификации биомов и разными биомами.

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

Кен Перлин (Ken Perlin) — мастер работы с шумами, он придумал шум Перлина. Также он создал менее известный симплекс-шум (PDF). В моём проекте я использовал шум Перлина для создания общей формы острова. У Джо Слейтона (Joe Slayton) есть страница о том, как превратить шум Перлина в острова. Я искал информацию о синем шуме и, прежде чем нашёл алгоритм Ллойда для улучшения распределения случайных точек, наткнулся на статью Данбара (Dunbar) и Хамфри (Humphreys) о генерировании шума, а также на рекурсивные плитки Вана. Также я посмотрел на текстуры Крейга Рейнольда (Craig Reynold), но не успел нигде их применить.

Также интересными показались эти статьи о генерировании миров, генератор карты природы Gozzy, генератор мира donjon, статья о процедурном генерировании дорог, статья о процедурном генерировании городов. Похоже, что прямые скелеты могут пригодиться для определения горных массивов, но как только я увидел, насколько хорошо работает подход с «расстоянием от побережья», мне не нужно было ничего другого. Довольно интересно генерирование 3d-карт в Dwarf Fortress.