естественный поток «воды» через сеть узлов

Question

Надеюсь, это будет достаточно ясно.

У меня есть двухмерная карта, состоящая из плиток, и я хочу, чтобы «вода» проходила по этой карте.Он выходит из трубы на определенную плитку, а затем должен, как вода, заполнить все плитки, чтобы добраться до определенной другой плитки.В настоящее время у меня есть карта, введенная в игру, где каждая плитка является узлом, и каждый узел имеет соединения со всеми соответствующими плитками вокруг него.У меня есть узлы, хранящиеся в отсортированном массиве сначала по x, затем по y.Кроме того, некоторые плитки являются плитками-воротами, которые могут препятствовать прохождению воды через них.Они являются частью одной и той же сетки тайлов узлов и просто помечаются флажком, когда активны.

Проблема в том, как я распределяю воду.

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

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

Так завершается моя дилемма.

Код написан на Python.

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

Answer 1

Это часто встречается в разработке игр — было много выступлений на GDC и статей в журнале Gamasutra/Game Developer именно на эту тему.Я думаю, что лучше всего для ваших целей Йос Стам's'Гидродинамика в реальном времени для игр" с GDC 2003 года.

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

Статья Мика Уэста о гидродинамике поскольку Gamasutra в некотором смысле расширяет статью Стама, что может улучшить производительность, поэтому вы можете начать с этого.

А также есть недавняя статья GameDev, спонсируемая Intel, которая предлагает более полное решение, но он довольно сложен и ориентирован больше на графическую сторону рендеринга в 3d.

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

В этих статьях математические расчеты и алгоритмы излагаются гораздо лучше, чем я мог бы втиснуть в блок Stack Overflow, но есть еще два общих момента, которые я хотел бы отметить:

1. Моделирование воды требует очень больших вычислительных затрат.Поскольку вы работаете на Python, это может привести к реальной проблеме с производительностью — обязательно настройте некоторые средства профилирования вашего алгоритма для поиска горячих точек на случай, если ваш цикл займет так много времени, что убьет частоту кадров.Возможно, вам придется прибегнуть к Числовой Питон чтобы получить быстрые операции с массивами на основе C.
2. В разработке игр гораздо больше математики, чем ожидает большинство людей!

Answer 2

Некоторые эвристики на основе предположений:

• дискретные «капли», занимающие ровно один квадрат каждая
• вода никогда не остается выше одного уровня на данной плитке,
• вода всегда остается непрерывной
• когда барьеры подняты, они как стены
• когда барьеры разрушены, они похожи на открытые площади

Для каждой лужи ведите список краевых квадратов и открытых квадратов рядом с краями.

Когда барьер падает

amend the lists of edge and open squares for any puddles that were touching it

Когда барьер поднимается

if (it was covered)
    pick a non-wall square next to it at random, and add the drop from the barrier there.
amend the lists of edge and open squares for any puddles next to the block

Когда вы добавляете каплю:

if (the square "under" the pipe is empty)
   fill it
else
   consult the list of edge square associated with the pool under the pipe, and select the one closest to the pipe (if more than one is closest, choose from the candidates at random), and fill it.  
amend the lists of edge and open squares for the puddle (be prepared to merge with neighboring puddles if necessary)

Когда убираешь каплю

 find the edge (not open!) square farthest from the sink (or randomly select from the equivalent candidates), and empty it
 amend the lists of edge and open squares for the puddle

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

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

Answer 3

Включает ли ваша модель концепцию разности потенциалов или давления?

Скажем, пустая плитка имеет нулевое давление, а полная плитка — давление 10.Если между двумя плитками есть труба, то вода течет для выравнивания давления, а ворота закрывают трубу, и ничего не течет.