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

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

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


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


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


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

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

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

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


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

Эта система координат независима от того, как будет отображаться карта. Это просто безразмерная система для созданиям мира — город находится в (0.12875, -0.223), граница проходит из (0.337, 0.010) в (0.333, 0.017), и так далее. И хотя нынешние мои региональные карты ограничены диапазоном от 0.5 до -0.5, это не является пределом системы координат. Я могу создать мир за пределами этих границ.

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


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

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

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

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


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

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

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

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


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

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


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

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


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

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


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


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


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

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

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

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

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


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


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

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

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


и:


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

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

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


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

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


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


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

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

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


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

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


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


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

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

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

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

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

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

Третья проблема связана с изображениями и другими загружаемыми ресурсами. В исходном 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 без необходимости повторной генерации мира. (Программист получше меня реализовал бы это как масштабирование и скроллинг.) Кнопка Save PNG сохраняет видимую карту как файл PNG; кнопка Save SVG сохраняет файл SVG всей карты. Кнопка Test It используется для запуска тестового кода, который меняется в процессе разработки разных функций.

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

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

Внеся в предыдущей части различные изменения, теперь я могу генерировать миры, которые гораздо больше предыдущих (до 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 раз быстрее исходной (!). Это очень значительное ускорение, мало повлиявшее на карты. Эксперименты дают понять, что модель не особо чувствительна к размеру шестиугольников, поэтому при необходимости я смогу ещё больше ускорить алгоритм, увеличив размер ячеек.

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