Хабрахабр

[Перевод] Как я создавал карты континентов для своей игры

image

Часть 1. SVG и системы координат

До недавнего времени размеры карт в моей игре Dragons Abound были фиксированными и несколько недетерминированными. Я считал их «региональными» — не картами всего мира, но его значительными частями, такими например, как западное побережье США или часть Европы. Меня вполне устраивал этот масштаб, но я хотел немного поэкспериментировать с игрой, чтобы посмотреть, смогу ли я генерировать карты целого мира (или хотя бы большего размера). Но прежде чем я приступлю к этому, давайте немного поговорим о картах фэнтези-миров.

Большинство карт фэнтезийных «миров» даже близко не походят на истинный размер. Мир — это большое пространство. Возьмём, например, Средиземье, в котором происходит действие «Властелина колец»:

Хоть и кажется, что на ней запечатлён огромный мир, на самом деле Средиземье создано на основе Европы.

То есть реальная карта «мира» для мира Толкиена будет примерно в 50 раз больше карты Средиземья (!). На самом деле, большинство виденных мной карт фэнтезийных миров отображают территорию размером примерно с континент:

Похоже, что это наибольшая область, которая хорошо визуализируется в стиле фэнтези-карт.

Лучше нацелиться на создание карты континента (или части континента). То есть задача генерации реальных «карт мира» наверно слишком амбициозна. Если нынешние карты Dragons Abound имеют «субконтинентальный» размер, то можно предположить, что нужно генерировать карты в 8-10 раз больше. (Однако всё равно удобнее считать карту имеющей размер «мира».) Так какого же размера должна быть карта?

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

Каждая региональная карта имеет координаты от (-0. Начнём с того, что «мир» региональной карты в данный момент генерируется в пределах единичного квадрата. 5) до (0. 5, -0. 5), а начало координат (0,0) находится в середине региона. 5, 0.

Одна из странностей здесь заключается в том, что ось Y перевёрнута по сравнению с тем, что мы и изучали в школьной геометрии. -0,5 находится вверху карты, а 0,5 — внизу. В компьютерной графике ось Y часто переворачивают. Я слышал, что это объясняют тем, как первые мониторы (телевизоры) выполняли развёртку сверху вниз, то есть первая строка развёртки находилась вверху, следующая сразу под ней, и так далее, то есть индекс Y строк развёртки изменялся от нуля вверху до некоторого положительного числа внизу. Как бы то ни было, в формате SVG (Scalable Vector Graphics) используется та же система координат, поэтому и в Dragons Abound тоже.

Это просто безразмерная система для созданиям мира — город находится в (0. Эта система координат независима от того, как будет отображаться карта. 223), граница проходит из (0. 12875, -0. 010) в (0. 337, 0. 017), и так далее. 333, 0. 5 до -0. И хотя нынешние мои региональные карты ограничены диапазоном от 0. Я могу создать мир за пределами этих границ. 5, это не является пределом системы координат.

Она задаёт истинные координаты, которые будут использоваться для отрисовки графики. Следующая система координат — это то, что в SVG называется viewbox. Например, Dragons Abound в начале устанавливает viewbox в координаты (-500, -500) и он имеет ширину 1000 и высоту 1000:

(На картинке опечатка, вверху оси Y должно быть значение -500, простите.)

То есть. Можно заметить, что в таком случае преобразование между первой и второй системами координат заключается всего лишь в умножении всего на 1000. чтобы что-то отрисовать, игра находит координаты этого объекта, умножает их на 1000, и отрисовывает в этих координатах SVG.

Но на самом деле я не хочу отрисовывать линию из (0, 0) в (250, 250) на экране компьютера. То есть я могу использовать координаты viewbox, чтобы допустим отрисовать линию из (0, 0) в (250, 250). Это был бы огромный труд. Это бы означало, что если я захочу отобразить карту в другой точке экрана, то мне придётся изменять координаты всех объектов карты и перерисовывать их.

Viewport — это та часть страницы, в которой должна отрисовываться графика (на веб-странице это элемент <svg>). Чтобы управлять координатами отображения графики на экране, в SVG есть третья система координат, называемая viewport. Расположение — это координаты левого верхнего угла viewport. Он имеет ширину, высоту и расположение. То есть если бы я отображал карту во viewport с координатами (30, 100), который имеет высоту и ширину 800, то система координат viewport выглядела бы так:

В SVG системы координат viewbox и viewport соединены друг с другом, а переходом между ними занимается сам SVG. Мы просто рисуем в системе координат viewbox, и всё отрисованное отображается в соответствующем месте viewport. (Возникают некоторые проблемы при создании viewbox и viewport с разным соотношением сторон. Тогда объекты или отсекаются, или растягиваются, в зависимости от значения атрибута preserveAspectRatio. Рекомендую вообще этого не делать.)

10, 0. Подведём итог: город, расположенный в координатах мира (0. 33) отрисовывается в координатах (100, 330) и показывается на экране в (110, 764).

Теперь вы можете понять, почему это может сбивать с толку!

Предположим, что в первой системе координат я сгенерирую мир, находящийся в пределах от -0. Что произойдёт, если я изменю каждую из этих систем координат? 25 по каждой оси. 25 до 0. Тогда получившийся мир будет в четыре раза меньше обычного мира и заполнит только среднюю часть viewport:

(Также можно заметить артефакты по краям, которые обычно скрыты.) Аналогично, если я удвою размер первой системы координат (СК), то большую часть карты мы не увидим, потому что она будет находиться за краями viewport.

Ну, если я также удвою соотношение между первой СК и viewbox (с 1000 до 2000), то особо ничего не изменится. Что произойдёт, если я удвою размер viewbox? Если соотношение останется равным 1000, то карта снова уменьшится вдвое.

Однако на этот раз карта имеет исходную площадь 1x1. Мы снова можем заметить артефакты по краям, которые обычно скрыты (например, выпуклые части лесов). Также можно увидеть, что паттерн океана неверен — должно быть, я жёстко задал некоторые допущения о размере viewbox. Кроме того, похоже, что компас располагается не на углу карты, а на углу viewbox.

И наоборот, если я уменьшу размер viewbox вдвое, то это создаст эффект зума карты:

Здесь мы видим только среднюю четверть карты. Это не очень удобный способ выполнения зума, потому что при отображении только половины карты создаются некоторые проблемы — например, маркер города «South Owenson» вышел за пределы экрана. Кроме того, это удваивает размер шрифтов и прочего, что мне не нужно.

Пока viewbox центрировался на карте, но это не обязательно. Более полезный аспект viewbox — изменение точки начала координат. Например, я могу сдвинуть карту вправо, центрировав viewbox на точке в левой части карты:

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

Она выглядит как любая другая карта, но на самом деле это только центральная часть более крупной карты. То есть теперь я могу изменять viewbox, чтобы переносить в окно обзора другие части карты:

Здесь я сдвинул viewpoint влево, поэтому мы видим часть мира к востоку от исходного вида. Некоторые названия на карте изменились, потому что Dragons Abound выполняет некоторые функции (например, даёт названия объектам) на основании того, видимы ли они. Мне нужно будет изменить это, чтобы при перемещении viewbox карта оставалась постоянной. Однако позже я смогу перемещать viewbox по крупной карте и генерировать региональные карты любой нужной области. То есть я могу генерировать и отображать большие карты размером с континент, но также могу генерировать региональные карты областей в пределах крупной карты.

Первая — это абстрактная СК для объектов мира. Подведём итог: в игре используется три системы координат. Третья — это viewport, она управляет тем, где на экране будет отрисовываться карта. Вторая — это viewbox, она определяет видимую область мира. Чтобы отображать на экране больше, нужно расширить viewbox. Для отрисовки большего мира мне нужно расширить первую СК. Также я могу сдвигать viewbox, чтобы отображать разные части большого мира.

Часть. Делаем карты постоянными

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

Проблема с размещением названий, которую я описал в предыдущей части, очевидно заметна на этих двух видах одной карты:

Вот тот же мир, только вид сдвинут влево:

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

Но здесь есть только одно исключение, мешающее давать наименования всем последующим объектам. Посмотрев на код, я обнаружил, что почти всем объектам даются названия в зависимости от их видимости. Причины этого весьма запутанны. В нашем случае исключение в том, что Dragons Abound генерирует только видимые береговые линии. Чтобы избежать этого, я просто сгенерировал только видимую береговую линию. На самом деле вдоль всего края мира существует «береговая линия», но создание этой линии разрушает часть логики программы, потому что она заключает в себя весь мир. Вместо этого мне нужно прекратить генерировать береговые линии тогда, когда я приближаюсь к настоящему краю карты. Теперь, когда карта может расширяться далеко за пределы viewport, это решение не выглядит хорошим. (Который я по-прежнему оставляю за пределами экрана, чтобы скрыть проблемы на краях.)

После устранения этой проблемы названия на двух картах остаются постоянными:

и:

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

Так получилось, потому что Dragons Abound на самом деле считает, что область океана — это остров. Если внимательно приглядеться к предыдущей карте, то можно увидеть, что область океана рядом с нижней центральной частью карты имеет висящую метку «Meb Island». Алгоритм сбивает с толку изменение, которое я внёс в генерацию невидимых береговых линий, и чтобы избегать подобных проблем, это нужно исправить. Не буду вдаваться в технические подробности, но на удивление сложно отличать острова от озёр, когда они выходят за пределы карты.

Теперь давайте учетверим размер карты и покажем в окне карты только её четверть:

В целом всё выглядит неплохо (на карте есть интересная система рек, большое озеро, но можно заметить, что города очень редки. Так получилось потому, что Dragons Abound генерирует 10-20 городов. Такой интервал хорошо подходит для мира обычного размера, но плох, когда размер в четыре раза больше. Поэтому интервал нужно менять в соответствии с относительным размером мира. Вероятно, это нужно сделать в нескольких местах.

Вот та же карта после устранения проблемы:

Теперь на карте более логичное количество городов и посёлков, но это демонстрирует нам ещё одну проблему. Можно заметить множество лишних названий по краям карты, например, Nanmrummombrook, Marwynnley и Noyewood в левом нижнем углу. Так происходит, потому что код размещения метод пытается поместить их туда, где они видимы. Раньше этой процедуре никогда не приходилось волноваться о метках за пределами экрана, потому что в картах регионального размера обычно виден весь мир. Но теперь могут существовать города и другие объекты, расположенные за пределами экрана. Поэтому мне нужно добавить в процедуру размещения меток логику, не пытающуюся создать метки для невидимых объектов карты.

Теперь картина более логична. Справа Cumden едва отображается на карте, но метка всё равно расположена там, где он видим.

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

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

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

Выполнив отладку, я устранил самые мешающие из них, что позволило мне создавать карты ещё больше. К счастью, при профилировании производительности генерации больших карт я заметил, что большую часть процессорного времени отнимают очевидные проблемы. Вот вся карта размера 4x:

Выполнен зум на 25% размера. Похоже, что приблизительно таков максимальный размер карты, который может отображать Chrome. Процедура генерации мира может обрабатывать карты и большего размера, но пытаясь их отобразить, браузер аварийно закрывается. Похоже, что в этом смысле Firefox более функционален; он может отображать карты в 9 раз больше от исходного размера. Вот часть такой карты — я оставил её в полном размере, поэтому можете открыть её в отдельном окне, чтобы лучше осознать размер и детализацию.

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

Лучшее решение заключается в сохранении самого SVG, чтобы его можно было открыть в программе наподобие Inkscape.

К счастью, я нашёл FileSaver.js и его можно использовать для сохранения SVG непосредственно в файл, а затем открыть его в Inkscape, создав таким образом очень большое изображение. Раньше я мог вырезать и вставлять SVG карты в Inkscape, но SVG для карт мира насколько велики, что при попытке вырезать браузер вылетает!

При попытке открыть эти карты в Inkscape я сталкиваюсь с парой проблем. По крайней мере, теоретически.

В частности, если в контуре не указан цвет заливки, то браузеры предполагают, что заливки нет; Inkscape предполагает, что контур залит чёрным. Первая проблема — допущения Inkscape отличаются от допущений Chrome и Firefox в том, как открывать SVG. Это можно исправить, указав в необходимых местах «fill: none», чтобы контуры одинаково отображались и в браузере, и в Inkscape. Поэтому когда я открываю сохранённый SVG в Inkscape, он почти полностью чёрный, потому что самый верхний слой карты не содержит цвета заливки.

Похоже, что Inkscape создаёт маски только с одним элементом, и плохо обрабатывает маски с несколькими элементами. Вторая проблема — у Inkscape есть ошибки в обработке масок. Обойти эту проблему можно, сгруппировав все элементы каждой маски игры в один (необязательный) элемент «group». Dragons Abound создаёт множество масок с несколькими элементами.

В исходном SVG ссылки на них указываются в относительном виде, например, «images/background0.png». Третья проблема связана с изображениями и другими загружаемыми ресурсами. Когда я беру тот же SVG и открываю его в Inkscape, эти относительные пути обрабатываются как URL «file:» и Inkscape выполняет поиск ресурсов относительно папки, в которую был сохранён SVG. Мои исходники упорядочены таким образом, что используемый мной отдельный веб-сервер может находить эти ресурсы в указанных местах. Эту проблему легко можно обойти, сохраняя SVG в папку, в которой уже есть ресурсы в нужных местах; это может быть та же корневая папка, что используется веб-сервером, или другое место, в котором есть копии ресурсов по тем же (относительным) путям.

В Dragons Abound используются и веб-шрифты, и локально хранящиеся шрифты; те и другие в формате WOFF2. Четвёртая проблема — шрифты. Когда тот же файл открывается в игре, он ищет шрифты в системном каталоге шрифтов, и похоже, что никаким образом нельзя указать другой каталог шрифтов. В браузере они применяются к тексту с помощью стиля CSS «font-family», и перед генерацией карты все возможные шрифты загружаются на веб-страницу, чтобы быть готовыми к использованию. Однако это не так просто, как кажется, потому что названия шрифтов должны совпадать, а в Windows нет простых способов изменения названия шрифта. Простое решение (по крайней мере, на машине, где я занимаюсь разработкой) — установка используемых игрой шрифтов в системный каталог шрифтов. Более портируемое решение заключается в встраивании в карты SVG-шрифтов. Но, разумеется, такая схема не будет работать на компьютерах, на которых не установлены все нужные шрифты. Это будет в моём TODO-списке.

В конце концов я пришёл к такому интерфейсу генерации карт:

Поля ввода Extent задают общий размер мира, где 1x1 — это размер исходных карт. Размер vbx (viewbox) определяет величину фрагмента мира, отображаемого на карте; на скриншоте он тоже имеет значение 1x1, то есть карта будет отображать весь мир. Поля vbx center задают расположение центра карты в мире; 0, 0 — это центр мира. Наконец, параметры SVG задают количество экранных пикселей на 1 единицу размера viewbox; при значении 775 карта 1x1 будет отображаться на экране в размере 775x775 пикселей. Это удобно, когда я создаю очень большую карту. Задавая параметру низкое значение (например, 150 пикселей) я могу уместить крупную карту на экране целиком.

Кнопка Generate работает именно так, как можно догадаться; кнопка Display просто отображает часть мира, то есть я могу сгенерировать мир, а затем отображать отдельные его части, изменяя параметры viewbox без необходимости повторной генерации мира. Изменяя эти шесть параметров, я могу управлять размером мира и той долей мира, которая отображается на карте. Кнопка Test It используется для запуска тестового кода, который меняется в процессе разработки разных функций. (Программист получше меня реализовал бы это как масштабирование и скроллинг.) Кнопка Save PNG сохраняет видимую карту как файл PNG; кнопка Save SVG сохраняет файл SVG всей карты.

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

Часть. Формы суши

Внеся в предыдущей части различные изменения, теперь я могу генерировать миры, которые гораздо больше предыдущих (до 8 раз больше) и сохранять их как большие графические изображения:

(Откройте изображение в отдельном окне, чтобы увидеть карту в полном разрешении 4800x2400 во Flickr.)

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

Эта карта — просто хаос из островов и швейцарского сыра суши.

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

Это огромная континентальная масса суши, но тут довольно много странных форм суши, и в целом мир выглядит не совсем «реальным». (Хотя кому-то такой мир покажется вполне подходящим для фэнтези.) Так какие же формы должна иметь карта «мира»?

Большинство виденных мной карт фэнтезийных миров отображают большой островной континент (с небольшими островами вокруг), например такой, как эта карта Анделена:

Или полуостров континента, как на этой карте Ангоруна:

Время от времени получается карта, полностью состоящая из суши или нескольких островных континентов, но они скорее являются исключениями из правила.

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

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

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

Это легко исправляется маскированием суши вместо круга эллипсом (искажённым), взятым по размерам карты:

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

Вот та же система управления границей с более логичными искажениями:

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

Раньше у меня были карты размером только 1x1, поэтому размеры паттернов океана и суши подогнаны под эти карты. Внимательный читатель, изучивший предыдущую карту, мог заметить, что паттерны океана и суши останавливаются посередине карты. (В SVG есть способ выполнения тайлинга паттерна, но в Chrome он содержит баг, поэтому использовать его я не могу.) Это хорошая функция, потому что теперь я могу использовать меньшие паттерны суши и океана, которые будут тайлиться автоматически. На картах большего размера мне нужно вручную тайлить паттерны по карте, поэтому я добавил эту функцию. Не знаю, почему я не реализовал её раньше!

Итак, теперь островные континенты работают нормально, и мы перейдём к реализации «полуостровных» континентов — карт, в которых континент появляется на карте с её края.

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

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

Разумеется, это не гарантирует того, что масса суши будет очень интересной, да и вообще окажется единой:

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

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

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

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

Часть 4. Модель ветра

Как и сказал, размер континентов на картах Dragons Abound начал демонстрировать нереалистичные паттерны погоды и биомов. В этом примере видно, что лес выстраивается вдоль преобладающего направления ветра:

Причина не в сломанном коде; скорее, модели погоды и биомов слишком просты, и при большом масштабе это становится очевидным. Чтобы справиться с этими проблемами, я начал с пересмотра модели ветра.

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

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

В идеале сетка должна состоять из равных областей, равноудалённых от своих соседей. Какую сетку мне использовать? И это описание похоже на сетку шестиугольников.

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

Я немного поискал в сети подсказки, и каждая ссылка возвращала меня к странице о сетках шестиугольников Амита Патела (перевод на Хабре). Следующий шаг — нужно определить, как представить сетку шестиугольников в моей программе. Амит объясняет лучше, чем я, поэтому если что-то будет непонятно, то прочитайте его страницу. Вероятно, с неё и надо начать; неплохо также сначала изучить сайт Red Blob Games, если вы ищете информацию об реализации игровой механики.

Проще всего хранить её как двухмерный массив, то мне нужна возможность привязки ячеек сетки к массиву. Первый выбор, который предстоит сделать — способ хранения сетки шестиугольников. Тут есть множество вариантов (прочитайте страницу Амита), но я буду использовать то, что он называет odd-r:

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

Например, если я ищу шестиугольную ячейку (3, 3), то какими будут её соседи? Сделав выбор, теперь я должен научиться привязывать индексы к сетке шестиугольников. И так далее. Если каждая ячейка имеет ширину 5 пикселей, то какими будут координаты центра ячейки (3, 3)? Разбираться с этим может оказаться сложно, поэтому я рад, что Амит сделал это за меня.

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

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

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

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

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

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

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

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

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

Можно использовать такое решение — брать высоту отсутствующих треугольников как среднее от их соседей, или как максимум от их соседей.

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

Основная идея модели ветра заключается в симуляции некоторых ветров (пассатов) и распространении их по всей карте, пока они не достигнут состояния неподвижности. Теперь, когда я наложил сетку шестиугольников на карту, можно приступить к реализации модели ветра. На уровне шестиугольников (или уровне локаций, если я делаю это на треугольниках Делоне) это включает в себя два этапа:  (1) суммируем все ветра, входящие в текущий шестиугольник, и (2) определяем, как суммированный ветер покидает шестиугольник.

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

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

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

Но что, если ветер не дует напрямую на соседнюю ячейку?

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

Один из вариантов — сохранять направление исходного ветра: Также необходимо принять решение о направлении распространившегося ветра.

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

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

Что должно случиться, когда на пути ветра встаёт гора? Ещё одна сложность возникает при рассмотрении рельефа.

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

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

Есть два основных варианта. Теперь давайте поговорим о том, как представить векторы. Во-первых, вектор может быть представлен как значения X и Y, например так:

Если мы отрисовываем вектор, начиная с (0, 0), то (X,Y) являются координатами конечных точек. Такая запись позволяет очень просто суммировать векторы. Мы просто суммируем все значения (X,Y) и получаем новый вектор:

Другой вариант — использование угла и длины вектора:

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

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

Пока выглядит хорошо.

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

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

Например, если вектор ветра имеет угол 22 градусов:

тогда 38/60 значения распространяется в ячейку справа, а 22/60 значения вектора — в ячейку внизу справа. Если векторы представлены в виде пары значений X и Y, то распространить их можно, умножив каждое значение исходного вектора на долю (например, на 22/60), а затем прибавив его к вектору ветра в новом шестиугольнике.

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

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

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

  1. Ветер отворачивается от препятствий.
  2. Ветер замедляется, когда поднимается вверх, и ускоряется, опускаясь вниз.

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

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

По-прежнему сохраняется большая доля движения ветра, вызванного рельефов, но больших пробелов и долин сильного ветра стало меньше.

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

Как видите, теперь ветер над Breeches начал немного рассеиваться вниз.

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

Вот, как всё это выглядит:

Теперь мы видим, что часть ветра, дующего через высокие горы в центральной части острова, оказалась отсечённой. И наоборот — появилось несколько новых ветров в западной части острова, где воздух движется с относительно высокой суши в море. (Это береговой бриз! Хотя на самом деле не совсем: механизм там другой.)

Вот их сравнение (старые ветра слева, новые — справа): Теперь я могу подставить новый ветер в уже имеющийся алгоритм осадков.

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

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

Получилось ли у меня? Смысл всего этого заключается в ускорении и упрощении генерации ветра, чтобы можно было добавить на континентальные карты новые поведения ветра. Оказалось, что новая модель в 15-20 раз быстрее исходной (!). Я выполнил профилирование исходной модели ветра и новой модели на основе шестиугольников. Эксперименты дают понять, что модель не особо чувствительна к размеру шестиугольников, поэтому при необходимости я смогу ещё больше ускорить алгоритм, увеличив размер ячеек. Это очень значительное ускорение, мало повлиявшее на карты.

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

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

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

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

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

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