Simulation von Erosion zur realistischen Weltgenerierung

[focus0941]

Hallo,
Momentan versuche ich eine möglichst realistische Spielwelt auf Basis von einem Seed in der Programmiersprache Java zu generieren. Nachdem ich verschiedene Noise-Funktionen ausprobiert habe, erschien mir das etwas zu langweilig, weshalb ich beschloss nach zusätzlichen Methoden zu suchen, um das durch die Noise-Funktion entstandene Relief zu verbessern. Dabei fand ich etwas Namens "hydraulic erosion", also Erosion durch Wasser, womit man Terrain realistischer machen kann. Aber leider verstehe ich nicht so ganz wie das funktioniert. Kennt sich jemand darin gut aus?


Hier ist ein Link zum Artikel:

https://www.firespark.de/resources/down ... rosion.pdf

[mtorc1]

Hey,
also tatsächlich habe ich überhaupt keine Ahnung davon. Ich bin aber erst gestern zufällig über diesen Artikel gestoßen: https://nickmcd.me/2022/04/15/soilmachine/
Vielleicht hilft es!
Gruß

[focus0941]

Der Artikel sieht zwar interessant aus, aber so wie ich es verstanden habe, müsste ich erst eine Voxel-Engine programmieren. :(
Aber trotzdem vielen Dank!

[focus0941]

Gibt es irgend eine Möglichkeit ein Vektorfeld aus einer Noise-Funktion machen, also ich meine z.B. durch ableiten oder so.
Damit könnte man dann die Fließrichtung des Wassers angeben, ohne sie jedes Mal neu zu berechnen.

[Jonathan]

Aber leider verstehe ich nicht so ganz wie das funktioniert. Kennt sich jemand darin gut aus?

Die Arbeit sieht ja eigentlich ganz gut und ausführlich erklärt aus. Was hast du nicht verstanden? Bzw. bis zum welchen Punkt hast du sie gelesen und wo bist du dann hängen geblieben? Für eine konkrete Frage kriegst du ggf. eine konkrete Antwort, ansonsten ist die Antwort halt "Arbeite die BA durch und implementiere sie".

Ich habe das btw. auch noch nicht implementiert, aber es sieht nicht so wahnsinnig kompliziert aus, bei einer konkreten Frage könnte ich also vlt. weiterhelfen.

Gibt es irgend eine Möglichkeit ein Vektorfeld aus einer Noise-Funktion machen, also ich meine z.B. durch ableiten oder so.
Damit könnte man dann die Fließrichtung des Wassers angeben, ohne sie jedes Mal neu zu berechnen.

"Noise" Funktion kann ja erstmal alles sein, aber ich nehme an, du benutzt den Noise um eine Heightmap zu generieren und willst jetzt dazu die Normalmap berechnen? Das ist ja eine Standard-Aufgabe, die man verschieden-fancy lösen kann:

- Ganz simpel mit Finiten-Differenzen: Jeweils den Pixel darüber von dem Pixel darunter und den Pixel links von dem Pixel rechts abziehen, und man hat den Gradienten in x/y Richtung
- Irgendeine Funktion (z.B. ein Polynom) durch ein paar benachbarte Pixel fitten und ableiten (ist ggf. besser bei niedriger Auflösung / viel Rauschen)
- Irgendeinen Code im Internet kopieren. z.B. das hier: https://www.shadertoy.com/view/3sSSW1
- vielleicht hilft das hier auch: https://stackoverflow.com/questions/528 ... height-map

Aber was meinst du mit "Fließrichtung des Wassers angeben, ohne sie jedes Mal neu zu berechnen"? Wenn du sie schon jedesmal neu berechnen kannst, wieso fragst du, wie man das Vektorfeld berechnet? Ist das nicht das selbe?

[Krishty]

Der Link macht ein High-End-System vor; für den Anfang ist das viel zu komplex. Das geht weitaus einfacher.

Du brauchst kein Voxel-Feld. Du brauchst tatsächlich nur ein paar 2D-Felder zusätzlich zur Höheninformation.

In einem speicherst du die Regenmenge pro Vertex. Millimeter, Liter, wie es dir gefällt. Bei jeder Iteration lässt du es „regnen“, indem du etwas auf diese Regenmenge aufschlägst. Wie viel, musst du experimentieren.

Weiterhin musst du diese Regenmenge in jeder Iteration an die Nachbarn abfließen lassen, falls sie tiefer liegen. Typischerweise berechnest du aus deiner Heightmap die Steigung zu jedem Nachbarn; falls es bergab geht, fließt Wasser dahin ab – also Regenmenge des aktuellen Vertex verringern und dafür auf den Nachbarn aufschlagen. Wie viel? Das soll von der Steigung abhängen – je steiler es bergab geht, desto schneller sollte die Regenmenge abfließen.

Und dieses Abfließen ist dann, was deine Erosion steuert. Fließt über ein Vertex sehr viel drüber, dann subtrahierst du an dieser Stelle von deiner Heightmap. So wie viel fließendes Wasser eben Sand/Gestein/Whatever abträgt. Wie viel? Experimentiert ein Bisschen. Optimalerweise solltest du das abgetragene Gestein gemeinsam mit der Regenmenge auf die niedrigeren Nachbarn verteilen.

Hier ein billig-Video meiner Experimente von 2013, das ich gerade parat liegen habe:


Bloß Heightmap + Wassermenge.

Wenn das funktioniert, kannst du damit schon recht potente Landschaften machen, indem du mit Regenmenge/Erosionsstärke herumspielst:

Die Screenshots haben jeweils 10 Sekunden oder so gebraucht, weil ich’s auf der GPU gemacht habe. Diese Erosion lässt sich nämlich perfekt parallelisieren!

IMHO ist das größte Problem (das siehst du bei mir und auch in den Links oben), dass sich ständig Pixelmuster bilden. Also experimentier ruhig auch mit Blur o.Ä..

Wenn du so weit gekommen bist, dann würde ich ein 3D-Voxelmodell wie in den Links probieren. Das eröffnet dir die Arbeit mit verschiedenen Gesteinssorten, Höhlen, usw. Für einen Einstieg ist das aber totaler Overkill. Ich würd’s mir noch nicht zutrauen.

Falls das mit 3D-Voxeln schiefgeht, probier mal mehrere Heightmaps parallel: Eine für Gestein, eine für Sand, eine für Erde. Simulier mal, dass Pflanzen in der Nähe von Wasser wachsen, und dadurch Erosion bremsen. Da kann man sich mächtig austoben!

[focus0941]

Die Arbeit sieht ja eigentlich ganz gut und ausführlich erklärt aus. Was hast du nicht verstanden? Bzw. bis zum welchen Punkt hast du sie gelesen und wo bist du dann hängen geblieben? Für eine konkrete Frage kriegst du ggf. eine konkrete Antwort, ansonsten ist die Antwort halt "Arbeite die BA durch und implementiere sie".

Also ich bin bei 5.1 hängen geblieben. Dort wo der Tropfen Werte zugewiesen bekommt und die Vektoren berechnet werden.
Mein erstes Problem ist, dass ich nicht weiß was der Tropfen überhaupt ist. Ich kann zwar Variablen für die Werte definieren, aber dann sind sie ja kein Tropfen, weil sie separat sind.
Sonst, weiß ich auch noch nicht wozu das "u" und das "v" in "posold = (x + u, y + v) with u, v ∈ [0, 1]" dienen.
Noch ist mir das mit dem "old" und "new" auch unklar. Soll ich da neue Variablen nehmen, also eine für die "old"-Version des Werts und eine für die"old"?

[Jonathan]

Deine Heightmap ist eine Textur, d.h. hat eine Integer-Anzahl an Pixeln. Tropfen sind aber floats. Pixelwerte sind nur an diskreten Punkten (ganzzahlige Koordinate) definiert, Tropfen können auch zwischen 2 Pixeln liegen. u/v gibt den Abstand zur nächsten ganzzahligen Pixelposition an. Die Tropfenposition x+u ist also zum Beispiel 30 + 0.3 = 30.3

In der Theorie ist dein Höhenfeld natürlich durchgehend (blaue Linie) in der Praxis hast du nur diskrete Werte (rote Punkte)



Um also den Gradienten zwischen 2 roten Punkten zu bekommen, musst du interpolieren. Das ist das, was auf Seite 9 oben passiert, dort wird eine gewichtete Summe der Pixelwerte berechnet.

Das old und new ist einfach eine Notationssache. Du musst ja in jeder Iteration die Tropfenposition aktualisieren. Die ist abhängig von der vorherigen Position. Ggf. kommst du in deinem Code ganz ohne old und new aus, und kannst die Variable einfach jedes mal direkt überschreiben.

[focus0941]

Das habe ich jetzt verstanden, aber wie soll ich dass jetzt in Code übersetzten?

[Jonathan]

Also es sind ja zwei Schritte - das eine ist die mathematische Intuition ("da ist jetzt eine Linie die zwischen zwei Punkten ist, und die hat eine andere Steigung, je nachdem wo man gerade ist"), das nächste die mathematischen Formeln (das, was in der Bachelorarbeit steht) und der dritte Schritt dann die Implementierung im Code. Hängt es also an Schritt 2 oder Schritt 3?
Die Formeln in Code umzusetzen sollte ja nicht so das Problem sein, das ist ja im Wesentlichen nur umformulieren. Und wenn das Probleme macht, dann hilft halt mehr Erfahrung und einfach viel üben. Wenns ein Problem mit den Formeln gibt, kann man das besser erklären.

[focus0941]

Ich würde eher sagen in Schritt 3, aber eigentlich auch in Schritt 2, da ich mir nicht sicher bin, ob das, was ich mache überhaupt richtig ist.
Momentan sieht mein Code so aus:

Code: Alles auswählen

    public static float[][] erode(float[][] terrain, int SIZE) {
        Random random = new Random();
        float velocity;
        float volume;
        float sediment;
        float u;
        float v;
        float inertia;
        Vector2f position;
        Vector2f gradient;
        Vector2f gradient_xy;
        Vector2f gradient_x1y;
        Vector2f gradient_xy1;
        Vector2f gradient_x1y1;
        Vector2f p_xy;
        Vector2f p_x1y;
        Vector2f p_xy1;
        Vector2f p_x1y1;
        Vector2f flowDirection = new Vector2f(1,1);
        flowDirection.normalise();
        float[][] erodedTerrain = terrain;

        for(int i = 0; i < 10000; i++) {
            position = new Vector2f(random.nextFloat(SIZE), random.nextFloat(SIZE));
            while(flowDirection.length() == 1) {
                //berechne p_xy, p_x1y, p_xy1, p_x1y1 aus position
                //berechne gradient_xy, gradient_x1y, gradient_xy1, gradient_x1y1
                //berechne gradient durch Interpolieren von gradient_xy, gradient_x1y, gradient_xy1, gradient_x1y1
                flowDirection = new Vector2f(flowDirection.x * inertia - gradient.x * (1 - inertia), flowDirection.y * inertia - gradient.y * (1 - inertia));
                position = new Vector2f(position.x + flowDirection.x, position.y + flowDirection.y);
            }
        }

        return erodedTerrain;
    }

[Jonathan]

Naja, gerade am Anfang macht es Sinn, das Problem in Einzelprobleme zu zerlegen, die du vernünftig testen kannst. Für diese Partikel könntest du z.B. erstmal Code schreiben, der dir den Verlauf eine Partikels anzeigt, damit du siehst, ob die Laufbahn richtig ist. z.B. eine Interaktive Anwendung wo du schon eine Landkarte hast und du klickst einen Punkt an und bekommst dann eine Linie angezeigt. Oder für die Subpixelkoordinaten könntest du ein weißes Bild nehmen und einen einzelnen roten Pixel auf 4 umliegende Pixel korrekt verteilen, je nach Subpixelkoordinate. Du könntest die Pixelposition dann interaktiv ändern und schauen ob die Interpolation korrekt aussieht. Gerade am Anfang sind so kleine Fingerübungen ganz gut um mehr Praxis zu bekommen.

[focus0941]

Das ist kein Problem, da es Pixel sind und man nur ganzzahlige Pixelkoordinaten auslesen kann.
Der Code ist aber trotzdem sehr umständlich. Hier beispielsweise, die Methode die den Displayinhalt malt:

Code: Alles auswählen

public void paint(Graphics g) {
        Random r = new Random();
        Graphics2D g2D = (Graphics2D) g;
        g2D.drawImage(map,0,0,null);
        g2D.setColor(Color.red);
        int x = 202;
        int y = 202;
        int difUL;
        int difML;
        int difOL;
        int difOM;
        int difOR;
        int difMR;
        int difUR;
        int difUM;

        for(int i = 0; i < 1000; i++) {
            if(x<=1 || y<=1 || x>=255 || y>=255 ){
                break;
            }

            difUL = map.getRGB(x,y)-map.getRGB(x-1,y-1);
            difML = map.getRGB(x,y)-map.getRGB(x-1,y);
            difOL = map.getRGB(x,y)-map.getRGB(x-1,y+1);
            difOM = map.getRGB(x,y)-map.getRGB(x,y+1);
            difOR = map.getRGB(x,y)-map.getRGB(x+1,y+1);
            difMR = map.getRGB(x,y)-map.getRGB(x+1,y);
            difUR = map.getRGB(x,y)-map.getRGB(x+1,y-1);
            difUM = map.getRGB(x,y)-map.getRGB(x,y-1);

            if( difUL > difML &&
                difUL > difOL &&
                difUL > difOM &&
                difUL > difOR &&
                difUL > difMR &&
                difUL > difUR &&
                difUL > difUM) {

                g2D.drawLine(x,y,x-1,y-1);
                x-=1;
                y-=1;
            }
            if( difML > difUL &&
                difML > difOL &&
                difML > difOM &&
                difML > difOR &&
                difML > difMR &&
                difML > difUR &&
                difML > difUM ){

                g2D.drawLine(x,y,x-1,y);
                x-=1;
            }
            if( difOL > difUL &&
                difOL > difML &&
                difOL > difOM &&
                difOL > difOR &&
                difOL > difMR &&
                difOL > difUR &&
                difOL > difUM) {

                g2D.drawLine(x,y,x-1,y+1);
                x-=1;
                y+=1;
            }
            if( difOM > difUL &&
                difOM > difML &&
                difOM > difOL &&
                difOM > difOR &&
                difOM > difMR &&
                difOM > difUR &&
                difOM > difUM) {

                g2D.drawLine(x,y,x,y+1);
                y+=1;
            }
            if( difOR > difUL &&
                difOR > difML &&
                difOR > difOL &&
                difOR > difOM &&
                difOR > difMR &&
                difOR > difUR &&
                difOR > difUM) {

                g2D.drawLine(x,y,x+1,y+1);
                x+=1;
                y+=1;
            }
            if( difMR > difUL &&
                difMR > difML &&
                difMR > difOL &&
                difMR > difOM &&
                difMR > difOR &&
                difMR > difUR &&
                difMR > difUM) {

                g2D.drawLine(x,y,x+1,y);
                x+=1;
            }
            if( difUR > difUL &&
                difUR > difML &&
                difUR > difOL &&
                difUR > difOM &&
                difUR > difOR &&
                difUR > difMR &&
                difUR > difUM) {

                g2D.drawLine(x,y,x+1,y-1);
                x+=1;
                y-=1;
            }
            if( difUM > difUL &&
                difUM > difML &&
                difUM > difOL &&
                difUM > difOM &&
                difUM > difOR &&
                difUM > difMR &&
                difUM > difUR) {

                g2D.drawLine(x,y,x,y-1);
                y-=1;
            }else{
                x += r.nextInt(2)-r.nextInt(2);
                y += r.nextInt(2)-r.nextInt(2);
                g2D.fillRect(x,y,1,1);
            }
        }
    }

[focus0941]

Mit der übersetzten Code aus dem Artikel, ist es jedoch viel sauberer, wie man erkennen kann.
Noch verändert sich das Relief aber nicht, es werden lediglich gelbe Eier erzeugt, die den Weg der Tropfen darstellen.

Code: Alles auswählen

public static float[][] erode(float[][] terrain, int SIZE) {
        Random random = new Random();
        float velocity;
        float volume;
        float sediment;
        float u = 0.2f;
        float v = 0.75f;
        float inertia = 0.5f;
        Vector2f position;
        Vector2f gradient;
        int x;
        int y;
        float P00;
        float P01;
        float P10;
        float P11;
        Vector2f flowDirection = new Vector2f(1,1);
        flowDirection.normalise();
        float[][] erodedTerrain = terrain;

        for(int i = 0; i < 10; i++) {
            position = new Vector2f(random.nextInt(SIZE - 1) + u, random.nextFloat(SIZE - 1) + v);
            for(int n = 0; n < 100; n++) {
            if(position.x < 2 || position.y < 2 || position.x > 254 || position.y > 254) {
                break;
            }
                u = (float) (position.x - Math.floor(position.x));
                v = (float) (position.y - Math.floor(position.y));
                x = (int) (position.x - u);
                y = (int) (position.y - v);
                P00 = erodedTerrain[x][y];
                P01 = erodedTerrain[x][y+1];
                P10 = erodedTerrain[x+1][y];
                P11 = erodedTerrain[x+1][y+1];
                gradient = new Vector2f((P10 - P00) * (1 - v) + (P11 - P01) * v, (P01 - P00) * (1 - u) + (P11 - P10) * u);
                flowDirection = new Vector2f(flowDirection.x * inertia - gradient.x * (1 - inertia), flowDirection.y * inertia - gradient.y * (1 - inertia));
                position = new Vector2f(position.x + flowDirection.x, position.y + flowDirection.y);
                MainGameLoop.entities.add(new Entity("egg", new Vector3f(position.x, erodedTerrain[x][y], position.y), 0, 0, 0, 1));
            }
        }

        return erodedTerrain;
    }

[Jonathan]

Ja ok, aber das sieht ja schonmal nach ganz gutem Fortschritt aus. Bin gespannt was noch daraus wird!

[focus0941]

Keine Ahnung, nach 10 Stunden Arbeit will es nicht funktionieren. Ich habe schon 3 Mal alles neu gemacht. Ich weiß auch nicht was falsch ist.

Code: Alles auswählen

public static float[][] erode(float[][] terrain, int SIZE) {
        Random random = new Random();

        Vector2f position;
        Vector2f flowDirection = new Vector2f(1,1);
        float water = 10;
        float velocity = 1;
        float sediment = 10;
        float capacity;

        float inertia = 0.5f;
        float minSlope = 0.5f;
        float carryCapacity = 0.5f;
        float deposition = 0.5f;
        float erosion = 0.5f;
        float gravity = 1;
        float evaporation = 0.5f;
        int maxSteps = 100;
        int steps;
        int dropCount = 10;

        Vector2f gradient;
        float P00, P01, P10, P11;
        float u, v;
        int x, y;
        float hdif, hold, hnew;

        for(int i = 0; i < dropCount; i++) {
            iterations = 0;
            position = new Vector2f(random.nextFloat(SIZE), random.nextFloat(SIZE));

            while(!(position.x < 2 || position.y < 2 || position.x > terrain.length - 3 || position.y > terrain.length - 3) && steps < maxSteps) {
                u = (float) (position.x - Math.floor(position.x));
                v = (float) (position.y - Math.floor(position.y));
                x = (int) (position.x - u);
                y = (int) (position.y - v);

                P00 = terrain[x][y];
                P01 = terrain[x][y + 1];
                P10 = terrain[x + 1][y];
                P11 = terrain[x + 1][y + 1];

                gradient = new Vector2f((P10 - P00) * (1 - v) + (P11 - P01) * v,
                        (P01 - P00) * (1 - u) + (P11 - P10) * u);

                flowDirection = new Vector2f(flowDirection.x * inertia - gradient.x * (1 - inertia),
                        flowDirection.y * inertia - gradient.y * (1 - inertia));

                hold = (P10 - P00) * (1 - v) + (P11 - P01) * v;
                        // ((P11 - P01) * u) + ((P10 - P00) * u) * v;

                position = new Vector2f(position.x + flowDirection.x, position.y + flowDirection.y);

                u = (float) (position.x - Math.floor(position.x));
                v = (float) (position.y - Math.floor(position.y));
                x = (int) (position.x - u);
                y = (int) (position.y - v);

                P00 = terrain[x][y];
                P01 = terrain[x][y+1];
                P10 = terrain[x+1][y];
                P11 = terrain[x+1][y+1];

                hnew = ((P11 - P01) * u) - ((P10 - P00) * u) * v;

                hdif = hnew - hold;

                velocity = (float)Math.sqrt(velocity * velocity + hdif * gravity);
                water = water * (1 - evaporation);
                capacity = Math.max(-hdif, minSlope) * velocity * water * carryCapacity;

                if(sediment > capacity) {
                    terrain[x][y] += (sediment - capacity) * deposition;
                    terrain[x][y+1] += (sediment - capacity) * deposition;
                    terrain[x+1][y] += (sediment - capacity) * deposition;
                    terrain[x+1][y+1] += (sediment - capacity) * deposition;
                    sediment--;
                } else {
                    terrain[x][y] -= Math.min((capacity - sediment) * erosion, -hdif);
                    terrain[x][y+1] -= Math.min((capacity - sediment) * erosion, -hdif);
                    terrain[x+1][y] -= Math.min((capacity - sediment) * erosion, -hdif);
                    terrain[x+1][y+1] -= Math.min((capacity - sediment) * erosion, -hdif);
                    sediment++;
                }

                steps++;
            }
        }
        return terrain;
    }

[focus0941]

Ich habe aber auch nicht (so ganz) verstanden wie das Terrain verändert und das Sediment berechnet wird.

[Jonathan]

Ich habe aber auch nicht (so ganz) verstanden wie das Terrain verändert und das Sediment berechnet wird.

Es geht noch um diese BA, oder? Was genau (d.h. welcher Satz) bereitet dir Probleme?

Grundsätzlich ist es ziemlich schwierig, Code anhand von Formeln zu schreiben, die man nicht ganz verstanden hat. Wenn es zwei oder 3 Zeilen sind, ist das ok. Aber du hast da ja eine knappe Seite, und das ist eigentlich schon so viel, dass man ihn weiter zerlegen muss, um ihn vernünftig debuggen zu können. Du musst irgendwie gucken, ob du Zwischenergebnisse verifizieren kannst. Beispielsweise werden da ja Gradienten und Flussrichtungen berechnet. Gibt es vielleicht einen Spezialfall wo du überprüfen kannst, ob die Richtung korrekt ist? Nützliche wäre es bestimmt auch z.B. erstmal mit einem einzigen Tropfen anzufangen. Oder statt eines komplizierten Terrains einfach mal eine Schräge Ebene zu nehmen oder so. Egal wie, du brauchst Zwischenschritte die du verstehst und überprüfen kannst und die kannst du dann auch gut debuggen. Und wenn alle Zwischenschritte gehen, sollte auch das ganze gehen.

Ein "Es geht nicht und ich weiß nicht, was falsch ist" ist halt auch keine gute Fehlerbeschreibung. Du müsstest mindestens mal beschreiben was passiert und was du stattdessen erwartest was passieren solltest. Und so eine Beschreibung liefert ja schonmal einen ersten Indikator, was falsch sein könnte.

[focus0941]

Also den Weg finden die Tropfen schon. Diesen Teil habe ich verstanden, aber das Abtragen und Auftragen funktioniert gar nicht.
Es entsteht lediglich ein unendlich tiefes Loch beim ersten Tropfen und bei x = 0, z = 0 und die restlichen Tropfen sind gar nicht existent.

[focus0941]

Mein Problem liegt bei den Formeln ab 5.3, also dort wo die Abtragung anfängt.

[focus0941]

Zum Beispiel weiß ich nicht, wie das Sediment berechnet wird oder was der Unterschied zwischen carryCapacity c, water und pCarycapacity ist.