[Перевод] Генерация барьерных островов
В декабрьских новостях об урагане Флоренс часто упоминались Внешние отмели — ряд барьерных островов на побережье Северной Каролины:
Барьерные острова — это плоские или глыбистые участки песка, формируемые волнами и прибоем параллельно побережью материка. Они часто имеют вид длинных цепочек, которые могут тянуться на многие десятки миль. Барьерные острова обычно разделены небольшими приливными протоками, и могут формировать лагуны между островами и материком.
По данным Википедии, барьерные острова могут закрывать до 15% побережья, поэтому можно ожидать увидеть их на большинстве фэнтезийных карт, но на самом деле они довольно редки. А из-за природы шума их почти никогда не бывает на процедурно генерируемых картах, в которых для создания рельефа используется шум.
Чтобы понять, почему это так, давайте взглянем на «ванильную» карту острова:
По сути, это круг, искажённый небольшим количеством низкочастотного шума, добавленного для разбиения круглой формы. Давайте теперь попробуем использовать шум, чтобы разбить побережье и сформировать прибрежные острова. Вот тот же остров с добавлением низкочастотного шума:
У него есть заливы и мысы. Элементы рельефа довольно большие, потому что я использовал низкочастотный шум, который меняется медленно. Однако шум недостаточно силён, чтобы создать острова. Давайте немного его усилим:
Теперь мы создали несколько островов, но они по сути являются круглыми пятнами, не обязательно протянувшимися вдоль побережья. Можно добавить высокочастотный шум:
Это может дать нам очень изломанные береговые линии и небольшие острова вдоль побережья, но ничего, напоминающего барьерный остров.
Единственная причина этого в том, что шум не согласован по x и y, поэтому хотя в целом шум не случаен, создаваемые им формы случайны:
Для некоторых вещей это хорошо, но для создания конкретной формы, например, острова вдоль побережья, не подходит.
Как и в других случаях, когда мне нужно было сгенерировать определённую форму или область, необходимо создать маску требуемой формы, а затем использовать внутри маски шум. (Также можно использовать шум для искажения маски и придания ей более естественной формы.) Барьерные острова — это, по сути, длинные тонкие области, смещённые относительно побережья. Поэтому давайте создадим маску этой формы.
Начнём с того, что зададим часть побережья, на которой будет расположен барьерный остров. Это можно сделать, выбрав случайную точку на побережье, и вторую точку пониже, которые помечены на рисунке красной линией в правом верхнем углу:
Чтобы начать создавать барьерный остров, я могу просто взять прямую линию между этими двумя точками и спроецировать её немного наружу, в воду. Это даст мне очень прямой и неестественно выглядящий остров, но можно исказить его форму, чтобы скрыть это. Настоящая проблема заключается в том, что остров не будет следовать береговой линии. Вероятно, для большинства прямых участков побережья это будет выглядеть нормально, но покажется странным на извилистых побережьях. Лучше реплицировать береговую линию и сделать её основой формы острова.
Для этого мне нужно создать копию береговой линии, а затем спроецировать её в океан перпендикулярно береговой линии. У меня уже есть процедура для вычисления перпендикуляров (нормалей) к ломаным ещё с тех пор, когда я реализовывал рукописные линии, а мои береговые линии всегда проходят в одинаковом направлении, поэтому всё довольно просто:
Или кажется простым. Давайте посмотрим, что случится, если я спроецирую береговую линию немного дальше наружу (чтобы создать другую сторону маски острова) на менее плавной части береговой линии:
Два отрезка спроецированной линии пересекаются друг с другом и создают на полигоне устрашающую «восьмёрку». Это так называемая проблема параллельных кривых. Мы не можем просто сместить берег на какое-то расстояние, необходимо также решить проблемы, возникающие из-за острых внутренних и внешних углов.
Я поискал код на Javascript для решения этой проблемы, но единственный найденный пример (отсюда) потрясающе сбоил даже на довольно простых образцах. Поэтому я написал собственный. В целом решение заключается в том, чтобы смещать каждую точку по нормали, но затем проверять, создаёт ли новая точка отрезок, пересекающий какой-нибудь из уже существующих отрезков. Если да, то мы отсекаем петлю и вставляем новый отрезок, состоящий из точки пересечения и новой точки. В проверенных мной тестовых примеров эта система сработала для моих требований достаточно хорошо.
Итак, теперь я могу генерировать простые маски (без петель) для островов:
Это слишком равномерно, поэтому я искажу контуры:
Контуры могут в некоторых точках касаться берега, но это нормально, такое часто встречается у барьерных островов.
Следующий этап — заполнение контура сушей, но прежде чем я этим займусь, хочется сделать острова длиннее и добавить логику избегания пересекающихся островов на случай создания нескольких барьерных островов на одной береговой линии.
Теперь давайте попробуем добавить сушу. Для этого я подниму высоту любой локации суши (которые являются треугольниками Делоне) над уровнем моря:
Здесь стоит заметить пару аспектов. Во-первых, в левом верхнем углу есть довольно успешный барьерный остров. Однако непохоже, что остров хорошо заполняет полигон. Множество треугольников суши «включено» из-за наличия их центров внутри полигона. Это добавляет в форму острова случайность. Во-вторых, можно заметить, что два других острова были так близки к побережью, что просто слились с ним. Поскольку здесь я хочу создавать острова, то мне не нужно, чтобы такое происходило слишком часто, поэтому я настрою генерацию для получения большего водного зазора между береговой линией и островом. (Позже я добавлю проверку, чтобы этого не происходило.)
Одна из приятных особенностей составляющих сушу неправильных треугольников заключается в том, что они естественным образом создают приливные протоки, типичные для барьерных островов. Плохо в них то, что обычно они создают острова-пятна, выглядящие как искажённые жемчужины на нитке. Они не очень похожи на барьерные острова, а если взять много отдельных треугольников, то выглядят они очень неестественно.
Если я увеличу ширину островов, оба эффекта исчезают, и я получаю более естественные острова, но без приливных проток:
Но мне хотелось бы научиться генерировать очень узкие острова. Ещё один подход заключается в (значительном) увеличении количества локаций мира для повышения разрешения:
Так мы можем получить впечатляюще тонкие и детализированные острова, но это значительно увеличивает время и память, необходимые для создания карты.
В обоих этих методах есть хорошая вероятность того, что некоторые части острова будут сильно неровными:
Это происходит, потому что контур пересекает две стороны (а иногда и все три стороны) лежащих в основе треугольников Делоне. Это неотъемлемая проблема использования триангуляции Делоне в генерации карт, но обсуждают её почему-то редко! Такое происходит на береговых линиях в моей игре не очень часто, потому что для уменьшения количества таких случаев я намеренно добавил этап сглаживания, но этот этап имеет тенденцию к уничтожению узких островов. Потенциальное решение заключается в создании чуть более широких островов и в использовании сглаживания — при правильной настройке так можно получить более тонкие острова без множества артефактов треугольников:
Однако при таком подходе всё равно есть ограничения на то, насколько узкими могут быть острова. Кроме того, это означает, что мы никогда не получим действительно фрактальные береговые линии.
Иногда алгоритм сглаживания приводит к разбиению длинного барьерного острова на несколько мелких (как в левом нижнем углу изображения выше), но удобно было бы иметь опцию, позволяющую делать это принудительно:
Единственное, что остаётся — дать островам названия и нанести их на карту. Единственный тонкий аспект здесь в том, что я не хочу давать названия всем островам в цепи барьерных островов. В реальных цепях барьерных островов у отдельных островов часто бывают названия, что приводит к хаосу на карте:
Поэтому при создании барьерного острова я учитываю всю дугу и прикрепляю к ней одно название, даже если в результате генерация разбивает дугу на несколько островов:
Обычно барьерные острова называют «отмелями» (Banks) или «валами» (Bars), поэтому эти слова встречаются в вариантах названий.
На этом примере показана потенциальная проблема с барьерными островами:
Здесь барьерный остров был создан внутри залива. Это нелогично (кроме того, приводит к пересечению названий). Чтобы избежать этого, я могу использовать свою логику распознавания заливов, и пропускать эти участки береговой линии. Вероятно, в этом методе нет защиты от дурака, но для данной карты он работает хорошо:
