Как течет пиксельная вода?

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

Как моделировать поведение воды на двухмерной клеточной доске? На первый взгляд, все довольно очевидно. Задаем для каждой клетки уровень воды (значение с плавающей точкой от 0.0 до 1.0, где 0.0 - клетка суха, а 1.0 - заполнена полностью). Далее необходимо перераспределять воду по мере ее поступления. Для этого нужно понять: как течет вода? В реальном мире она подчиняется довольно сложной системе уравнений Навье-Стокса.

Система уравнений Навье-Стокса (Уравнения Навье — Стокса — Википедия) состоит из двух уравнений: уравнения движения и уравнения неразрывности. Для несжимаемой жидкости (которой с хорошей степенью точности является вода), она дополняется уравнением несжимаемости. Она описывает движение воды, иными словами, полностью предсказывает изменение состояние жидкой сплошной среды в любую единицу времени. Если мы хотим смоделировать движение жидкости, нам достаточно решить это уравнение и подставить в него наши параметры (начальную скорость и положение жидкости в каждой точке), и мы сможем с легкостью предсказать развитие: что и куда течет.

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

Чтобы понять, что это означает на практике, рассмотрим гораздо более простую задачу: пусть нам надо смоделировать падение персонажа на землю в одномерном пространстве. Да, любой физический движок умеет это делать, но как это работает? Ускорение свободного падения равно g, а значит уравнение падения очень простое: v'(t) = g. Штрих здесь означает производную по времени. Любой, кто знаком с основами интегрирования, может решить это уравнение: v(t) = v0 + g * t (где v0 - начальная скорость). Пойдя еще дальше, и вспомнив, что x'(t) = v(t), где x - координата тела, и применив свои навыки интегрирования еще раз, получим: x(t) = x0 + v0 * t + g * t^2 / 2 (x0 - начальное положение тела). Это и есть аналитическое решение уравнения падения. Подставив в него значение момента времени t, мы с уверенностью можем найти положение падающего тела.
Более подробно в Вики: Свободное падение — Википедия
Если бы с уравнениями Навье-Стокса дела обстояли столь же просто, мы смогли бы расчитать движение воды, просто подставив значение времени t в его решение. К сожалению, как мы уже знаем, этого решения пока найдено не было.
Использует ли физический движок типа box2d аналитические решения для расчета движения тел? Нет, не использует. Причина этого заключается в том, что сложность их нахождения с ростом числа взаимодействующих тел растет столь быстро, что для задачи тяготения двух тел (например Земли и Луны) аналитическое решение существует, а для задачи тяготения трех тел (например, Земли, Луны и Солнца) - нет. Повторимся аналитическое решение не то, чтобы не удается найти, доказано, что его не существует в принципе!

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

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

Код:

повторять:
 максимальный_поток = 0
 для каждой клетки доски:
  оставшаяся_масса_воды = масса_воды_в_клетке
  для всех соседей клетки:
   для направления в порядке ВНИЗ
    если масса_воды_в_соседней_клетке < МАКСИМАЛЬНО_ВОДЫ_С_УЧЕТОМ_СЖАТИЯ:
     поток = (МАКСИМАЛЬНО_ВОДЫ_С_УЧЕТОМ_СЖАТИЯ - масса_воды_в_соседней_клетке) / 2
   для направления ВПРАВО, ВЛЕВО:
    поток = (оставшаяся_масса_воды - масса_воды_в_соседней_клетке) / 2
   для направления ВВЕРХ:
    если оставшаяся_масса_воды > МАКСИМАЛЬНО_ВОДЫ_С_УЧЕТОМ_СЖАТИЯ:
     поток = (оставшаяся_масса_воды - МАКСИМАЛЬНО_ВОДЫ_С_УЧЕТОМ_СЖАТИЯ) / 2
   оставшаяся_масса_воды -= поток
   масса_воды_в_соседней_клетке += поток
   максимальный_поток = макс(максимальный_поток, поток)
пока максимальный_поток > МИНИМАЛЬНЫЙ_ДОПУСТИМЫЙ_ПОТОК

В Dwarven Skykeep принятые следующие константы:

МАКСИМАЛЬНО_ВОДЫ = 1.0
МАКСИМАЛЬНО_ВОДЫ_С_УЧЕТОМ_СЖАТИЯ = 1.01
МИНИМАЛЬНЫЙ_ДОПУСТИМЫЙ_ПОТОК = 0.01

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

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



Наш трейлер