[Перевод] Снова о диаграммах Вороного
Как написано в недавнихпостах блога, я боролся за то, чтобы получить в своей игре Dragons Abound нужную детализацию береговых линий. Моё разочарование возникло во время реализации барьерных островов. Чтобы создать как можно более узкий остров, я делал их шириной в одну локацию — на рисунке ниже каждая локация является треугольником Делоне:
Это было довольно неприятно — и из-за того, что остров оказался очень изломанным, и потому, что размер деталей был слишком большим. Казалось, что при сильном увеличении количества треугольников Делоне (то есть при сильном уменьшении их размеров) эта проблема решится —, но нужная мне плотность треугольников приводила к сбою браузера.
Я решил эту проблему, отделив контуры суши от внутреннего представления локаций. Это позволило мне отрисовывать острова любого размера или формы, вне зависимости от лежащей в их основе сетки локаций:
Итак, проблема решена! Это позволило мне отрисовать барьерные острова, и поскольку береговая линия не обязана теперь следовать базовой сетке, при необходимости более детализированной береговой линии можно было создать её обычным образом, а затем добавить детали.
Но… как мы добавляем детали к береговой линии? Это не так просто, как можно подумать. Так как я хотел создать фрактальную береговую линию, я рассмотрел возможность использования фракталов, добавляющих детали к береговой линии:
Поэкспериментировав с настройками, я смог добавить к береговой линии множество деталей и интересностей. Однако система не могла создавать чего-то, напоминающего такую карту:
Шум Перлина может создавать подобный вид рельефа при наличии достаточно детализированной базовой сетки, но можно ли это сделать без хранения значений высот рельефа в базовой сетке с нужным разрешением (ведь я знаю, что это сломает мой код)? Пока я не разобрался, как это делать. Береговая линия по сути является путём через все точки, в которых функция шума Перлина имеет нулевое значение. Хотя мы можем узнать непосредственно из функции шума Перлина значение в конкретной локации (X, Y), нельзя найти (допустим) «все локации, в которых функция имеет нулевое значение». То есть сложно увидеть, как провести контур высот без базовой сетки.
Хуже того то, что я спросил Амита, как это сделать, и он тоже не знал ответа. Одно дело, когда этого не могу сказать я, но когда ответа не может дать даже такой умный человек, я начинаю думать, что этого сделать нельзя. Печально. Я могу придать береговой линии любую нужную мне форму, но не могу получить нужные формы без очень детализированной базовой сетки.
Так как же мне получить сетку высокого разрешения, не сломав при этом код?
Одно из решений, которое пришло мне в голову, напоминает то, что сделал Azgaar в своём генераторе карт — ячейки Вороного переменного размера. Основная идея заключается в повышении плотности (и уменьшении размера) базовой сетки вдоль береговых линий и сохранение меньшей плотности в океанах и других областях, не требующих детализации. При таком варианте у меня будет много ячеек сетки только в тех областях, где нужна детализация. Это изменение будет довольно сложно реализовать в Dragons Abound, но я хочу его обдумать. С другой стороны, сам Azgaar был не очень доволен таким подходом, поэтому это тоже нужно учитывать.
Параллельно я хотел исследовать причины сбоя браузера при обработке кучи треугольников. Инструменты разработчика в Chrome предоставили мне подробную информацию о производительности. Я ни в коем случае не являюсь специалистом в использовании этих инструментов, но многие функции достаточно просты, чтобы их мог понять любой. На случай, если вы хотите узнать общее количество занятой в программе памяти, во вкладке Memory есть информация о текущем занятом объёме:
В данном случае я открыл веб-страницу Azgaar, и она занимает скромные 20 МБ памяти. Можно использовать этот инструмент, чтобы узнать, сколько памяти занимает Dragons Abound, и определить момент, в котором происходит сбой вкладки.
Базовый параметр, управляющий разрешением лежащей в основе сетки в Dragons Abound умно назван «npts» (Number of Points). На каждую единичную площадь карты (карты регионов, которые я обычно использую в качестве примеров, имеют площадь в 1 единицу) Dragons Abound создаёт данное количество локаций базовой сетки. Обычно я использую для 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% локаций около нуля. Все эти локации попадают в интервал (допустим) [-0.05, 0.05], и тогда я могу использовать значение 0.05 для определения масштаба добавляемого шума.
(Я пишу «определения», потому что по разным причинам нельзя просто использовать 0.05. Сначала нужно превратить сушу в воду и наоборот. Прибавление (допустим) 0.002 к -0.05 не внесёт в карту никаких видимых изменений. То есть интервал должен быть гораздо больше 0.05, если я хочу превращать значительную долю локаций с высотой -0.05 из воды в сушу. Во-вторых, функции шума не являются равномерно распределёнными, поэтому с масштабом 0.05 функция шума никогда на самом деле не вернёт значение 0.05! На практике сложность в том, что масштаб должен быть гораздо больше, чем наибольше значения, которые мы хотим видеть достаточно часто.)
Поэкспериментировав, я нашёл значение, добавляющее в береговые линии сложность, при этом не меняя их значительно, а также создающее небольшое количество островов:
Как всегда эти параметры в игре могут принимать интервал значений, поэтому я могу получать широкий диапазон карт: от карт с достаточно плавными побережьями до карт с изломанными и сложными берегами. Позволив программе подбирать значения, я получил следующий результат:
Береговые линии находятся на более плавной стороне, но по-прежнему есть большая часть добавленной сложности среднего масштаба и достаточное количество новых островов.
При реализации фрактальных береговых линий я реализовал возможность управления уровнем фрактализации с помощью функции шума, поэтому некоторые области будут иметь плавные побережья, а другие — сложные. Я подумал, что это сильно повысит интересность карты, и она будет выглядеть менее «сгенерированной», поэтому добавлю эту возможность и здесь. Идея довольно проста — прежде чем добавлять на карту шум береговой линии, я умножаю его на выходные данные второй функции шума, которые варьируются от нуля до 1. Там, где эта функция мала, к береговым линиям будут добавляться мелкие детали. Там, где она близка к 1, дополнительные детали будут добавляться полностью. Подбирая масштаб второй функции шума, которая медленно варьируется на протяжении карты, я получу некоторые области со сложными береговыми линиями, часть с простыми, и логичные переходы между ними:
Здесь я сделал береговые параметры большими значениями, чтобы разница была нагляднее. Мы видим дикий, изрезанный берег на северо-востоке, и более плавные пляжи на западе.
Итак, мы значительно улучшили генерацию береговой линии, но я по-прежнему не могу полностью генерировать карту с таким количеством треугольников Делоне. Я показываю только контурные карты, потому что многие другие элементы карты сломаны. Надо это исправить.
Остальная часть программы плохо работает с таким количеством треугольников Делоне (при текущих параметрах их 256K). Основная проблема в том, что Dragons Abound отрисовывает сушу и воду отрисовкой всех отдельных треугольников, а такое количество элементов SVG приводит к сбою браузера. Поэтому мне пришлось полностью отключить рендеринг суши. Вероятно, есть способ обойти эту проблему, но наличие такого количества треугольников создаёт другие проблемы. Например, некоторые части программы должны обрабатывать всю карту. Каждая из них становится при 256K локаций в шестнадцать раз медленнее, чем при 16K локаций. Также в коде есть части (например, новая модель осадков), которые ломаются при работе с таким количеством треугольников. А от создания такой детализированной сетки локаций мы ничего не выигрываем — после генерации береговой линии от добавленной сложности ничего не улучшается. Поэтому хотя я и мог просмотреть программу и исправить те области, где большое количество локаций слишком замедляет или ломает код, кажется проще уменьшать разрешение сетки карты после создания береговых линий.
Как сказано выше, Azgaar уже провёл работу по изменению разрешения сетки Вороного, лежащей в основе карты. Он реализовал возможность изменения разрешения сетки на лету в процессе генерации, то есть он мог (например) увеличивать плотность локаций вдоль побережья. Однако локальное изменение плотности имеет свои недостатки — в частности, оно создаёт вдоль границы треугольники странной формы. Позже Azgaar высказал мнение, что система слишком сложна и не стоит усилий. Azgaar обычно знает, о чём говорит, поэтому я поверю ему на слово, и не буду пытаться переупаковать готовую сетку.
Вместо этого я создал вторую сетку с нужным (более низким) разрешением, а затем скопировал карту высот на эту новую сетку. (Не забывайте, что Dragons Abound теперь хранит береговые линии отдельно от сетки, поэтому после их создания они больше не зависят от точного соответствия сетке. Сделать это немного сложновато. Так как исходная сетка имеет гораздо большее разрешение по сравнению с новой, многие локации в исходной сетке будут накладываться на одну локацию в новой сетке. Каждая из этих исходных локаций имеет на карте высот разную высоту, как же мне их копировать? Использовать среднее? Или максимальную (минимальную) высоту?
Для начала я просто выберу одну случайную локацию, чтобы просто посмотреть, сработает ли новая сетка с остальной частью программы:
Всё получилось на удивление хорошо. Мелкий баг возникает тогда, когда новые локации не помечены должным образом как суша, берег или вода, но после решения этой проблемы генерация карты заработала отлично. Нужно подчистить мелкие недочёты (например вышедшая на воду метка Palmanor), но в целом всё выглядит хорошо. Даже крошечные островки получились красивыми.
В конце концов я решил, что при снижении разрешения сетки Вороного каждая локация будет средним базовых локаций. Это кажется разумным решением, и при необходимости это всегда можно будет изменить. На этом изображении показано, как в результате береговые линии оказались отделёнными от готовой сетки:
Подведём итог: в Dragons Abound во время генерации карты высот используется сетка треугольников Делоне очень высокого разрешения. После её завершения Dragons Abound определяет береговые линии, отслеживая в карте высот переходы от отрицательных к положительным значениям. Затем игра копирует сетку высокого разрешения в сетку гораздо меньшего разрешения, усредняя локации, попадающие в одну локацию новой сетки. Далее сетка высокого разрешения отбрасывается, и оставшаяся часть процедурной генерации и визуализация продолжаются на сетке низкого разрешения. Интересный вопрос заключается в том, имеет ли какую-то ценность на этом этапе использование сетки Делоне; возможно, стоит просто выполнять копирование в сетку шестиугольников или нечто подобное.
