- In Spielen, in denen sich Terrain ausheben und auffüllen lässt, müssen Seen, Flüsse und Pfützen entlang neuer Grenzen abfließen können; dafür ist eine schnelle und stabile gitterbasierte Wassersimulation nötig
- Ziel ist ein 2D-Höhenfeldmodell, das auf demselben Gitter wie das Terrain bei einem Maßstab von etwa 1 m arbeitet und Wassererhaltung, kontrollierbare Stabilität sowie lineare Update-Kosten erfüllt
- Smoothed Particle Hydrodynamics und Stable Fluids sind jeweils auf hochauflösende Partikelflüssigkeiten bzw. geschlossene Flüssigkeitsvolumina ausgelegt und passen daher nicht gut zu der Anforderung, freie Wasseroberflächen auf Terrain schnell zu verarbeiten
- Der gewählte Virtual-Pipes-Ansatz speichert Wasserhöhen und Flüsse zwischen Zellen auf einem staggered grid und verarbeitet Flussbeschleunigung, Ausfluss-Skalierung und Aktualisierung der Wassersäulen mit einigen Schleifen über 2D-Arrays
- Mit geeigneten Werten für
dtundgentstehen Ergebnisse, die wie Wasser wirken, aber es bleibt die Einschränkung, dass Trägheit und Geschwindigkeitsdiffusion fehlen, sodass ein schneller Wasserstrahl sich in einem See nicht weiter fortpflanzt
Warum Wasser in Spielen mit Terrainbearbeitung schwierig ist
- In Strategiespielen oder Stadt-/Dorfsimulationen kann Wasser als natürliche Grenze dienen und Funktionen wie Schifffahrt, Angeln, Handel, Seeschlachten, Trinkwasserversorgung, Transport und Ästhetik übernehmen
- Wenn sich das Terrain direkt verändern lässt, steigt die Schwierigkeit der Wasserbehandlung stark an
- Wenn Ressourcen wie Erde, Sand oder Lehm aus dem Boden gegraben werden, wirkt es natürlicher, wenn dabei auch das Terrain entfernt wird
- Auch bei Stein- und Metallerz passt ein Abbau durch Ausheben des Bodens besser als Objekte, die nur auf der Oberfläche liegen
- Wenn sich Gebäude nicht an Hängen errichten lassen, muss das Terrain vor dem Bauen eingeebnet werden
- Terrainbearbeitung selbst kann als Werkzeug für kreativen Ausdruck angeboten werden
- Die zentrale Situation ist: Wenn der Rand eines Sees oder einer Pfütze aufgegraben wird und sich ein Abfluss öffnet, wohin und wie viel Wasser fließt dann?
Wo einfache Lösungen nicht ausreichen
- Mögliche Umgehungslösungen sind, Wasser an seiner Startposition zu fixieren, alles unterhalb einer bestimmten Höhe als Wasser zu behandeln, zu tiefes Graben zu verbieten oder ein einfaches Strömungsmodell wie in Minecraft oder Dwarf Fortress zu verwenden
- Solche Ansätze können als Alternativen funktionieren, sind aber als Hauptmodell zu simpel oder wirken zu blockig
- Das Modell von Dwarf Fortress kommt den Anforderungen näher als die anderen Beispiele, wurde aber für 3D entworfen, während das benötigte Problem überwiegend Wasser auf 2D-Terrain ist
- Timberborn verwendet ein Modell wie das hier behandelte
Gewünschte Bedingungen für die Simulation
- Das angestrebte Wassermodell sollte die folgenden Bedingungen erfüllen
- Es sollte vorzugsweise auf demselben Gitter wie das Terrain arbeiten
- Der durchschnittliche Maßstab liegt bei etwa 1 m, und kleine Spritzer müssen nicht simuliert werden
- Wasser wird als Höhenfeld über dem Terrain betrachtet; vertikale Strömungen oder Hohlräume im Vertikalschnitt werden nicht berücksichtigt
- Wasser muss fließen und darf nicht durch Simulationsfehler verschwinden
- Die Stabilität muss kontrollierbar sein
- Die Kosten pro Schritt sollten linear mit der Simulationsgröße skalieren; ideal sind ein paar wenige Schleifen
Abweichungen zu bestehender Strömungssimulation
- Smoothed Particle Hydrodynamics liefert beeindruckende hochauflösende Fluidergebnisse, passt aber nicht zu diesem Problem
- Wasserpartikel in 1-m-Größe können wie Wasserballons aussehen
- Kleinere Partikel erhöhen die Rechenkosten
- Ziel ist nicht hochauflösender Realismus, sondern ein schnelles und plausibles Modell
- Jos Stams Stable Fluids ist näher an einem Modell für vollständig mit Fluid gefüllte Volumina wie geschlossene Tanks
- Es unterscheidet sich vom Problem einer freien Oberfläche auf Terrain
- In einigen Schritten müssen dünn besetzte lineare Gleichungssysteme iterativ gelöst werden, was teuer ist
- Der Ansatz löst die vollständigen Navier-Stokes-Gleichungen, während hier eigentlich die shallow water equations gebraucht werden
Shallow water equations und Gitterwahl
- Die shallow water equations behandeln eine Wasserschicht auf Terrain als in vertikaler Richtung gemitteltes 2D-Gleichungssystem
- „Shallow“ bedeutet, dass die vertikale Höhe der Wassersäule deutlich kleiner ist als die relevante horizontale Skala
- Das kann etwa gelten, wenn ein Fluss einige bis einige Dutzend Meter tief ist und die interessierenden Distanzen im Kilometerbereich liegen
- Ein gewöhnliches collocated grid speichert Wasserhöhe und Geschwindigkeit in derselben Zelle, was in der Fluiddynamik Probleme verursachen kann
- Eine naive Diskretisierung erster Ableitungen kann Richtungs-Bias oder Instabilität erzeugen
- Wenn von links und rechts Zufluss und nach oben und unten Abfluss in derselben Zelle liegen, kann paradoxerweise eine Gesamtgeschwindigkeit von 0 entstehen
- Ein staggered grid speichert Werte wie Wasserhöhe oder Dichte in den Zellen und Geschwindigkeiten bzw. Flüsse an den Kanten zwischen den Zellen
N x N-Array für Wasserhöhen(N+1) x N-Array für Flüsse in X-RichtungN x (N+1)-Array für Flüsse in Y-Richtung
Der Virtual-Pipes-Ansatz
- Virtual Pipes berechnet den Fluss, indem Wasserzellen als über virtuelle Rohre verbunden betrachtet werden
- Eine der referenzierten Arbeiten behandelt auch Wassersäulen mit mehreren Ebenen und vertikale Verbindungen, eine andere vor allem hydraulische Erosion; diese Ziele werden hier jedoch ausgeklammert
- Gespeichert werden drei Werte
water: Höhe der Wassersäule in jeder ZelleflowX: gesamter Wasserfluss zwischen horizontal benachbarten ZellenflowY: gesamter Wasserfluss zwischen vertikal benachbarten Zellen
- Gespeichert wird Fluss (flow, flux) statt Geschwindigkeit
- Fluss kann als Wasservolumen pro Zeiteinheit verstanden werden
- Zwischen leeren Zellen ist der Fluss auf natürliche Weise 0
- Geschwindigkeit ist Fluss geteilt durch Querschnitt; bei fast keinem Wasser entstehen dabei 0/0- oder Schwellenwertprobleme
Die 3 Schritte eines Simulationsschritts
- Ein Simulationsschritt besteht aus drei Phasen
- Flussbeschleunigung: Der Fluss zwischen Zellen wird entsprechend der Differenz der Wasseroberflächenhöhen benachbarter Zellen erhöht
- Ausfluss-Skalierung: Wenn aus einer Zelle mehr Wasser abfließt, als tatsächlich vorhanden ist, werden die Ausflusswerte reduziert
- Aktualisierung der Wassersäulen: Die Wasserhöhe jeder Zelle wird anhand der benachbarten Flüsse erhöht oder verringert
-
Flussbeschleunigung
- Wenn benachbarte Zellen unterschiedliche Wasserhöhen haben, wird der Fluss von der höheren zur niedrigeren Seite beschleunigt
- Der Fluss wird an inneren Kanten in X- und Y-Richtung aktualisiert; dabei werden
g,dt,dxunddyverwendet - Die Querschnittsfläche
Ades virtuellen Rohrs tritt nur im Produkt mitgauf und kann in einfachen Anwendungen praktisch ingaufgehen - Reibung wird ergänzt, indem der Fluss in jedem Schritt reduziert wird
- Die Arbeit empfiehlt dafür den Faktor
pow(friction, dt) - Für intuitivere Werte kann stattdessen
pow(1-friction, dt)verwendet werden friction=0entspricht maximaler Reibung, bei der der vorherige Fluss vollständig verschwindet, undfriction=1bedeutet keine Reibung- Je größer
dt, desto schneller die Simulation, aber desto instabiler kann sie werden - Für Strömungssimulationen ist die Courant-Friedrichs-Lewy-Bedingung wichtig
- In der Praxis muss
dtso lange verringert werden, bis die Simulation stabil ist; verwendet wurden ungefähr0.001bis0.01
-
Aktualisierung der Wassersäulen
- Jede Zelle addiert oder subtrahiert Wasser anhand ihrer vier benachbarten Flüsse
- Zuflüsse von links und unten,
flowX(x,y)undflowY(x,y), werden addiert - Abflüsse nach rechts und oben,
flowX(x+1,y)undflowY(x,y+1), werden subtrahiert - Dies ist der Schritt, in dem anhand der berechneten Flüsse tatsächlich Wasser zwischen Zellen verschoben wird
-
Ausfluss-Skalierung
- Wenn die Flüsse zu groß sind, kann die Wasserhöhe einer Zelle nach dem Update negativ werden
- Es werden nur die ausgehenden Flüsse jeder Zelle aufsummiert, um zu prüfen, ob die in einem Schritt entfernte Wassermenge den tatsächlichen Inhalt übersteigt
- Ist die abgeführte Menge zu groß, werden die ausgehenden Flüsse proportional reduziert, damit die Wasserhöhe bei 0 oder höher bleibt
- Dieser Schritt ist der zentrale Stabilisierungsmechanismus gegen negative Wassermengen
Terrain, Randbedingungen und Viskosität
- Das Terrain wird in der Phase der Flussbeschleunigung berücksichtigt, indem statt der Höhe der Wassersäule die Wasseroberflächenhöhe verwendet wird
- Wasseroberflächenhöhe =
terrain(x,y) + water(x,y) - In Zellen mit höherem Terrain liegt die Oberfläche auch bei gleicher Wassersäule höher, sodass Wasser abfließen kann
- Wasseroberflächenhöhe =
- Randbedingungen werden implizit über die Randflusswerte festgelegt
flowX(0,y),flowX(N,y),flowY(x,0),flowY(x,N)entsprechen den Rändern- Wenn sie 0 sind, wirken sie wie Wände
- Einlasswerte fügen Wasser hinzu, Auslasswerte entfernen Wasser
- Für Wasser auf Terrain kann ein Auslassrand natürlich sein, bei dem Wasser am Kartenrand verschwindet
- Wenn ein Fluss den Rand kreuzt, kann dort ein Einlassrand gesetzt werden, damit das Flusswasser weiterströmt
- Randflüsse müssen zu Beginn jedes Simulationsschritts neu gesetzt werden
- Sonst kann die Ausfluss-Skalierung die Randflüsse verändern und einen Auslassrand in eine Wand verwandeln
- Die Arbeiten enthalten außerdem einen Viskositäts-Term, der Flüsse abhängig von der Wasserhöhe reduziert
- Die Idee ist, dass sich dünne Wasserschichten wegen innerer Kräfte schwerer bewegen, während dickere Schichten freier fließen
- Das kann etwa für Magmaströme nützlich sein
- Für Wasser wurde es nicht verwendet; bei großskaligem Terrain ist der Einfluss der Viskosität gering
Implementierungsablauf und Leistungsprofil
- Der gesamte Code folgt dieser Reihenfolge
- Initialisierung der Randflüsse
- Vorberechnung des Reibungsfaktors
pow(1-friction, dt) - Beschleunigung der X-Flüsse
- Beschleunigung der Y-Flüsse
- Ausfluss-Skalierung zur Vermeidung negativer Wassermengen
- Aktualisierung der Wassersäulen
- Der Großteil der Simulation besteht aus 4 Schleifen über einige 2D-Arrays und einfachen Formeln
- Der vollständige C++-Update-Code ist in water_2d.cpp zu sehen
- Die Video-Beispiele stammen aus dem vor einigen Tagen veröffentlichten WebGPU water simulator; die Partikel im Video dienen nur der Visualisierung und sind nicht Teil der Simulation
- Mit passenden Werten für
dtundgwirkt das Ergebnis stabil, erfüllt die Anforderungen und sieht nach Wasser aus
Verbleibende Einschränkungen
- Dem Modell fehlen Trägheit und Geschwindigkeitsdiffusion
- Wenn ein schneller Wasserstrahl in einen See eintritt, pflanzt er sich nicht ins Seeinnere fort, sondern verteilt sich in alle Richtungen
- Wenn die Wasserhöhe gleich ist, können zwei parallele Wasserströme in entgegengesetzter Richtung existieren, ohne miteinander zu interagieren
- Wenn Wasser zum ersten Mal in einen Bereich eintritt, entstehen Wellen, die etwas merkwürdig aussehen können
Erweiterung auf hexagonale und dreieckige Gitter
- Das Zielspiel verwendet kein quadratisches Gitter, sondern ein reguläres dreieckiges Gitter
- Ein dreieckiges Gitter kann als das Dual eines hexagonalen Gitters betrachtet werden
- Verbindet man die Mittelpunkte benachbarter Hexagone, entsteht ein reguläres Dreiecksgitter
- Das ähnelt der Verwendung des axial coordinate system aus Red Blob Games’ Artikel zu hexagonal grids auf dem dualen Gitter pointy-top-orientierter Hexfelder
- Auch ein dreieckiges Gitter kann in einem leicht geneigten gewöhnlichen 2D-Array gespeichert werden
- Die Höhen der Wassersäulen werden an den Gitterpunkten gespeichert, was das Rendern der Wasseroberfläche erleichtert
- Die Flüsse werden in drei Richtungen aufgeteilt
- Fluss in X-Richtung
- Fluss in Y-Richtung
- Fluss in Z-Richtung
- Für ein
N x N-Punktgitter werden folgende Arrays verwendet(N+1) x N-Array für X-FlüsseN x (N+1)-Array für Y-Flüsse(N+1) x (N+1)-Array für Z-Flüsse, wobei die Werte unten links und oben rechts nicht verwendet werden
- Im Vergleich zum quadratischen Gitter müssen bei Randbedingungen, Beschleunigung, Ausfluss-Skalierung und Wasser-Update nur die Z-Flüsse ergänzt werden
- Der schwierigste Teil ist, sich bei der Indizierung nicht zu vertun
- Der C++-Code für Dreiecks-/Hexgitter ist in water_2d_hex.cpp zu sehen
- Dieser Ansatz kann etwas isotroper sein als ein quadratisches Gitter
1 Kommentare
Meinungen auf Hacker News
Einen anderen Ansatz zur Fluidsimulation bieten die Coding-Adventure-Videos
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
Einer der Gründe, warum Hydrologie-Simulationen in prozedural generierten Spielen schwierig sind, ist, dass sich angesammeltes Wasser auf benachbarte Zellen auswirkt und dieser Effekt sich dann immer weiter auf andere Nachbarzellen ausbreitet
Prozedurale Generierung eignet sich oft gut für Parallelisierung, aber gerade in unendlichen Bereichen, wo Parallelisierung am nötigsten erscheint, lassen sich solche Berechnungen nur schwer korrekt parallelisieren
Ich habe nicht gesehen, dass dieses Thema besonders ausführlich untersucht wurde; unter den Leuten, die daran arbeiten, mag ich https://nickmcd.me besonders. Das gehört zu den besten prozeduralen Terrains, die ich bisher gesehen habe
Allerdings ist auch diese Arbeit wegen des Simulationsdesigns auf begrenzte Bereiche beschränkt. Als mögliche Lösung erscheint es am besten, unüberwindbare Einzugsgebietsgrenzen prozedural zu erzeugen und dann das gesamte Einzugsgebiet auf einmal parallel zu simulieren
Ein äußerst interessantes Problem, aber es liegt außerhalb meines Wissensbereichs, daher bin ich hauptsächlich Beobachter
Gemeint sind der Bereich, der den Wert an einem bestimmten Punkt beeinflussen kann, und der Bereich, den der Wert an diesem Punkt beeinflussen kann; das berührt genau das oben Gesagte. In manchen Fällen kann man diese Bereiche im Voraus kennen
Wenn man zum Beispiel 10 Stunden Schritte simulieren will, legt man eine Grenze von 10 Rasterzellen an. Man berechnet in jedem Bereich 10 Schritte, synchronisiert dann den Grenzzustand mit den anderen parallel berechneten Grenzsimulationen und wiederholt das
Etwas abseits vom Thema, aber mir fiel die Stelle im Artikel ein, in der stand, dass zur Ressourcengewinnung Terrain-Manipulation nötig sei
Ich habe immer gedacht, dass Animal Crossing das auch ohne Terrain-Manipulation ziemlich clever und effizient gelöst hat. Wenn man einen Baum fällt, erhält man Holzstämme, aber nur eine bestimmte Menge, und faktisch entsteht eine Abklingzeit
So bekommt man Feedback und ein Gefühl endlicher Ressourcen, ohne teure Terrain-Manipulation. Natürlich passt das nicht zu jedem Spiel und funktioniert besser auf kleinen Karten, aber es ist eine Überlegung wert. Wenn es für das Spiel nicht wirklich nötig ist, ist es oft besser, auf Terrain-Manipulation zu verzichten
Als Methode zur Ressourcenausgabe ist das Standard, aber eine Abklingzeit beseitigt das Problem unendlicher Ressourcen nicht, sondern verlangsamt es nur. Außerdem ist es etwas langweilig und hat wenig Wirkung
Ein sauberer Einstieg in dieses Thema, und ich freue mich, dass Timberborn erwähnt wurde
Ich bin derzeit völlig in dieses Spiel vertieft und kann es nur wärmstens empfehlen, falls man es noch nicht gespielt hat. Der physikbasierte Wasserfluss wirkt wie eine weitere Figur im Spiel, und herauszufinden, wie man Wasser staut, für Motoren nutzt und Felder versorgt, ist der zentrale Gameplay-Loop
Interessant und wirklich gut umgesetzt. Die größte Gefahr bei der Entwicklung solcher Dinge ist, dass man beim Betrachten hübscher Ergebnisse stundenlang nur an Parametern herumdreht
Das erinnerte mich daran, wie ich 2011 für eine wissenschaftliche Arbeit selbst GPU-basierte Fluiddynamik implementiert habe. Es ging um Blut, also eine Flüssigkeit, die über eine Oberfläche bzw. Gewebe fließt; ich habe sie in 2D simuliert und dann unter Berücksichtigung von Schwerkraft und Oberflächenneigung auf ein Mesh projiziert
Ein kurzes Video habe ich auch auf YouTube hochgeladen: https://youtu.be/4vGrNc-GGW8
Wirklich cool
Kürzlich habe ich mit Hilfe von o3-mini-high mit einer ähnlichen Idee experimentiert. Ich habe die Algorithmusidee erklärt, und es hat sie ohne manuelles Eingreifen in 3D implementiert und gerendert. Allerdings habe ich mehrere Prompts verwendet
https://3d-water-sim.netlify.app/
Es ist noch nicht perfekt, weil ich irgendwann aufgehört habe, daran herumzuspielen, aber mit jeder Iteration wurde es deutlich besser. Interessant ist, dass es für die Terrain-Erzeugung nichts von einem CDN oder Ähnlichem geholt hat, sondern eine funktionierende Version von Perlin-Rauschen von Grund auf korrekt implementiert hat
Es ist eine Frage nach dem Unterschied zwischen Reise und Ziel
Die Stelle im Artikel, in der es heißt: „Dieses Modell hat keine Trägheit und keine Diffusion von Geschwindigkeit. Selbst wenn ein schneller Wasserstrom in einen See fließt, breitet er sich nicht weiter ins Innere des Sees aus, sondern verteilt sich in alle Richtungen, während die angesammelte Trägheit ignoriert wird. Wenn der Wasserstand gleich ist, können auch zwei parallele Wasserströme, die in entgegengesetzte Richtungen fließen, unter Umständen nicht miteinander interagieren“, ließe sich vermutlich lösen, indem man den Durchschnitt mit den sechs benachbarten Strömungspfeilen in derselben Richtung bildet.
Dabei bekämen die Pfeile vorne und hinten ein großes Gewicht, die seitlichen Pfeile ein kleines. Wenn es zum Beispiel solche Pfeile gibt:
-a-> -b->
-c-> -d-> -e->
-f-> -g->
New_d = d * (1 - 2*.1 - 4*.01) + (c+e).1 + (a+b+f+b).01
Dabei sind .1 und .01 willkürlich gewählte Gewichte und müssten angepasst werden; man könnte auch, ähnlich wie zur Verringerung von Schwingungen, eine Potenz einbauen. Mit diesem Koeffizienten könnte es dann so aussehen:
New_d = d * (1 - 2*.1 - 4*.01 - .001) + (c+e).1 + (a+b+f+b).01
grid 0: Wasserhöhe jeder Zelle
grid 1: Wasserfluss an jeder Kante, also die erste Ableitung
grid 2: Wasserbeschleunigung jeder Zelle, also die zweite Ableitung
Die Struktur wäre so, dass jedes Gitter das duale Gitter des vorherigen ist und dessen Ableitungswerte speichert. Eigentlich müsste man Kantendaten wohl gar nicht gesondert behandeln, sondern könnte nur Scheitelpunktdaten verwenden und das Ganze rein als duales Gitter behandeln. Der Kantenfluss lässt sich als Summe der Flüsse an den beiden Scheitelpunkten dieser Kante ableiten.
Daher aktualisiert man die Flüssigkeitshöhe anhand des Flusses, aktualisiert dann die Beschleunigung danach, mit welcher Geschwindigkeit wie viel Flüssigkeitsmasse in eine Zelle eingetreten ist, und aktualisiert anschließend den Fluss anhand von Beschleunigung und aktueller Flüssigkeitshöhe. Von Strömungsmechanik verstehe ich nicht viel, aber aus Sicht der numerischen Simulation wirkt das plausibel, und diagonale Flüsse würden dadurch ebenfalls möglich.
Wie im Artikel erwähnt, steigt der Rechenaufwand dadurch deutlich; man sollte also zuerst prüfen, ob dieser Grad an Realismus für den konkreten Anwendungsfall überhaupt nötig ist.
Ein grobes Ergebnis, das ich vor ein paar Jahren aus Neugier gebaut habe: https://aperocky.com/hydrosim/
Bevor dieses private Projekt im Cold Storage verschwand, hatte ich nicht herausgefunden, wie man Erosion behandeln sollte. Mir gefiel, dass der Autor diesen Punkt erwähnt und sogar Gleichungen dafür angefügt hat.
Kürzlich habe ich etwas Ähnliches veröffentlicht. Es enthält zufällige Heightfield-Erzeugung, Sedimenttransport und Erosion: https://github.com/Ono-Sendai/terraingen
Man kann eine lehrreiche Flutsimulation direkt ausprobieren, die ein hervorragender Entwickler in unserem Unternehmen als Teil eines Forschungsprojekts gebaut hat.
https://flood.concord.org/
Um einen größeren Effekt zu sehen, muss man die Modellwerte in der unteren Symbolleiste ändern.
Es handelt sich um eine zellbasierte Simulation, die Zellwerte in WebGL anhand benachbarter Zellen berechnet. Der Shader, der diese Berechnung ausführt, ist hier:
https://github.com/concord-consortium/flooding-model/blob/ma...