- En juegos donde se puede excavar y rellenar el terreno, los lagos, ríos y charcos deben fluir hacia nuevos límites, por lo que se necesita una simulación de agua basada en grilla que sea rápida y estable
- El objetivo es un modelo 2D de campo de alturas que use la misma grilla que el terreno a una escala de aproximadamente 1 m, y que cumpla con conservación del agua, estabilidad controlable y costo de actualización lineal
- Smoothed Particle Hydrodynamics y Stable Fluids están orientados, respectivamente, a fluidos de partículas de alta resolución y a volúmenes de fluido cerrados, por lo que no encajan con la necesidad de procesar rápidamente superficies libres sobre terreno
- El enfoque elegido de virtual pipes almacena la altura del agua y los flujos entre celdas en una staggered grid, y procesa la aceleración del flujo, el escalado de salidas y la actualización de columnas de agua con unos cuantos bucles sobre arreglos 2D
- Con
dtygadecuados produce resultados que se ven como agua, pero mantiene limitaciones: no hay inercia ni difusión de velocidad, por lo que una corriente rápida no continúa propagándose dentro de un lago
Por qué el agua es difícil en juegos con modificación de terreno
- En juegos de estrategia o simuladores de ciudades y pueblos, el agua puede servir como frontera natural, navegación, pesca, comercio y batallas navales, además de agua potable, transporte y estética
- Si se puede modificar directamente el terreno, la dificultad de manejar el agua aumenta mucho
- Al extraer recursos como tierra, arena o arcilla del suelo, resulta natural que también se elimine el terreno
- Para piedra y minerales metálicos, también encaja mejor un sistema donde se excava el suelo para minarlos, en vez de tratarlos como objetos sobre la superficie
- Si no se pueden construir edificios en pendientes, hay que aplanar el terreno antes de construir
- La modificación de terreno en sí puede ofrecerse como herramienta de expresión creativa
- La situación clave es qué tanto y hacia dónde fluye el agua cuando se abre un cauce excavando el borde de un lago o charco
Dónde no alcanzan las soluciones simples
- Entre los posibles atajos están fijar el agua en su posición inicial, considerar como agua todo lo que esté por debajo de cierta altura, impedir excavar demasiado profundo o usar un modelo de flujo simple al estilo Minecraft o Dwarf Fortress
- Estos métodos pueden servir como alternativas, pero son demasiado simples o demasiado cuadriculados para usarlos como modelo principal
- El modelo de Dwarf Fortress es más cercano que otros ejemplos, pero está diseñado con una premisa 3D; el problema necesario aquí es principalmente agua sobre terreno 2D
- Timberborn usa un modelo como el tratado aquí
Condiciones deseadas para la simulación
- El modelo de agua objetivo debe cumplir estas condiciones
- Conviene que funcione en la misma grilla que el terreno
- La escala promedio es de alrededor de 1 m, y no hace falta simular hasta pequeñas salpicaduras
- El agua se considera un campo de alturas sobre el terreno; no se consideran flujos verticales ni huecos en cortes verticales
- El agua debe fluir y no debe desaparecer por errores de simulación
- La estabilidad debe poder controlarse
- El costo de cada paso debe ser lineal respecto del tamaño de la simulación; idealmente, debe resolverse con unos pocos bucles
Desajuste con simulaciones de fluidos existentes
- Smoothed Particle Hydrodynamics produce resultados de fluidos de alta resolución impresionantes, pero es un problema distinto al que se necesita aquí
- Partículas de agua de 1 m podrían parecer globos de agua
- Hacer las partículas más pequeñas aumenta el costo de rendimiento
- El objetivo no es realismo de alta resolución, sino un modelo rápido y verosímil
- Stable Fluids de Jos Stam se parece más a un modelo que trata un volumen lleno de fluido, como un tanque cerrado
- Es distinto del problema de manejar directamente una superficie libre sobre terreno
- En algunas etapas hay que resolver iterativamente sistemas lineales dispersos, lo que tiene un costo alto
- Es un enfoque que resuelve Navier-Stokes completo, mientras que aquí lo necesario son shallow water equations
Shallow water equations y elección de grilla
- Shallow water equations es un enfoque que promedia verticalmente la capa de agua sobre el terreno y la trata como ecuaciones 2D
- “Shallow” se refiere a la suposición de que el tamaño vertical de la columna de agua es mucho menor que la escala horizontal de interés
- Puede cumplirse, por ejemplo, cuando la profundidad de un río es de varios metros a decenas de metros y la distancia de interés está en kilómetros
- Una collocated grid común almacena la altura del agua y la velocidad en la misma celda, pero eso puede causar problemas en dinámica de fluidos
- Si se discretiza ingenuamente una derivada de primer orden, pueden aparecer sesgos direccionales o inestabilidad
- Si los flujos que entran por izquierda y derecha y salen por arriba y abajo están en la misma celda, surge la contradicción de que la velocidad total parezca 0
- Una staggered grid almacena valores como altura del agua y densidad en celdas, y velocidades o flujos en las aristas entre celdas
- Arreglo de alturas de agua
N x N - Arreglo de flujos en dirección X
(N+1) x N - Arreglo de flujos en dirección Y
N x (N+1)
- Arreglo de alturas de agua
Método de virtual pipes
- Virtual pipes es un método que calcula el flujo suponiendo que las celdas de agua están conectadas por tuberías virtuales
- Uno de los papers referenciados también trata columnas de agua de múltiples niveles y conexiones verticales, y otro se enfoca principalmente en erosión hidráulica (hydraulic erosion), pero aquí se omiten esos objetivos
- Se almacenan 3 valores
water: altura de la columna de agua de cada celdaflowX: flujo total de agua entre celdas adyacentes horizontalmenteflowY: flujo total de agua entre celdas adyacentes verticalmente
- En lugar de velocidad se almacena flujo (flow, flux)
- El flujo puede verse como el volumen de agua que pasa por unidad de tiempo
- El flujo entre celdas vacías se define naturalmente como 0
- La velocidad es el flujo dividido por el área de sección transversal, así que cuando casi no hay agua pueden aparecer problemas de 0/0 o de umbrales
Las 3 etapas de un paso
- Un paso de simulación se divide en tres etapas
- Aceleración del flujo: aumenta el flujo entre celdas según la diferencia de altura de la superficie del agua en celdas vecinas
- Escalado de salidas: si el agua que sale de una celda supera la cantidad que realmente contiene, reduce los flujos de salida
- Actualización de columnas de agua: suma o resta la altura de agua de cada celda según los flujos vecinos
-
Aceleración del flujo
- Si dos celdas vecinas tienen distintas alturas de agua, el flujo se acelera desde la más alta hacia la más baja
- Se actualiza el flujo para las aristas internas en direcciones X e Y, usando
g,dt,dxydy - El área de sección transversal
Ade la tubería virtual solo se usa multiplicada porg, así que en usos simples puede tratarse como si se hubiera incorporado ag - La fricción se agrega reduciendo el flujo en cada paso
- El paper recomienda un coeficiente
pow(friction, dt) - Para usar un valor más intuitivo, se puede usar
pow(1-friction, dt) friction=0puede verse como fricción máxima, que elimina por completo el flujo anterior;friction=1como ausencia de fricción- Cuanto mayor sea
dt, más rápida será la simulación, pero puede volverse inestable - En simulación de fluidos es importante la condición de Courant-Friedrichs-Lewy
- En la práctica, hay que reducir
dthasta que sea estable; los valores usados fueron aproximadamente entre0.001y0.01
-
Actualización de columnas de agua
- Cada celda observa los cuatro flujos vecinos y suma o resta agua
- Los
flowX(x,y)yflowY(x,y)que entran desde la izquierda y desde abajo se suman - Los
flowX(x+1,y)yflowY(x,y+1)que salen hacia la derecha y hacia arriba se restan - Esta es la etapa en la que el agua se mueve realmente entre celdas según el flujo calculado
-
Escalado de salidas
- Si el flujo es demasiado grande, después de la actualización alguna celda puede quedar con altura de agua negativa
- Para cada celda, se suman solo los flujos salientes y se verifica si el agua que se eliminaría en un paso supera la cantidad real que contiene
- Si la cantidad a eliminar es demasiado grande, los flujos salientes se reducen en la misma proporción para mantener la altura del agua en 0 o más
- Esta etapa es el mecanismo clave de estabilización que impide cantidades negativas de agua
Terreno, condiciones de borde y manejo de viscosidad
- El terreno se incorpora en la etapa de aceleración del flujo usando la altura de la superficie del agua en lugar de la altura de la columna de agua
- Altura de la superficie del agua =
terrain(x,y) + water(x,y) - Una celda con terreno más alto tiene una superficie más alta incluso con la misma altura de columna de agua, por lo que el agua puede moverse
- Altura de la superficie del agua =
- Las condiciones de borde se determinan implícitamente por los valores de flujo en el borde
flowX(0,y),flowX(N,y),flowY(x,0),flowY(x,N)corresponden al borde- Si se dejan en 0, funcionan como una pared
- Los valores de entrada agregan agua, y los de salida eliminan agua
- Para agua sobre terreno, puede ser natural un borde de salida donde desaparece el agua en los extremos del mapa
- Las partes donde un río cruza el borde pueden configurarse como borde de entrada para que fluya el agua del río
- Los flujos de borde deben volver a configurarse al inicio de cada paso de simulación
- Porque el escalado de salidas puede cambiar los flujos de borde y convertir un borde de salida en algo parecido a una pared
- El paper también incluye un término de viscosidad que reduce el flujo según la altura del agua
- La idea es que una capa de agua pequeña se mueve con dificultad por fuerzas internas, mientras que una capa grande se mueve con más libertad
- Puede ser útil para cosas como flujo de magma
- No se usó para agua, y a grandes escalas de terreno el efecto de la viscosidad es casi nulo
Flujo de implementación y forma del rendimiento
- El código completo se organiza en este orden
- Inicialización de flujos de borde
- Precálculo del coeficiente de fricción
pow(1-friction, dt) - Aceleración de flujo X
- Aceleración de flujo Y
- Escalado de salidas para evitar cantidades negativas de agua
- Actualización de columnas de agua
- La mayor parte de la simulación se resuelve con 4 bucles que recorren algunos arreglos 2D y fórmulas simples
- El código completo de actualización en C++ puede verse en water_2d.cpp
- Los ejemplos en video vienen del WebGPU water simulator publicado hace unos días; las partículas del video son solo para visualización y no participan en la simulación
- Al encontrar valores adecuados de
dtyg, se ve estable, cumple las condiciones requeridas y produce resultados que parecen agua
Limitaciones pendientes
- Este modelo no tiene inercia ni difusión de velocidad
- Aunque una corriente rápida entre a un lago, no sigue propagándose hacia el interior del lago, sino que se dispersa en todas direcciones
- Si la altura del agua es la misma, pueden existir dos corrientes paralelas en direcciones opuestas sin interactuar entre sí
- Cuando el agua entra por primera vez a una zona, se generan ondas y puede verse algo extraño
Extensión a grillas hexagonales y triangulares
- El juego objetivo usa una grilla triangular regular, no una grilla cuadrada
- Una grilla triangular puede verse como el dual de una grilla hexagonal
- Si se conectan con líneas los centros de hexágonos adyacentes, se obtiene una grilla triangular regular
- Es similar a la forma en que el artículo de Red Blob Games sobre grillas hexagonales usa un sistema de coordenadas axial en la grilla dual de hexágonos con orientación pointy-top
- Una grilla triangular también puede almacenarse en un arreglo 2D común ligeramente inclinado
- La altura de las columnas de agua se almacena en los vértices de la grilla para facilitar el renderizado de la superficie del agua
- El flujo se divide en tres direcciones
- Flujo en dirección X
- Flujo en dirección Y
- Flujo en dirección Z
- En una grilla de vértices
N x Nse usan los siguientes arreglos- Arreglo de flujo X
(N+1) x N - Arreglo de flujo Y
N x (N+1) - Arreglo de flujo Z
(N+1) x (N+1), donde no se usan los valores bottom-left y top-right
- Arreglo de flujo X
- En comparación con una grilla cuadrada, basta con agregar el flujo Z a las condiciones de borde, la aceleración, el escalado de salidas y la actualización de agua
- La parte más difícil es no equivocarse con la indexación
- El código C++ para grillas triangulares y hexagonales puede verse en water_2d_hex.cpp
- Este enfoque puede ser un poco más isotrópico que una grilla cuadrada
1 comentarios
Opiniones de Hacker News
Hay videos de Coding Adventure con otro enfoque sobre simulación de fluidos
Rendering Fluids: https://www.youtube.com/watch?v=kOkfC5fLfgE
I Tried Putting my Fluid Simulation on a Planet: https://www.youtube.com/watch?v=8nIB7e_eds4&t=817s
GitHub: https://github.com/SebLague/Fluid-Sim?tab=readme-ov-file
[0] https://www.youtube.com/playlist?list=PLFt_AvWsXl0dT82XMtKAT...
[1] https://github.com/SebLague/Geographical-Adventures
Una de las razones por las que la simulación hidrológica es difícil en juegos con generación procedural es que, cuando el agua se acumula, afecta a las celdas vecinas, y ese efecto vuelve a propagarse continuamente a otras celdas cercanas
La generación procedural muchas veces se presta bien a la paralelización, pero justamente en regiones infinitas, donde más parece hacer falta paralelizar, este tipo de cálculo es difícil de paralelizar correctamente
No he visto que este tema se haya explorado mucho, y entre la gente que trabaja en cosas relacionadas me gusta especialmente https://nickmcd.me. Es de los mejores terrenos procedurales que he visto hasta ahora
Aun así, ese trabajo también tiene regiones limitadas por el diseño de la simulación. Como posible solución, lo que mejor parece funcionar es generar proceduralmente límites de cuencas hidrográficas que no puedan romperse y luego simular en paralelo toda la cuenca de una sola vez
Es un problema muy interesante, pero queda fuera de mi área de conocimiento, así que lo observo más bien desde afuera
Se refieren a la región que puede influir en el valor de un punto determinado y a la región sobre la que ese punto puede influir, y se conectan directamente con lo mencionado arriba. En algunos casos, esas regiones se pueden conocer de antemano
Por ejemplo, para simular pasos de 10 horas, se deja un borde de 10 celdas de cuadrícula. Se calculan 10 pasos en cada región, luego se sincroniza el estado del borde con las simulaciones de bordes calculadas en paralelo, y se repite
Esto se sale un poco del tema, pero me recordó la parte del artículo donde decía que hacía falta manipular el terreno para recolectar recursos
Siempre pensé que Animal Crossing lo resolvía de forma bastante ingeniosa y eficiente sin manipulación de terreno. Si talas un árbol, obtienes troncos, pero solo una cantidad determinada, y en la práctica aparece un tiempo de reutilización
Sin manipulación de terreno costosa, se puede dar feedback y la sensación de recursos finitos. Claro que no sirve para todos los juegos y encaja mejor en mapas pequeños, pero vale la pena considerarlo. Si no es estrictamente necesario para el juego, muchas veces conviene no manipular el terreno
Como forma de entregar recursos es bastante estándar, pero un tiempo de reutilización no elimina el problema de los recursos infinitos; solo lo ralentiza. Además, es un poco aburrido y tiene poco impacto
Es un artículo que profundiza muy bien en este tema, y me alegró que mencionara Timberborn
Últimamente estoy totalmente enganchado con ese juego, así que lo recomiendo mucho si todavía no lo probaste. El flujo de agua basado en física se siente como otro personaje dentro del juego, y descubrir cómo contener el agua para usarla en motores y abastecer campos es el núcleo del loop de juego
Fue interesante y además estuvo muy bien ejecutado. El mayor riesgo al desarrollar algo así es perder horas ajustando parámetros mientras miras resultados bonitos
Me hizo recordar cuando en 2011 implementé por mi cuenta dinámica de fluidos basada en GPU para un trabajo de investigación. Trataba con sangre, un fluido que corre sobre una superficie, es decir, tejido; la simulaba en 2D y luego la proyectaba sobre una malla teniendo en cuenta la gravedad y la pendiente de la superficie
También subí un video corto a YouTube: https://youtu.be/4vGrNc-GGW8
Realmente genial
Hace poco experimenté con una idea parecida con ayuda de o3-mini-high. Le expliqué la idea del algoritmo y lo implementó y renderizó en 3D sin intervención manual. Eso sí, tuve que usar varios prompts
https://3d-water-sim.netlify.app/
Todavía no está perfecto, porque dejé de tocarlo, pero en cada iteración mejoraba bastante. Lo interesante es que, para la generación de terreno, no tomó nada de un CDN ni algo parecido, sino que implementó correctamente desde cero una versión funcional de ruido Perlin
Es una pregunta sobre la diferencia entre el viaje y el destino
La parte del artículo que dice: “Este modelo no tiene inercia ni difusión de velocidad. Aunque una corriente rápida entre a un lago, no se propaga más hacia el interior del lago y se dispersa en todas direcciones ignorando la inercia acumulada. Si el nivel del agua es el mismo, dos corrientes paralelas que fluyen en direcciones opuestas podrían no interactuar entre sí” parece que podría resolverse promediando con las 6 flechas de flujo vecinas en la misma dirección
La idea sería darles un peso alto a las flechas de adelante y atrás, y uno pequeño a las laterales. Por ejemplo, si hay flechas así:
-a-> -b->
-c-> -d-> -e->
-f-> -g->
New_d = d * (1 - 2*.1 - 4*.01) + (c+e).1 + (a+b+f+b).01
Aquí .1 y .01 son pesos elegidos arbitrariamente, así que habría que ajustarlos, y también se podría introducir una potencia como se hace para reducir las oscilaciones. Incluyendo ese coeficiente, podría quedar así:
New_d = d * (1 - 2*.1 - 4*.01 - .001) + (c+e).1 + (a+b+f+b).01
grid 0: altura del agua en cada celda
grid 1: flujo de agua en cada borde, es decir, la primera derivada
grid 2: aceleración del agua en cada celda, es decir, la segunda derivada
Es una estructura en la que cada cuadrícula es la cuadrícula dual de la anterior y almacena su valor derivado. De hecho, parece que no haría falta tratar los datos de los bordes como algo especial; se podrían usar solo datos de vértices y manejarlo puramente como una cuadrícula dual. El flujo de un borde se puede derivar como la suma de los flujos de los vértices en sus dos extremos
Por lo tanto, se actualiza la altura del fluido a partir del flujo; luego se actualiza la aceleración según con qué velocidad y cuánta masa de fluido entró en la celda; y después se actualiza el flujo a partir de la aceleración y la altura actual del fluido. No sé mucho de dinámica de fluidos, pero desde el punto de vista de la simulación numérica parece correcto, y también permite flujos diagonales
Como dice el artículo, el costo computacional aumenta mucho, así que primero habría que evaluar si ese nivel de realismo es necesario para el caso de uso real
Un resultado rudimentario que hice hace unos años por curiosidad: https://aperocky.com/hydrosim/
Nunca logré resolver cómo manejar la erosión antes de que este proyecto personal terminara en almacenamiento en frío. Me gustó que el autor mencionara esa parte e incluso incluyera las ecuaciones
Hace poco publiqué algo similar. Incluye generación aleatoria de heightfield, transporte de sedimentos y erosión: https://github.com/Ono-Sendai/terraingen
Se puede probar directamente una simulación de inundaciones educativa que hizo un excelente desarrollador de nuestra empresa como parte de un proyecto de investigación
https://flood.concord.org/
Para ver un efecto grande, hay que cambiar los valores del modelo en la barra de herramientas inferior
Es una simulación basada en celdas que calcula los valores de cada celda en WebGL a partir de las celdas vecinas. El shader que hace ese cálculo está aquí:
https://github.com/concord-consortium/flooding-model/blob/ma...