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

Question

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

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

Проблема в том, как я разгоняю воду.

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

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

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

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

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

Answer 1

Это очень важно для разработки игр - было много выступлений на GDC и тематических статей в журнале Gamasutra / Game Developer. Я думаю, что лучшим для ваших целей является Jos Stam" Динамическая динамика в реальном времени для игр " от GDC 2003 года.

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

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

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

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

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

1. Имитация воды очень затратна в вычислительном отношении. Поскольку вы работаете в Python, это может привести к реальной проблеме производительности - обязательно настройте некоторые средства профилирования вашего алгоритма для поиска горячих точек в случае, если ваш цикл занимает так много времени, что он убивает частоту кадров. Возможно, вам придется прибегнуть к Числовой 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. Если между двумя плитками есть труба, то вода течет, чтобы выровнять давление, ворота закрывают трубу, поэтому ничего не течет.