Simulação de água sobre terreno

 (lisyarus.github.io)
2 pontos por GN⁺ 2025-02-08 | 1 comentários | Compartilhar no WhatsApp
  • Em jogos em que é possível cavar e aterrar o terreno, lagos, rios e poças precisam escoar para novos contornos, então é necessária uma simulação de água baseada em grade que seja rápida e estável
  • O objetivo é um modelo 2D de campo de altura que use a mesma grade do terreno em escala de cerca de 1 m, preservando a água, com estabilidade controlável e custo de atualização linear
  • Smoothed Particle Hydrodynamics e Stable Fluids são voltados, respectivamente, para fluidos de partículas em alta resolução e volumes fechados de fluido, o que não combina com a necessidade de processar rapidamente uma superfície livre sobre o terreno
  • A abordagem adotada de virtual pipes armazena a altura da água e o fluxo entre células em uma staggered grid, e resolve aceleração do fluxo, escalonamento do escoamento e atualização da coluna d’água com alguns loops sobre arrays 2D
  • Com dt e g adequados, o resultado parece água, mas ainda há a limitação de não haver inércia nem difusão de velocidade, então um jato rápido que entra em um lago não continua se propagando por ele

Por que a água é difícil em jogos com modificação de terreno

  • Em jogos de estratégia ou simulações de cidade e vila, a água pode servir como fronteira natural e como base para navegação, pesca, comércio, combate naval, abastecimento, transporte e estética
  • Se o jogador pode alterar diretamente o terreno, a dificuldade de tratar a água sobe bastante
    • Ao escavar recursos como terra, areia e argila, é mais natural que o terreno seja removido junto
    • Pedra e minério metálico também combinam mais com mineração por escavação do terreno do que como objetos soltos sobre a superfície
    • Se não for possível construir em encostas, é preciso nivelar o terreno antes de construir
    • Também é possível oferecer a própria modificação do terreno como ferramenta de expressão criativa
  • A situação central é: quando se cava a borda de um lago ou poça e se abre um canal, para onde e quanto a água vai escoar

Onde soluções simples falham

  • Algumas alternativas possíveis seriam fixar a água na posição inicial, considerar como água tudo que estiver abaixo de certa altura, limitar o quanto se pode cavar, ou usar um modelo simples de fluxo no estilo Minecraft ou Dwarf Fortress
  • Essas abordagens podem funcionar como solução alternativa, mas são simples demais ou têm um aspecto muito blocado para servirem como modelo principal
  • O modelo de Dwarf Fortress é o mais próximo entre os exemplos, mas foi pensado para 3D, enquanto o problema aqui é principalmente água 2D sobre terreno
  • Timberborn usa um modelo do mesmo tipo discutido aqui

Requisitos desejados para a simulação

  • O modelo de água buscado deveria atender às seguintes condições
    • De preferência operar na mesma grade do terreno
    • Trabalhar em escala média de cerca de 1 m, sem necessidade de simular respingos pequenos
    • Tratar a água como um campo de altura sobre o terreno, sem considerar fluxo vertical nem vazios em seções verticais
    • A água deve escoar, mas não pode desaparecer por erro numérico da simulação
    • A estabilidade precisa ser controlável
    • O custo de cada passo deve ser linear no tamanho da simulação, idealmente com apenas algumas passagens pelos dados

Desalinhamento com simulações de fluidos existentes

  • Smoothed Particle Hydrodynamics produz resultados impressionantes de fluido em alta resolução, mas não é o que este problema pede
    • Partículas de água com tamanho de 1 m podem parecer balões d’água
    • Reduzir o tamanho das partículas aumenta o custo de desempenho
    • O objetivo não é realismo em alta resolução, e sim um modelo rápido e convincente
  • Stable Fluids, de Jos Stam, está mais próximo de um modelo para volumes fechados cheios de fluido, como um tanque
    • É diferente do problema de tratar diretamente uma superfície livre sobre o terreno
    • Em algumas etapas, é preciso resolver iterativamente sistemas lineares esparsos, o que custa caro
    • É uma abordagem para resolver o conjunto completo de Navier-Stokes, enquanto aqui o necessário são as shallow water equations

Shallow water equations e escolha da grade

  • As shallow water equations tratam a camada de água sobre o terreno como uma média na vertical, resultando em equações 2D
  • “Shallow” significa assumir que a dimensão vertical da coluna d’água é muito menor que a escala horizontal de interesse
    • Isso pode valer, por exemplo, quando a profundidade do rio é de alguns metros ou dezenas de metros e a distância relevante está na escala de quilômetros
  • Uma collocated grid comum armazena altura da água e velocidade na mesma célula, mas isso pode causar problemas em dinâmica de fluidos
    • Se derivadas de primeira ordem forem discretizadas de forma ingênua, podem surgir viés direcional ou instabilidade
    • Se há fluxo entrando pela esquerda e direita e saindo por cima e por baixo na mesma célula, a velocidade total pode parecer zero, o que é contraditório
  • A staggered grid armazena valores como altura da água e densidade nas células, e velocidade ou fluxo nas arestas entre células
    • array N x N para altura da água
    • array (N+1) x N para fluxo na direção X
    • array N x (N+1) para fluxo na direção Y

Método de virtual pipes

  • Virtual pipes calcula o fluxo assumindo que as células de água estão conectadas por tubos virtuais
  • Um dos artigos de referência também trata múltiplos níveis de coluna d’água e conexões verticais; outro foca principalmente em erosão hidráulica, mas esses objetivos não são considerados aqui
  • São armazenados 3 valores
    • water: altura da coluna d’água em cada célula
    • flowX: fluxo total de água entre células adjacentes na horizontal
    • flowY: fluxo total de água entre células adjacentes na vertical
  • Em vez de velocidade, armazena-se fluxo (flow, flux)
    • O fluxo pode ser visto como o volume de água que atravessa por unidade de tempo
    • Entre células vazias, o fluxo naturalmente é definido como 0
    • Velocidade é fluxo dividido pela área da seção transversal, então quando quase não há água podem surgir problemas de 0/0 ou de limiar

As 3 etapas de cada passo

  • Um passo da simulação é dividido em três etapas
    • Aceleração do fluxo: aumenta o fluxo entre células vizinhas de acordo com a diferença de altura da superfície da água
    • Escalonamento do escoamento: se a água que sai de uma célula for maior que a quantidade realmente disponível, reduz os fluxos de saída
    • Atualização da coluna d’água: soma ou subtrai a altura da água em cada célula conforme os fluxos vizinhos

  • Aceleração do fluxo

    • Quando duas células adjacentes têm alturas de água diferentes, o fluxo acelera da mais alta para a mais baixa
    • O fluxo é atualizado nas arestas internas nas direções X e Y, usando g, dt, dx e dy
    • A área da seção transversal A do tubo virtual só aparece multiplicada por g, então em usos simples ela pode ser incorporada a g
    • O atrito pode ser adicionado reduzindo o fluxo a cada passo
    • O artigo recomenda um coeficiente pow(friction, dt)
    • Para usar um valor mais intuitivo, pode-se empregar pow(1-friction, dt)
    • friction=0 pode ser interpretado como atrito máximo, eliminando totalmente o fluxo anterior, e friction=1 como ausência de atrito
    • Quanto maior dt, mais rápida a simulação, mas maior o risco de instabilidade
    • Em simulação de fluidos, a condição de Courant-Friedrichs-Lewy é importante
    • Na prática, dt precisa ser reduzido até a simulação ficar estável; os valores usados ficaram em torno de 0.001 a 0.01

  • Atualização da coluna d’água

    • Cada célula adiciona ou remove água observando os quatro fluxos adjacentes
    • Entradas pela esquerda e por baixo, flowX(x,y) e flowY(x,y), são somadas
    • Saídas pela direita e por cima, flowX(x+1,y) e flowY(x,y+1), são subtraídas
    • É a etapa que efetivamente move água entre as células com base no fluxo calculado

  • Escalonamento do escoamento

    • Se o fluxo for grande demais, a altura da água em alguma célula pode ficar negativa após a atualização
    • Soma-se apenas o fluxo de saída de cada célula para verificar se a água removida em um passo excede a quantidade disponível
    • Se a remoção for grande demais, todos os fluxos de saída dessa célula são reduzidos na mesma proporção para manter a altura da água em 0 ou mais
    • Essa etapa é o principal mecanismo de estabilização para impedir quantidades negativas de água

Terreno, condições de contorno e viscosidade

  • O terreno entra na etapa de aceleração do fluxo usando a altura da superfície da água em vez da altura da coluna d’água
    • altura da superfície da água = terrain(x,y) + water(x,y)
    • Uma célula com terreno mais alto pode ter a superfície mais alta e empurrar água mesmo com a mesma altura de coluna d’água
  • As condições de contorno são definidas implicitamente pelos valores de fluxo na borda
    • flowX(0,y), flowX(N,y), flowY(x,0) e flowY(x,N) correspondem às bordas
    • Se forem 0, funcionam como paredes
    • Valores de entrada adicionam água, e valores de saída removem água
    • Em água sobre terreno, uma borda de saída onde a água some ao chegar ao limite do mapa pode ser natural
    • Onde um rio cruza a borda, pode-se usar uma borda de entrada para manter o fluxo do rio
  • Os fluxos de contorno precisam ser redefinidos no início de cada passo da simulação
    • Isso acontece porque o escalonamento do escoamento pode alterar esses fluxos e fazer uma borda de saída se comportar como parede
  • O artigo também inclui um termo de viscosidade que reduz o fluxo conforme a altura da água
    • A ideia é que lâminas rasas de água se movem com mais dificuldade por forças internas, enquanto lâminas mais profundas se movem com mais liberdade
    • Isso pode ser útil para algo como fluxo de magma
    • Não foi usado para água, e em grandes escalas de terreno o efeito da viscosidade é quase irrelevante

Fluxo de implementação e formato de desempenho

  • O código completo segue esta ordem
    • inicialização dos fluxos de contorno
    • pré-cálculo do coeficiente de atrito pow(1-friction, dt)
    • aceleração do fluxo em X
    • aceleração do fluxo em Y
    • escalonamento do escoamento para evitar água negativa
    • atualização da coluna d’água
  • Quase toda a simulação termina em 4 loops sobre arrays 2D com fórmulas simples
  • O código completo de atualização em C++ pode ser visto em water_2d.cpp
  • Os exemplos em vídeo vêm do simulador de água em WebGPU divulgado alguns dias atrás; as partículas no vídeo são apenas para visualização e não participam da simulação
  • Ao encontrar bons valores para dt e g, o resultado parece estável, atende aos requisitos e soa convincente como água

Limitações restantes

  • Este modelo não tem inércia nem difusão de velocidade
    • Se um jato rápido entra em um lago, ele não continua se propagando pelo interior do lago e acaba se espalhando em todas as direções
    • Se a altura da água for igual, dois fluxos paralelos em direções opostas podem coexistir sem interagir
  • Quando a água entra pela primeira vez em uma região, surgem ondulações que podem parecer um pouco estranhas

Expansão para grades hexagonais e triangulares

  • O jogo-alvo não usa grade quadrada, e sim uma grade triangular regular
  • Uma grade triangular pode ser vista como a dual de uma grade hexagonal
    • Se conectarmos os centros de hexágonos adjacentes, obtemos uma grade triangular regular
    • Isso é semelhante ao uso do axial coordinate system no dual de uma grade hexagonal pointy-top no artigo da Red Blob Games sobre hexagonal grids
  • A grade triangular também pode ser armazenada em um array 2D comum, ligeiramente inclinado
  • As alturas da coluna d’água ficam armazenadas nos vértices da grade para facilitar o render da superfície
  • O fluxo é dividido em três direções
    • fluxo na direção X
    • fluxo na direção Y
    • fluxo na direção Z
  • Em uma grade de vértices N x N, usam-se os seguintes arrays
    • array (N+1) x N para fluxo em X
    • array N x (N+1) para fluxo em Y
    • array (N+1) x (N+1) para fluxo em Z, sem usar os valores bottom-left e top-right
  • Em comparação com a grade quadrada, basta adicionar o fluxo em Z às condições de contorno, aceleração, escalonamento do escoamento e atualização da água
  • A parte mais difícil é não errar a indexação
  • O código C++ para grades triangulares e hexagonais pode ser visto em water_2d_hex.cpp
  • Essa abordagem pode ser um pouco mais isotrópica que a grade quadrada

Leituras relacionadas

1 comentários

 
GN⁺ 2025-02-08
Opiniões no Hacker News

  • Há vídeos do Coding Adventure com outra abordagem para simulação 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

  • Um dos motivos pelos quais a simulação hidrológica é difícil em jogos com geração procedural é que, quando a água se acumula, ela afeta as células ao redor, e esse efeito continua se propagando para outras células vizinhas
    A geração procedural muitas vezes combina bem com paralelização, mas justamente em áreas infinitas, onde a paralelização parece ser mais necessária, é difícil paralelizar esse tipo de cálculo corretamente
    Não vi esse tema ser muito explorado, e entre as pessoas que trabalham com isso gosto especialmente de https://nickmcd.me. É um dos melhores terrenos procedurais que já vi
    Ainda assim, esse trabalho também tem a área limitada por causa do projeto da simulação. Como possível solução, parece melhor gerar proceduralmente divisores de bacias hidrográficas que não possam ser rompidos e então simular a bacia inteira em paralelo de uma vez
    É um problema muito interessante, mas está fora do meu domínio de conhecimento, então fico mais como observador

    • Se tiver curiosidade, vale procurar pelos conceitos de “domínio de influência” e “domínio de dependência” usados na área de resolução de equações diferenciais parciais
      Eles se referem à região que pode influenciar o valor em um determinado ponto e à região que o valor desse ponto pode influenciar, e têm relação direta com o que foi dito acima. Em alguns casos, é possível conhecer essa região antecipadamente
    • Sinceramente, vale muito a pena conferir https://nickmcd.me. É realmente incrível
    • É uma pergunta interessante. Talvez seja possível colocando uma borda ao redor de cada região e assumindo uma velocidade máxima de propagação do efeito, ou seja, causalidade
      Por exemplo, para simular passos de 10 horas, coloca-se uma borda de 10 células de grade. Calculam-se 10 passos em cada região e depois sincroniza-se o estado da borda com outras simulações de borda calculadas em paralelo, repetindo o processo
    • Fiquei surpreso ao saber que Nick tem apenas 25 anos

  • Fugindo um pouco do tema, lembrei da parte do texto que dizia que a manipulação do terreno era necessária para coletar recursos
    Sempre achei que Animal Crossing resolveu isso de forma bem inteligente e eficiente sem manipulação de terreno. Ao cortar uma árvore, você recebe toras, mas só uma quantidade determinada, o que na prática cria um tempo de recarga
    Dá para oferecer feedback e a sensação de recursos finitos sem uma manipulação de terreno cara. Claro que isso não serve para todos os jogos e funciona melhor em mapas pequenos, mas vale considerar. Se não for algo essencial para o jogo, muitas vezes é melhor não fazer manipulação de terreno

    • O texto também abordava essa estratégia na forma de rochas de minério de ouro colocadas ao redor
      Como método de entrega de recursos, é algo padrão, mas o tempo de recarga não elimina o problema de recursos infinitos; apenas reduz a velocidade. E também é meio tedioso e de pouco impacto

  • O texto se aprofunda nesse tema de forma limpa, e foi bom ver Timberborn mencionado
    Estou completamente viciado nesse jogo ultimamente, então recomendo muito se você ainda não jogou. O fluxo de água baseado em física parece outro personagem dentro do jogo, e descobrir como represar a água para usar em motores e abastecer plantações é o loop central do gameplay

  • Foi divertido e muito bem executado. O maior risco ao desenvolver algo assim é perder horas apenas ajustando parâmetros enquanto se olha para resultados bonitos
    Isso me fez lembrar de quando implementei por conta própria hidrodinâmica baseada em GPU para um trabalho acadêmico em 2011. Eu lidava com sangue, um fluido que corre sobre uma superfície, ou seja, tecido; simulava em 2D e depois projetava sobre uma malha levando em conta a gravidade e a inclinação da superfície
    Também publiquei um vídeo curto no YouTube: https://youtu.be/4vGrNc-GGW8

  • Muito legal
    Recentemente experimentei uma ideia parecida com a ajuda do o3-mini-high. Expliquei a ideia do algoritmo, e ele implementou e renderizou em 3D sem intervenção manual. Porém, usei vários prompts
    https://3d-water-sim.netlify.app/
    Ainda não está perfeito, porque parei de mexer, mas a cada iteração estava melhorando bastante. O interessante é que, para gerar o terreno, ele não buscou algo em uma CDN ou similar; implementou corretamente do zero uma versão funcional do ruído de Perlin

    • Fico curioso se, ao fazer esse tipo de experimento, o objetivo é diversão ou aprendizado. Se o objetivo for aprendizado, também fico curioso se ler este texto ainda parece valioso, mesmo que você não tenha implementado diretamente
      É uma pergunta sobre a diferença entre a jornada e o destino

  • A parte do texto que diz: “Este modelo não tem inércia nem difusão de velocidade. Mesmo que um fluxo rápido de água entre em um lago, ele não se propaga mais para dentro do lago e se espalha em todas as direções, ignorando a inércia acumulada. Se o nível da água for o mesmo, dois fluxos paralelos em direções opostas podem não interagir entre si” parece que poderia ser resolvida tirando a média com as 6 setas de fluxo vizinhas na mesma direção
    A ideia seria dar pesos maiores às setas da frente e de trás, e pesos menores às setas laterais. Por exemplo, com setas assim
    -a-> -b->
    -c-> -d-> -e->
    -f-> -g->
    New_d = d * (1 - 2*.1 - 4*.01) + (c+e).1 + (a+b+f+b).01
    Aqui, .1 e .01 são pesos escolhidos arbitrariamente e precisariam ser ajustados; também daria para aplicar uma potência, como se faz para reduzir oscilações. Incluindo esse coeficiente, poderia ficar assim
    New_d = d * (1 - 2*.1 - 4*.01 - .001) + (c+e).1 + (a+b+f+b).01

    • A solução correta parece estar mais próxima de adicionar mais uma grade para derivadas de segunda ordem, compatível com a grade original
      grid 0: altura da água em cada célula
      grid 1: fluxo de água em cada aresta, ou seja, a derivada de primeira ordem
      grid 2: aceleração da água em cada célula, ou seja, a derivada de segunda ordem
      Cada grade é a grade dual da anterior e armazena seu valor derivado. Na verdade, talvez nem seja necessário tratar os dados das arestas de forma especial; poderia haver apenas dados nos vértices e tratar tudo puramente como grades duais. O fluxo em uma aresta pode ser derivado como a soma dos fluxos dos dois vértices nas extremidades dessa aresta
      Assim, a altura do fluido é atualizada a partir do fluxo; depois a aceleração é atualizada conforme a velocidade e a quantidade de massa de fluido que entrou na célula; por fim, o fluxo é atualizado com base na aceleração e na altura atual do fluido. Não conheço bem dinâmica de fluidos, mas do ponto de vista de simulação numérica parece fazer sentido, e também permite fluxos diagonais
    • Esse método viola a conservação de momento. Para obter um fluxo realista, é preciso usar a equação de continuidade para conservar a energia do fluxo e fazer com que o cisalhamento se dissipe e se difunda em vórtices
      Como o texto comenta, isso aumenta muito o custo computacional, então é preciso avaliar antes se esse nível de realismo é necessário para o caso de uso real

  • Um resultado tosco que fiz há alguns anos por curiosidade: https://aperocky.com/hydrosim/
    Antes de esse projeto pessoal ir para a prateleira fria do armazenamento, não consegui descobrir como lidar com erosão. Gostei de o autor mencionar essa parte e até incluir equações

  • Recentemente publiquei algo parecido. Inclui geração aleatória de heightfield, transporte de sedimentos e erosão: https://github.com/Ono-Sendai/terraingen

  • Dá para experimentar diretamente uma simulação de enchentes educacional feita por um excelente desenvolvedor da nossa empresa como parte de um projeto de pesquisa
    https://flood.concord.org/
    Para ver um efeito maior, é preciso alterar os valores do modelo na barra de ferramentas inferior
    É uma simulação baseada em células que calcula os valores das células no WebGL com base nas células vizinhas. O shader que faz esse cálculo está aqui
    https://github.com/concord-consortium/flooding-model/blob/ma...