Simulation de l’eau sur un terrain

 (lisyarus.github.io)
2 points par GN⁺ 2025-02-08 | 1 commentaires | Partager sur WhatsApp
  • Dans les jeux où l’on peut creuser et remblayer le terrain, les lacs, rivières et flaques doivent pouvoir s’écouler vers de nouvelles frontières ; il faut donc une simulation de l’eau sur grille rapide et stable
  • L’objectif est un modèle 2D en champ de hauteur, à une échelle d’environ 1 m, utilisant la même grille que le terrain, tout en assurant la conservation de l’eau, une stabilité contrôlable et un coût de mise à jour linéaire
  • Smoothed Particle Hydrodynamics et Stable Fluids sont respectivement adaptés aux fluides particulaires haute résolution et aux volumes de fluide fermés, ce qui ne correspond pas au besoin de traiter rapidement une surface libre sur un terrain
  • La méthode virtual pipes retenue stocke la hauteur d’eau et les flux entre cellules sur une staggered grid, puis traite l’accélération des flux, la mise à l’échelle des sorties et la mise à jour des colonnes d’eau avec quelques boucles sur des tableaux 2D
  • Avec des valeurs appropriées de dt et g, on obtient un résultat visuellement crédible, mais il reste une limite : l’absence d’inertie et de diffusion de vitesse empêche un jet rapide de continuer sa propagation dans un lac

Pourquoi l’eau est difficile dans un jeu avec modification du terrain

  • Dans les jeux de stratégie ou les simulations de ville et de village, l’eau peut servir de frontière naturelle, permettre la navigation, la pêche, le commerce et les batailles navales, et jouer un rôle pour l’eau potable, le transport ou l’esthétique
  • Si l’on peut modifier directement le terrain, la difficulté du traitement de l’eau augmente fortement
    • Quand on extrait de la terre, du sable ou de l’argile, il est plus naturel que le terrain lui-même soit retiré
    • Pour la pierre et les minerais métalliques aussi, il est plus cohérent de miner en creusant le terrain plutôt qu’en récoltant des objets posés à la surface
    • Si l’on ne peut pas construire sur une pente, il faut aplanir le terrain avant de bâtir
    • On peut aussi proposer la modification du terrain comme outil d’expression créative
  • La situation clé est la suivante : lorsqu’on creuse la bordure d’un lac ou d’une flaque et qu’un passage s’ouvre, où l’eau s’écoule-t-elle, et en quelle quantité ?

Là où les solutions simples ne suffisent pas

  • Parmi les contournements possibles : figer l’eau à sa position initiale, considérer comme eau tout ce qui est sous une certaine altitude, interdire de creuser trop profondément, ou utiliser un modèle de flux simplifié à la Minecraft ou Dwarf Fortress
  • Ces approches peuvent servir d’alternatives, mais elles sont trop simplistes ou trop « en blocs » pour constituer le modèle principal
  • Le modèle de Dwarf Fortress s’en rapproche davantage, mais il a été conçu en 3D, alors que le problème à résoudre ici concerne surtout de l’eau en 2D sur un terrain
  • Timberborn utilise un modèle du même type que celui présenté ici

Conditions souhaitées pour la simulation

  • Le modèle d’eau visé doit satisfaire les conditions suivantes
    • Il est préférable qu’il fonctionne sur la même grille que le terrain
    • L’échelle moyenne visée est d’environ 1 m, sans nécessité de simuler les petites éclaboussures
    • L’eau est traitée comme un champ de hauteur au-dessus du terrain, sans prendre en compte les flux verticaux ni les vides dans une coupe verticale
    • L’eau doit s’écouler, et ne pas disparaître à cause des erreurs de simulation
    • La stabilité doit pouvoir être contrôlée
    • Le coût d’un pas de simulation doit être linéaire par rapport à la taille de la simulation, idéalement avec seulement quelques passes

Décalage avec les simulations de fluides existantes

  • Smoothed Particle Hydrodynamics produit des résultats fluides haute résolution impressionnants, mais ne correspond pas au problème ici
    • Des particules d’eau de taille 1 m peuvent ressembler à des ballons d’eau
    • Réduire la taille des particules augmente fortement le coût en performance
    • L’objectif n’est pas le réalisme haute résolution, mais un modèle rapide et plausible
  • Les Stable Fluids de Jos Stam sont plus proches d’un modèle pour des volumes entièrement remplis de fluide, comme un réservoir fermé
    • Cela diffère du problème consistant à traiter directement une surface libre au-dessus d’un terrain
    • Certaines étapes nécessitent de résoudre itérativement des systèmes linéaires creux, ce qui coûte cher
    • C’est une approche qui résout l’ensemble des équations de Navier-Stokes, alors qu’ici on a surtout besoin des shallow water equations

Shallow water equations et choix de la grille

  • Les shallow water equations sont une approche qui moyenne verticalement la couche d’eau au-dessus du terrain pour la traiter comme un système 2D
  • « Shallow » signifie que la dimension verticale de la colonne d’eau est supposée bien plus petite que l’échelle horizontale qui nous intéresse
    • Cela peut être valable, par exemple, pour une rivière profonde de quelques mètres à quelques dizaines de mètres, quand les distances d’intérêt sont de l’ordre du kilomètre
  • Une collocated grid classique stocke la hauteur d’eau et la vitesse dans la même cellule, mais cela peut poser problème en dynamique des fluides
    • Une discrétisation naïve des dérivées premières peut introduire un biais directionnel ou de l’instabilité
    • Si des flux entrent par la gauche et la droite et sortent par le haut et le bas dans une même cellule, on obtient la contradiction d’une vitesse totale qui semble nulle
  • Une staggered grid stocke les valeurs comme la hauteur d’eau ou la densité dans les cellules, et les vitesses ou flux sur les arêtes entre cellules
    • tableau N x N pour la hauteur d’eau
    • tableau (N+1) x N pour les flux selon X
    • tableau N x (N+1) pour les flux selon Y

Approche par virtual pipes

  • Les virtual pipes consistent à considérer que les cellules d’eau sont reliées par des tuyaux virtuels et à calculer les flux ainsi
  • L’un des articles de référence traite aussi des colonnes d’eau à plusieurs niveaux et des connexions verticales, et un autre se concentre surtout sur l’érosion hydraulique, mais ces objectifs ne sont pas retenus ici
  • Trois valeurs sont stockées
    • water : hauteur de la colonne d’eau dans chaque cellule
    • flowX : flux total d’eau entre cellules adjacentes à l’horizontale
    • flowY : flux total d’eau entre cellules adjacentes à la verticale
  • On stocke un flux (flow, flux) plutôt qu’une vitesse
    • Le flux peut être vu comme le volume d’eau qui passe par unité de temps
    • Entre deux cellules vides, le flux se définit naturellement comme 0
    • La vitesse étant le flux divisé par une section, on tombe sinon sur des problèmes de 0/0 ou de seuil quand il y a presque plus d’eau

Les 3 étapes d’un pas de simulation

  • Un pas de simulation se divise en trois étapes
    • Accélération des flux : on augmente le flux entre cellules selon la différence de hauteur de surface de l’eau entre cellules voisines
    • Mise à l’échelle des sorties : si l’eau qui quitte une cellule dépasse la quantité réellement disponible, on réduit les flux sortants
    • Mise à jour des colonnes d’eau : on ajoute ou retire de la hauteur d’eau dans chaque cellule selon les flux voisins

  • Accélération des flux

    • Si deux cellules adjacentes ont des hauteurs d’eau différentes, le flux s’accélère du côté haut vers le côté bas
    • On met à jour les flux sur les arêtes internes selon X et Y, en utilisant g, dt, dx et dy
    • La section A du tuyau virtuel n’est utilisée qu’en produit avec g, donc pour un usage simple on peut la considérer comme intégrée dans g
    • On ajoute le frottement en réduisant les flux à chaque pas
    • L’article recommande le coefficient pow(friction, dt)
    • Pour une valeur plus intuitive, on peut utiliser pow(1-friction, dt)
    • friction=0 correspond alors au frottement maximal, qui annule complètement le flux précédent, et friction=1 à l’absence de frottement
    • Plus dt est grand, plus la simulation est rapide, mais plus elle risque de devenir instable
    • En simulation de fluides, la condition de Courant-Friedrichs-Lewy est importante
    • En pratique, il faut réduire dt jusqu’à retrouver la stabilité ; les valeurs utilisées étaient d’environ 0.001 à 0.01

  • Mise à jour des colonnes d’eau

    • Chaque cellule observe les quatre flux adjacents et gagne ou perd de l’eau
    • Les flux entrants par la gauche et par le bas, flowX(x,y) et flowY(x,y), sont ajoutés
    • Les flux sortants vers la droite et vers le haut, flowX(x+1,y) et flowY(x,y+1), sont soustraits
    • C’est l’étape qui déplace effectivement l’eau entre cellules selon les flux calculés

  • Mise à l’échelle des sorties

    • Si les flux sont trop élevés, la mise à jour peut rendre la hauteur d’eau d’une cellule négative
    • On additionne uniquement les flux sortants de chaque cellule afin de vérifier si l’eau retirée pendant un pas dépasse la quantité réellement présente
    • Si c’est le cas, on réduit tous les flux sortants dans la même proportion pour conserver une hauteur d’eau supérieure ou égale à 0
    • Cette étape est le mécanisme de stabilisation essentiel qui empêche les quantités d’eau négatives

Terrain, conditions aux limites et viscosité

  • Le terrain est pris en compte dans l’étape d’accélération des flux, en utilisant la hauteur de surface de l’eau plutôt que la seule hauteur de colonne d’eau
    • hauteur de surface de l’eau = terrain(x,y) + water(x,y)
    • Une cellule plus élevée peut donc faire bouger l’eau même si la hauteur de colonne d’eau est la même
  • Les conditions aux limites sont définies implicitement par les valeurs de flux en bordure
    • flowX(0,y), flowX(N,y), flowY(x,0), flowY(x,N) correspondent aux bords
    • Les mettre à 0 les fait agir comme des murs
    • Une valeur d’entrée ajoute de l’eau, une valeur de sortie en retire
    • Pour de l’eau sur un terrain, une frontière de sortie où l’eau disparaît au bord de la carte peut être naturelle
    • Là où une rivière traverse la frontière, on peut utiliser une frontière d’entrée pour faire circuler le débit
  • Les flux aux limites doivent être réinitialisés au début de chaque pas de simulation
    • Sinon, la mise à l’échelle des sorties peut les modifier et transformer une frontière de sortie en mur
  • L’article inclut aussi un terme de viscosité qui réduit le flux selon la hauteur d’eau
    • L’idée est qu’une fine couche d’eau se déplace difficilement à cause des forces internes, alors qu’une couche plus épaisse se déplace plus librement
    • Cela peut être utile pour des écoulements comme le magma
    • Ce terme n’a pas été utilisé pour l’eau, et sur de grandes échelles de terrain son effet est presque nul

Flux d’implémentation et profil de performance

  • Le code complet suit l’ordre suivant
    • initialisation des flux aux limites
    • pré-calcul du coefficient de frottement pow(1-friction, dt)
    • accélération des flux X
    • accélération des flux Y
    • mise à l’échelle des sorties pour éviter des quantités d’eau négatives
    • mise à jour des colonnes d’eau
  • L’essentiel de la simulation tient dans 4 boucles sur quelques tableaux 2D et des formules simples
  • Le code complet de mise à jour en C++ peut être consulté dans water_2d.cpp
  • Les exemples vidéo proviennent du simulateur d’eau WebGPU publié il y a quelques jours ; les particules visibles dans la vidéo ne servent qu’à la visualisation et ne participent pas à la simulation
  • En trouvant des valeurs appropriées pour dt et g, on obtient un comportement visuellement stable, conforme aux objectifs, et crédible comme eau

Limites restantes

  • Ce modèle n’intègre ni inertie ni diffusion de vitesse
    • Si un jet rapide entre dans un lac, il ne continue pas sa propagation vers l’intérieur et se diffuse plutôt dans toutes les directions
    • Si la hauteur d’eau est identique, deux jets parallèles de sens opposés peuvent coexister sans interagir
  • Quand l’eau pénètre pour la première fois dans une zone, des ondulations apparaissent et peuvent sembler un peu étranges

Extension à une grille hexagonale ou triangulaire

  • Le jeu visé n’utilise pas une grille carrée mais une grille triangulaire régulière
  • Une grille triangulaire peut être vue comme le dual d’une grille hexagonale
    • En reliant les centres d’hexagones voisins, on obtient une grille triangulaire régulière
    • C’est proche de l’usage de l’axial coordinate system sur la grille duale des hexagones pointy-top dans l’article de Red Blob Games sur les grilles hexagonales
  • Une grille triangulaire peut elle aussi être stockée dans un tableau 2D ordinaire légèrement incliné
  • La hauteur des colonnes d’eau est stockée aux sommets de la grille, ce qui facilite le rendu de la surface
  • Les flux sont répartis selon trois directions
    • flux selon X
    • flux selon Y
    • flux selon Z
  • Pour une grille de sommets N x N, on utilise les tableaux suivants
    • tableau (N+1) x N pour les flux X
    • tableau N x (N+1) pour les flux Y
    • tableau (N+1) x (N+1) pour les flux Z, où les valeurs bottom-left et top-right ne sont pas utilisées
  • Par rapport à la grille carrée, il suffit d’ajouter le flux Z dans les conditions aux limites, l’accélération, la mise à l’échelle des sorties et la mise à jour de l’eau
  • La partie la plus difficile est de ne pas se tromper dans les indices
  • Le code C++ pour les grilles triangulaires et hexagonales est disponible dans water_2d_hex.cpp
  • Cette approche peut être un peu plus isotrope qu’une grille carrée

À lire aussi

1 commentaires

 
GN⁺ 2025-02-08
Avis de Hacker News

  • Il existe aussi des vidéos Coding Adventure qui adoptent une autre approche de la simulation de fluides
    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

  • L’une des raisons pour lesquelles la simulation hydrologique est difficile dans les jeux à génération procédurale, c’est que lorsque l’eau s’accumule, elle affecte les cases voisines, et cet effet continue ensuite de se propager aux autres cases alentour
    La génération procédurale se prête souvent bien à la parallélisation, mais dans les zones infinies où l’on dirait justement que la parallélisation serait la plus nécessaire, ce type de calcul est difficile à paralléliser correctement
    Je n’ai pas vu ce sujet beaucoup exploré, et parmi les personnes qui travaillent sur des choses connexes, j’aime particulièrement https://nickmcd.me. C’est l’un des meilleurs terrains procéduraux que j’aie vus jusqu’ici
    Cela dit, ce travail aussi est limité à des zones finies à cause de la conception de la simulation. Parmi les solutions possibles, celle qui me semble la meilleure consiste à générer procéduralement des limites de bassin versant infranchissables, puis à simuler tout le bassin versant en parallèle d’un seul coup
    C’est un problème très intéressant, mais qui dépasse mes connaissances ; je suis donc surtout observateur

    • Si cela t’intrigue, cherche les notions de « domaine d’influence » et de « domaine de dépendance » dans le domaine de la résolution des équations aux dérivées partielles
      Elles désignent respectivement la région qui peut influencer la valeur en un point donné et la région que la valeur en ce point peut influencer, ce qui rejoint directement ce qui vient d’être dit. Dans certains cas, on peut connaître ces régions à l’avance
    • Franchement, https://nickmcd.me vaut vraiment le détour. C’est impressionnant
    • Question intéressante. Cela semble probablement possible en plaçant une bordure autour de chaque région et en supposant une vitesse maximale de propagation des effets, c’est-à-dire une forme de causalité
      Par exemple, pour simuler des pas de 10 heures, on met une bordure de 10 cases de grille. On calcule 10 pas dans chaque région, puis on synchronise l’état des bordures avec les autres simulations de bordure calculées en parallèle, et on répète
    • J’ai été surpris d’apprendre que Nick n’a que 25 ans

  • C’est un peu hors sujet, mais cela me rappelle le passage de l’article qui disait que la manipulation du terrain était nécessaire pour collecter des ressources
    J’ai toujours pensé qu’Animal Crossing gérait cela de façon assez maligne et efficace, sans manipulation du terrain. Quand on coupe un arbre, on obtient des bûches, mais seulement en quantité limitée, ce qui introduit en pratique un temps de recharge
    Cela permet de donner du feedback et une impression de ressources finies sans manipulation coûteuse du terrain. Bien sûr, cela ne convient pas à tous les jeux et fonctionne mieux sur de petites cartes, mais ça vaut la peine d’y réfléchir. Si ce n’est pas indispensable au jeu, il vaut souvent mieux éviter la manipulation du terrain

    • L’article abordait aussi ce genre de stratégie sous la forme de rochers de minerai d’or placés à proximité
      C’est une manière standard de distribuer des ressources, mais un temps de recharge ne supprime pas le problème des ressources infinies, il ne fait que le ralentir. Et c’est un peu ennuyeux et peu impactant

  • C’est un article qui creuse proprement le sujet, et je suis content qu’il mentionne Timberborn
    Je suis complètement accro à ce jeu en ce moment, donc si vous ne l’avez pas encore essayé, je le recommande vivement. L’écoulement de l’eau basé sur la physique ressemble à un autre personnage dans le jeu, et comprendre comment barrer l’eau pour alimenter des moteurs et irriguer les champs constitue le cœur de la boucle de gameplay

  • C’est amusant et vraiment très bien exécuté. Quand on développe ce genre de chose, le plus grand danger est de perdre des heures à ajuster des paramètres en regardant de jolis résultats
    Cela m’a rappelé quand, en 2011, j’avais implémenté moi-même de la dynamique des fluides sur GPU pour un article. Il s’agissait de sang, donc d’un fluide s’écoulant sur une surface, c’est-à-dire un tissu ; je le simulais en 2D, puis je le projetais sur un maillage en tenant compte de la gravité et de la pente de la surface
    J’avais aussi mis une courte vidéo sur YouTube : https://youtu.be/4vGrNc-GGW8

  • Vraiment cool
    Récemment, avec l’aide de o3-mini-high, j’ai expérimenté une idée similaire. Je lui ai expliqué l’idée de l’algorithme, et il l’a implémentée et rendue en 3D sans intervention manuelle. J’ai toutefois utilisé plusieurs prompts
    https://3d-water-sim.netlify.app/
    Ce n’est pas encore parfait, parce que j’ai arrêté de bricoler dessus, mais à chaque itération ça s’améliorait assez nettement. Ce qui est intéressant, c’est que pour générer le terrain, il n’a pas récupéré quelque chose depuis un CDN ou autre : il a implémenté correctement dès le départ une version fonctionnelle du bruit de Perlin

    • Quand on fait ce genre d’expériences, je me demande si le but est de s’amuser ou d’apprendre. Si le but est l’apprentissage, je me demande aussi si lire cet article reste perçu comme utile même sans avoir implémenté soi-même
      C’est une question sur la différence entre le voyage et la destination

  • Le passage de l’article disant que « ce modèle n’a ni inertie ni diffusion de vitesse. Même si un courant rapide entre dans un lac, il ne se propage pas plus loin vers l’intérieur du lac et se répand dans toutes les directions en ignorant l’inertie accumulée. Si le niveau d’eau est le même, deux courants parallèles allant en sens opposé peuvent aussi ne pas interagir entre eux » pourrait, me semble-t-il, être résolu en faisant une moyenne avec les 6 flèches de flux voisines allant dans la même direction
    L’idée serait de donner un poids élevé aux flèches devant et derrière, et un poids plus faible aux flèches latérales. Par exemple, avec des flèches comme celles-ci
    -a-> -b->
    -c-> -d-> -e->
    -f-> -g->
    New_d = d * (1 - 2*.1 - 4*.01) + (c+e).1 + (a+b+f+b).01
    Ici, .1 et .01 sont des poids choisis arbitrairement et devraient être ajustés ; on pourrait aussi introduire une puissance, comme pour réduire les oscillations. En incluant ce coefficient, cela pourrait donner ceci
    New_d = d * (1 - 2*.1 - 4*.01 - .001) + (c+e).1 + (a+b+f+b).01

    • La vraie solution semble plutôt consister à ajouter une grille de dérivées secondes alignée sur la grille d’origine
      grid 0 : hauteur d’eau de chaque cellule
      grid 1 : flux d’eau sur chaque arête, c’est-à-dire la dérivée première
      grid 2 : accélération de l’eau dans chaque cellule, c’est-à-dire la dérivée seconde
      Chaque grille est la grille duale de la précédente et stocke ses valeurs dérivées. En fait, il ne serait peut-être même pas nécessaire de traiter spécialement les données d’arêtes : on pourrait ne garder que les données de sommets et tout gérer purement comme des grilles duales. Le flux sur une arête peut être déduit de la somme des flux aux deux sommets qui la délimitent
      On met donc à jour la hauteur du fluide à partir du flux, puis l’accélération selon la vitesse et la quantité de masse de fluide entrée dans une cellule, puis on met à jour le flux à partir de l’accélération et de la hauteur actuelle du fluide. Je ne connais pas bien la mécanique des fluides, mais du point de vue de la simulation numérique cela semble correct, et cela rend aussi possibles les flux diagonaux
    • Cette approche rompt la conservation de la quantité de mouvement. Pour obtenir un écoulement réaliste, il faut utiliser l’équation de continuité afin de conserver l’énergie du flux, et faire en sorte que le cisaillement se dissipe et se diffuse en tourbillons
      Comme le dit l’article, cela augmente fortement la charge de calcul ; il faut donc d’abord vérifier si ce niveau de réalisme est nécessaire pour le cas d’usage réel

  • Un résultat bricolé que j’avais fait il y a quelques années par curiosité : https://aperocky.com/hydrosim/
    Je n’avais pas réussi à déterminer comment gérer l’érosion avant que ce projet personnel ne parte au stockage froid. J’ai apprécié que l’auteur mentionne ce point et fournisse même les équations

  • J’ai récemment publié quelque chose de similaire. Il inclut la génération aléatoire de heightfield, le transport de sédiments et l’érosion : https://github.com/Ono-Sendai/terraingen

  • Vous pouvez essayer directement une simulation d’inondation pédagogique créée par un excellent développeur de notre entreprise dans le cadre d’un projet de recherche
    https://flood.concord.org/
    Pour obtenir un effet marqué, il faut modifier les valeurs du modèle dans la barre d’outils du bas
    C’est une simulation à base de cellules qui calcule les valeurs des cellules dans WebGL à partir des cellules voisines. Le shader qui effectue ce calcul se trouve ici
    https://github.com/concord-consortium/flooding-model/blob/ma...