Хабрахабр

[Перевод] Снова о диаграммах Вороного

Как написано в недавнихпостах блога, я боролся за то, чтобы получить в своей игре Dragons Abound нужную детализацию береговых линий. Моё разочарование возникло во время реализации барьерных островов. Чтобы создать как можно более узкий остров, я делал их шириной в одну локацию — на рисунке ниже каждая локация является треугольником Делоне:

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

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

Это не так просто, как можно подумать. Но… как мы добавляем детали к береговой линии? Так как я хотел создать фрактальную береговую линию, я рассмотрел возможность использования фракталов, добавляющих детали к береговой линии:

Поэкспериментировав с настройками, я смог добавить к береговой линии множество деталей и интересностей. Однако система не могла создавать чего-то, напоминающего такую карту:

Шум Перлина может создавать подобный вид рельефа при наличии достаточно детализированной базовой сетки, но можно ли это сделать без хранения значений высот рельефа в базовой сетке с нужным разрешением (ведь я знаю, что это сломает мой код)? Пока я не разобрался, как это делать. Береговая линия по сути является путём через все точки, в которых функция шума Перлина имеет нулевое значение. Хотя мы можем узнать непосредственно из функции шума Перлина значение в конкретной локации (X,Y), нельзя найти (допустим) «все локации, в которых функция имеет нулевое значение». То есть сложно увидеть, как провести контур высот без базовой сетки.

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

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

Основная идея заключается в повышении плотности (и уменьшении размера) базовой сетки вдоль береговых линий и сохранение меньшей плотности в океанах и других областях, не требующих детализации. Одно из решений, которое пришло мне в голову, напоминает то, что сделал Azgaar в своём генераторе карт — ячейки Вороного переменного размера. Это изменение будет довольно сложно реализовать в Dragons Abound, но я хочу его обдумать. При таком варианте у меня будет много ячеек сетки только в тех областях, где нужна детализация. С другой стороны, сам Azgaar был не очень доволен таким подходом, поэтому это тоже нужно учитывать.

Инструменты разработчика в Chrome предоставили мне подробную информацию о производительности. Параллельно я хотел исследовать причины сбоя браузера при обработке кучи треугольников. На случай, если вы хотите узнать общее количество занятой в программе памяти, во вкладке Memory есть информация о текущем занятом объёме: Я ни в коем случае не являюсь специалистом в использовании этих инструментов, но многие функции достаточно просты, чтобы их мог понять любой.

В данном случае я открыл веб-страницу Azgaar, и она занимает скромные 20 МБ памяти. Можно использовать этот инструмент, чтобы узнать, сколько памяти занимает Dragons Abound, и определить момент, в котором происходит сбой вкладки.

На каждую единичную площадь карты (карты регионов, которые я обычно использую в качестве примеров, имеют площадь в 1 единицу) Dragons Abound создаёт данное количество локаций базовой сетки. Базовый параметр, управляющий разрешением лежащей в основе сетки в Dragons Abound умно назван «npts» (Number of Points). Обычно я использую для npts значение 16K (16384), и это означает, что каждая локация сетки соответствует примерно 70 квадратным пикселям экрана при стандартном масштабе увеличения.

Разумеется, точный объём занимаемой памяти зависит от карты, но для показанной выше карты с 16K точками нужно примерно 92 МБ:

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

Если удвоить количество точек базовой сетки, то объём памяти увеличится до 138 МБ:

Размер занятой памяти не удвоился, потому что часть этой памяти занимается ресурсами и другими структурами данных, размер которых не поменялся. 16K дополнительных точек «весят» около 50 МБ памяти, то есть каждая точка в результате занимает примерно 3 КБ памяти. Это больше, чем я ожидал, но в целом объём всё равно достаточно скромный. На компьютере с 64 ГБ памяти 150 МБ едва заметны.

Если поймать её раньше, чем она вылетит, и проверить память, то увидим следующее: Выполнив ещё несколько удвоений, я обнаружил, что вкладка с Dragons Abound обычно крашится примерно при 128K точек.

Я предполагал, что вкладка даёт сбой из-за занимаемой памяти, но обычно проблема не в памяти. Почему же вкладка вылетает? Единственная подсказка в том, что вкладка не крашится до завершения карты, и это вероятно показатель того, что сбой возникает во время рендеринга.

Для начала я могу узнать, сколько элементов SVG я создаю. Логично предположить, что создаваемый мной SVG перегружает рендерер браузера, из-за своего объёма или сложности. В D3 я могу получить общее количество созданных элементов SVG с помощью svg.selectAll('*').size().

Прогон с 16K точек и проверка количества элементов SVG показали мне следующее:

32K точек имеют 65457 элементов, а 128K точек — 258823. Каждая точка, добавленная к базовой сетке, добавляет на карту по два элемента. Думаю, я нашёл источник бед.

Суша рендерится отрисовкой каждой базовой локации как заполненного полигона с последующим размытием их всех. Каждая точка базовой сетки добавляет элементы SVG из-за того, как Dragons Abound рендерит сушу (и воду). Это позволяет Dragons Abound придавать суше красивый узор или исопльзовать высоту суши для рендеринга суши с 3D-затенением, как показано здесь:

Можно отключить визуализацию суши и океана, чтобы проверить, сколько элементов SVG создаётся. При 256K точек:

Ого, количество элементов SVG значительно снизилось. Как я и надеялся, теперь карта рендерится без сбоев! То есть если избегать использования сетки для рендеринга суши и воды, можно создавать гораздо более плотную сетку, чем раньше.

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

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

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

Вот острова при увеличении в 300%:

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

Вероятно, придётся заняться настройкой, чтобы получить золотую середину.

Надо найти подходящие параметры шума, подобрать seed, а затем использовать значение шума в каждой локации (x, y) для задания массы суши. В большинстве процедурных генераторов суши для создания карты высот используется шум Перлина. Один из удобных аспектов создания суши заключается в том, что если требуется больше деталей в береговой линии, то можно просто настроить параметры шума.

(Или по крайней мере, создаёт не только таким.) В Dragons Abound для создания суши используется множество разных способов. Однако Dragons Abound не создаёт сушу таким образом. Например, в игре есть процедура для создания острова, которая создаёт маску для острова (обычно эллипс), использует шум для придания эллипсу более естественной формы, а затем применяет различный шум для приблизительного заполнения маски. Хотя все они в той или иной степени используют шум, очень немногие из них создают сушу непосредственно из шума. Поэтому добавление деталей настройкой параметров шума для Dragons Abound не очень подходит. Каждая конкретная карта обычно создаётся сочетанием нескольких различных процедур.

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

Береговая линия — это просто контурная линия, в которой карта высот имеет нулевое значение. Что же означает добавление деталей к береговой линии? Но это должно происходить не совсем случайно, я хочу, чтобы изменения казались естественными. (Значение произвольное, но такой принцип используется в каждом процедурном генераторе суши.) Чтобы сделать эту линию более детализированной, нужно немного смещать сушу рядом с этой контурной линий немного вверх и вниз, чтобы простые береговые линии становились сложнее, части суши выступали в океан и становились островами, и так далее. И на самом деле именно это я сделал в исходном примере, показанном выше. Суммируем всё это, и начинает казаться, что нужно добавить к всей карте небольшое количество шума.

По сути, мне нужно настроить три параметра. Разумеется, это нужно делать аккуратно, чтобы не стереть созданные массы суши и не создать других проблем.

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

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

Однако частота измеряется в координатах функции шума, а не координатах карты! Можно подумать, что это просто сделать (всего лишь измерить мелкий остров и присвоить основной частоте этот размер). Хуже того то, что координаты шума сворачиваются, а многие применяющие шум пользователи даже этого не осознают. Типичная функция шума может иметь в каждой координате интервал от 0 до 255, а карта может иметь в каждой координате интервал от -1 до 1. Перевод из одних единиц в другие и определение подходящих частот запутывает, поэтому обычно проще всего просто поэспериментировать с интервалами частот и выбрать тот, который создаёт элементы карты нужного размера.

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

Для начала я сгенерирую карту-пример без дополнительного шума: Давайте приступим к настройке.

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

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

То есть мне нужен относительно малый масштаб, но непонятно, как подобрать правильное число, потому что в разных картах распределение высот варьируется. Настройка шума — довольно сложная операция, потому что я хочу, чтобы этот шум в основном влиял на сушу и воду примерно при около контурной линии с высотой = 0. Можно взять все абсолютные значения высот на карте, отсортировать их, и найти точку отсечки, выбирающую (допустим) 10% локаций около нуля. Решение заключается в том, чтобы подбирать подходящий масштаб на лету. 05, 0. Все эти локации попадают в интервал (допустим) [-0. 05 для определения масштаба добавляемого шума. 05], и тогда я могу использовать значение 0.

05. (Я пишу «определения», потому что по разным причинам нельзя просто использовать 0. Прибавление (допустим) 0. Сначала нужно превратить сушу в воду и наоборот. 05 не внесёт в карту никаких видимых изменений. 002 к -0. 05, если я хочу превращать значительную долю локаций с высотой -0. То есть интервал должен быть гораздо больше 0. Во-вторых, функции шума не являются равномерно распределёнными, поэтому с масштабом 0. 05 из воды в сушу. 05! 05 функция шума никогда на самом деле не вернёт значение 0. На практике сложность в том, что масштаб должен быть гораздо больше, чем наибольше значения, которые мы хотим видеть достаточно часто.)

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

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

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

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

Здесь я сделал береговые параметры большими значениями, чтобы разница была нагляднее. Мы видим дикий, изрезанный берег на северо-востоке, и более плавные пляжи на западе.

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

Основная проблема в том, что Dragons Abound отрисовывает сушу и воду отрисовкой всех отдельных треугольников, а такое количество элементов SVG приводит к сбою браузера. Остальная часть программы плохо работает с таким количеством треугольников Делоне (при текущих параметрах их 256K). Вероятно, есть способ обойти эту проблему, но наличие такого количества треугольников создаёт другие проблемы. Поэтому мне пришлось полностью отключить рендеринг суши. Каждая из них становится при 256K локаций в шестнадцать раз медленнее, чем при 16K локаций. Например, некоторые части программы должны обрабатывать всю карту. А от создания такой детализированной сетки локаций мы ничего не выигрываем — после генерации береговой линии от добавленной сложности ничего не улучшается. Также в коде есть части (например, новая модель осадков), которые ломаются при работе с таким количеством треугольников. Поэтому хотя я и мог просмотреть программу и исправить те области, где большое количество локаций слишком замедляет или ломает код, кажется проще уменьшать разрешение сетки карты после создания береговых линий.

Он реализовал возможность изменения разрешения сетки на лету в процессе генерации, то есть он мог (например) увеличивать плотность локаций вдоль побережья. Как сказано выше, Azgaar уже провёл работу по изменению разрешения сетки Вороного, лежащей в основе карты. Позже Azgaar высказал мнение, что система слишком сложна и не стоит усилий. Однако локальное изменение плотности имеет свои недостатки — в частности, оно создаёт вдоль границы треугольники странной формы. Azgaar обычно знает, о чём говорит, поэтому я поверю ему на слово, и не буду пытаться переупаковать готовую сетку.

(Не забывайте, что Dragons Abound теперь хранит береговые линии отдельно от сетки, поэтому после их создания они больше не зависят от точного соответствия сетке. Вместо этого я создал вторую сетку с нужным (более низким) разрешением, а затем скопировал карту высот на эту новую сетку. Так как исходная сетка имеет гораздо большее разрешение по сравнению с новой, многие локации в исходной сетке будут накладываться на одну локацию в новой сетке. Сделать это немного сложновато. Использовать среднее? Каждая из этих исходных локаций имеет на карте высот разную высоту, как же мне их копировать? Или максимальную (минимальную) высоту?

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

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

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

Подведём итог: в Dragons Abound во время генерации карты высот используется сетка треугольников Делоне очень высокого разрешения. После её завершения Dragons Abound определяет береговые линии, отслеживая в карте высот переходы от отрицательных к положительным значениям. Затем игра копирует сетку высокого разрешения в сетку гораздо меньшего разрешения, усредняя локации, попадающие в одну локацию новой сетки. Далее сетка высокого разрешения отбрасывается, и оставшаяся часть процедурной генерации и визуализация продолжаются на сетке низкого разрешения. Интересный вопрос заключается в том, имеет ли какую-то ценность на этом этапе использование сетки Делоне; возможно, стоит просто выполнять копирование в сетку шестиугольников или нечто подобное.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть