Симуляция воды на рельефе. 1 ЧАСТЬ (сохраняем)

Я в какой-то степени одержим генерацией рельефа, играми на основе сетки, симуляциями и всем подобным. И все это часто включает в себя воду — или, по крайней мере, кажется естественным, что она там есть.

Допустим, вы создаете карту для стратегической игры и не хотите, чтобы границы карты просто заполнялись непроходимой пустотой (как в старых RTS-играх). Разве не было бы лучше, если бы границы заполнялись водой, как на этой карте из одного из моих заброшенных проектов?

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

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

Надеюсь, я вас убедил: наличие воды — это действительно здорово. (Хотя это и так очевидно).

Но у воды есть проблемы.

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

Однако в моей игре изменение рельефа необходимо:

Ну, эм... потому что так сказано в моих дизайнерских документах! Обещаю, это точно было где-то на той странице... или на этой...

Если серьезно, то у меня действительно есть несколько причин:

Допустим, у вас есть озеро или даже просто лужа. Вы выкопали его край и открыли свободный проход для воды. Что будет делать вода?

Есть несколько простых вариантов:

Среди этих решений ни одно меня не устраивает. Они хороши в качестве запасных вариантов, если не удастся найти что-то лучшее, но как основная модель воды они слишком... скучные. Dwarf Fortress ближе всего к тому, что мне нужно, но их модель слишком блочная и рассчитана на 3D, а мне это не особо нужно (об этом позже).

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

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

∇(масса ⋅ скорость) = 0

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

Кстати, теоретически превратить динамическую модель в статическую довольно просто: достаточно добавить уравнения вида

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

Конечно, я мог бы просто сдаться. В конце концов, важно помнить, что я не создаю симулятор реальности — я делаю игру и могу гнуть ее правила, как захочу. Однако я никак не мог отделаться от мысли, что какая-то хитрая комбинация простых формул должна сработать в моем случае. И я оказался прав!

Кстати, если при чтении этого раздела вам захотелось закричать "TIMBERBOOOORN" семь раз — угадайте что? Они используют точно такую же модель, которую я собираюсь описать.

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

Я уже четыре раза сказал «в моем случае», но что именно я имею в виду? Вот список требований, которым должна соответствовать моя симуляция воды:

Как вы уже догадались, я нашел такую модель — и именно об этом будет эта статья.

Но сначала...

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

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

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

Мне не нужна супердетализированная симуляция — мне нужна быстрая и разумная!

Метод Stable Fluids от Джоса Стама — одна из самых известных работ по симуляции жидкостей в компьютерной графике. Однако он тоже решает другую задачу.

Этот метод работает с полным объемом жидкости, а не с поверхностным слоем, как мне нужно. Представьте себе закрытый резервуар, заполненный водой, вместо воды, текущей по рельефу.

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

Я даже сам реализовывал Stable Fluids, и это очень веселая и впечатляющая модель, но она решает не ту задачу. Она основана на полном уравнении Навье-Стокса, в то время как нам на самом деле нужны уравнения мелкой воды (shallow water equations).

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

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

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

Обратите внимание, что здесь нигде не упоминается "количество воды". Есть плотность массы, но все уравнения делят на нее, так что мы не можем задать нулевую плотность или четкую границу между жидкостью и воздухом. (Впрочем, это можно сделать с помощью методов particle-in-cell и marker-and-cell, если я правильно помню.)

Даже в самой простой форме эти уравнения содержат давление ppp, которое неизвестно и меняется со временем, но при этом нет уравнения, описывающего, как именно оно эволюционирует! То есть нет уравнения вида

Вместо этого эволюция давления встроена в другие уравнения неявно. Это связано с шагом проекции в методе Stable Fluids.

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

Именно этим и занимаются уравнения мелкой воды (Shallow Water Equations, SWE).

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

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

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

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

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

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

Тогда обновление значений может выглядеть так:

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

Такие сетки называют коллокированными (collocated), и я всегда читаю это как co-located (то есть все величины хранятся в одном месте).

И вот проблема: коллокированные сетки — отвратительный выбор для гидродинамики!

Одна из причин — неудобные конечные разности.

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

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

Но в случае гидродинамики у нас есть векторные величины (скорость воды в разных направлениях), и тогда коллокированные сетки приводят к проблемам:

Поэтому вместо коллокированных сеток в вычислительной гидродинамике обычно используют сдвинутые сетки (Staggered Grids).

О них — дальше.

В уравнениях гидродинамики часто встречаются первые производные, например, выражения вида:

«Ускорение жидкости пропорционально разнице между количеством воды слева и справа».

Как вычислить это с помощью конечных разностей?

Если наивно дискретизировать уравнения гидродинамики, это приводит к сильной нестабильности:

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

Вопрос: как правильно учитывать потоки воды через границы ячейки?

Если граница скорости проходит по центру ячейки, то потоки слева и справа накладываются друг на друга, создавая паразитные осцилляции.

Решение? Использовать сдвинутую (staggered) сетку!

Об этом — дальше.

Общая скорость в этой ячейке равна нулю! Это абсурд, так как здесь явно происходит значительное течение воды.

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

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

Вот изображение:

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

Итак, если мы хотим использовать N × N квадратную сетку в качестве области симуляции, нам потребуется хранить:

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

Наконец, мы подошли к самому методу, который я использую для симуляции воды на рельефе. Этот метод называется виртуальные трубы (Virtual Pipes), потому что он основан на предположении, что водяные ячейки соединены воображаемыми трубами с некоторым радиусом.

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

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

Кстати, в дальнейшем я буду использовать array(i, j), чтобы обозначать элемент массива с индексами i,ji, ji,j. В моем C++ коде двумерные массивы имеют перегруженный оператор () для доступа к элементам, так как многомерный operator[] доступен только с C++23.

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

Поток воды через эту завесу зависит от:

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

Хранение потока вместо скорости имеет важные преимущества:

Всё это создаёт много сложностей, но работа с потоками вместо скоростей решает все эти проблемы элегантно.