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

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

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

Подход с моделированием капли воды

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

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

Подход предварительного заполнения

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

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

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

Неудачный метод: изоляция каждой долины

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

Я начал с определения потока локально и использовал это, чтобы найти «конечный пункт назначения» для каждой плитки, куда в конечном итоге будет поступать вода. Любой пункт назначения, который не был океаном, я считал дном долины - и с впитавшимися в него плитками у меня было что-то вроде водораздела. Это казалось очень умным, но на самом деле у меня были только участки водоразделов, часто являющиеся частью одной и той же долины.

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

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

Использование двухмерной метафоры

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

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

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

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

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

Алгоритм успешного заполнения

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

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

Вот результат:

Псевдокод

Быстрая версия для кодеров:

elev = a 2-d numeric array
fill = elev
drains = boolean array, where elev == 0
 
timestep loop
  for every cell
    find neighboring cells and store fill values
    set neighbor values to NULL where drain = 0
    get max neighbor value
    if max is higher than self fill
      set fill to max
      set drains to 1
output fill

Интересные особенности вывода

Мы можем рассмотреть, как модель работает на примере острова, который, как напоминание, здесь без воды:

Заливка / Озера

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

Накопление воды

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

Водоразделы

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

Расчет пути

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

Фактически, я не использую эту карту исключительно для определения направления течения реки: во-первых, учитывается местная топография (крутизна), при этом поиск пути используется как средство разрешения конфликтов (после этого используется произвольный индекс ячейки).

Выводы

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

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