Nochmals zu Voronoi-Diagrammen

Wie in den letzten Blog- Beiträgen geschrieben , hatte ich Probleme, in meinem Dragons Abound- Spiel die richtigen Details zur Küste zu finden. Meine Enttäuschung trat bei der Umsetzung der Barriereinseln auf . Um eine möglichst schmale Insel zu schaffen, habe ich sie einen Ort breit gemacht - in der folgenden Abbildung ist jeder Ort ein Delaunay-Dreieck:


Das war ziemlich unangenehm - sowohl weil die Insel sehr kaputt war als auch weil die Teile zu groß waren. Es schien, dass mit einer starken Zunahme der Anzahl der Delaunay-Dreiecke (dh mit einer starken Abnahme ihrer Größe) dieses Problem gelöst werden würde - aber die Dichte der benötigten Dreiecke führte zu einem Browserabsturz.

Ich habe dieses Problem gelöst, indem ich die Konturen des Landes von der internen Darstellung der Orte getrennt habe. Dadurch konnte ich Inseln jeder Größe und Form zeichnen, unabhängig vom zugrunde liegenden Standortraster:


Damit ist das Problem gelöst! Dadurch konnte ich die Barriereinseln zeichnen, und da die Küstenlinie nicht mehr dem Grundraster folgen muss, konnte bei Bedarf auf die übliche Weise eine detailliertere Küstenlinie erstellt und anschließend Details hinzugefügt werden.

Aber ... wie fügen wir der Küste Details hinzu? Es ist nicht so einfach, wie Sie vielleicht denken. Da ich eine fraktale Küste erstellen wollte, habe ich überlegt, Fraktale zu verwenden, um der Küste Details hinzuzufügen :


Nachdem ich mit den Einstellungen experimentiert hatte, konnte ich der Küste viele Details und interessante Dinge hinzufügen. Das System konnte jedoch keine ähnliche Karte erstellen:


Perlin-Rauschen kann diese Art von Gelände erzeugen, wenn ein ausreichend detailliertes Basisgitter vorhanden ist. Kann dies jedoch durchgeführt werden, ohne die Höhenhöhen im Basisgitter mit der gewünschten Auflösung zu speichern (schließlich weiß ich, dass dies meinen Code beschädigen wird)? Bis ich herausgefunden habe, wie es geht. Die Küstenlinie ist im Wesentlichen ein Pfad durch alle Punkte, an denen die Perlin-Rauschfunktion einen Nullwert hat. Obwohl wir den Wert an einer bestimmten Stelle (X, Y) direkt von der Perlin-Rauschfunktion lernen können, können wir nicht "alle Stellen finden, an denen die Funktion einen Nullwert hat". Das heißt, es ist schwierig zu erkennen, wie eine Höhenkontur ohne ein Grundgitter gezeichnet werden kann.

Schlimmer noch, ich fragte Amit, wie das geht, und er wusste auch nicht die Antwort. Es ist eine Sache, wenn ich das nicht sagen kann, aber wenn selbst solch ein intelligenter Mensch keine Antwort geben kann, beginne ich zu denken, dass dies nicht möglich ist. Es ist traurig. Ich kann der Küste jede Form geben, die ich brauche, aber ohne ein sehr detailliertes Grundraster kann ich nicht die Formen bekommen, die ich brauche.

Wie erhalte ich ein hochauflösendes Raster, ohne den Code zu beschädigen?

Eine der Lösungen, die mir in den Sinn kamen, erinnert mich an das, was Azgaar in seinem Kartengenerator getan hat - Voronoi-Zellen mit variabler Größe. Die Hauptidee besteht darin, die Dichte (und die Größe) des Grundnetzes entlang der Küsten zu erhöhen und eine geringere Dichte in den Ozeanen und anderen Gebieten beizubehalten, die keine Details erfordern. Mit dieser Option habe ich viele Netzzellen nur in Bereichen, in denen Sie Details benötigen. Diese Änderung wird in Dragons Abound ziemlich schwierig zu implementieren sein, aber ich möchte darüber nachdenken. Auf der anderen Seite war Azgaar selbst mit diesem Ansatz nicht sehr zufrieden , daher muss dies ebenfalls berücksichtigt werden.

Parallel dazu wollte ich die Ursachen eines Browserabsturzes bei der Verarbeitung eines Haufen Dreiecke untersuchen. Die Entwicklertools in Chrome lieferten mir detaillierte Leistungsinformationen. Ich bin kein Experte für die Verwendung dieser Tools, aber viele Funktionen sind so einfach, dass jeder sie verstehen kann. Wenn Sie die Gesamtmenge des im Programm verwendeten Speichers ermitteln möchten, enthält die Registerkarte Speicher Informationen zur aktuell verwendeten Kapazität:


In diesem Fall habe ich die Azgaar-Webseite geöffnet und sie beansprucht bescheidene 20 MB Speicher. Mit diesem Tool können Sie herausfinden, wie viel Speicher Dragons Abound belegt, und feststellen, wann die Registerkarte abstürzt.

Der grundlegende Parameter, der die Auflösung des zugrunde liegenden Netzes in Dragons Abound steuert, heißt geschickt „npts“ (Anzahl der Punkte). Für jede Einheitsfläche der Karte (Karten von Regionen, die ich normalerweise als Beispiele verwende, haben eine Fläche von 1 Einheit) Dragons Abound erstellt eine bestimmte Anzahl von Positionen des Basisgitters. Normalerweise verwende ich 16K (16384) für npts, was bedeutet, dass jede Rasterposition ungefähr 70 quadratischen Pixeln des Bildschirms bei einer Standard-Zoomskala entspricht.


Natürlich hängt die genaue Größe des verwendeten Speichers von der Karte ab, aber für die oben gezeigte Karte mit 16K-Punkten benötigen Sie ungefähr 92 MB:


Dies ist weniger als ich erwartet hatte und, um ehrlich zu sein, eine ziemlich bescheidene Zahl.

Wenn Sie die Anzahl der Punkte im Basisraster verdoppeln, erhöht sich die Speicherkapazität auf 138 MB:


Die Größe des belegten Speichers hat sich nicht verdoppelt, da ein Teil dieses Speichers von Ressourcen und anderen Datenstrukturen belegt ist, deren Größe sich nicht geändert hat. 16K zusätzliche Punkte "wiegen" ungefähr 50 MB Speicher, das heißt, jeder Punkt belegt ungefähr 3 KB Speicher. Dies ist mehr als ich erwartet hatte, aber im Allgemeinen ist die Lautstärke immer noch recht bescheiden. Auf einem Computer mit 64 GB Speicher sind 150 MB kaum wahrnehmbar.

Nachdem ich noch ein paar Doppel gemacht hatte, stellte ich fest, dass der Tab mit Dragons Abound normalerweise an ungefähr 128K Punkten abstürzt. Wenn wir es fangen, bevor es herausfliegt, und den Speicher überprüfen, sehen wir Folgendes:


Ich nahm an, dass die Registerkarte aufgrund des belegten Speichers abstürzt, aber normalerweise liegt das Problem nicht im Speicher. Warum stürzt die Registerkarte ab? Der einzige Hinweis ist, dass die Registerkarte nicht abstürzt, bevor die Karte fertig ist. Dies ist wahrscheinlich ein Hinweis darauf, dass beim Rendern ein Absturz auftritt.

Es ist logisch anzunehmen, dass das von mir erstellte SVG den Browser-Renderer aufgrund seiner Größe oder Komplexität überlastet. Zunächst kann ich herausfinden, wie viele SVG-Elemente ich erstelle. In D3 kann ich die Gesamtzahl der SVG-Elemente svg.selectAll('*').size() die mit svg.selectAll('*').size() .

Aus 16K-Punkten zu laufen und die Anzahl der SVG-Elemente zu überprüfen, zeigte mir Folgendes:


32K-Punkte haben 65457 Elemente und 128K-Punkte haben 258823. Jeder Punkt, der dem Basisraster hinzugefügt wird, fügt der Karte zwei Elemente hinzu. Ich glaube, ich habe eine Quelle des Unglücks gefunden.

Jeder Punkt im Basisraster fügt SVG-Elemente hinzu, da Dragons Abound Land (und Wasser) rendert . Land wird gerendert, indem jeder Basisort als gefülltes Polygon gerendert und anschließend alle verwischt werden. Auf diese Weise können Dragons Abound dem Land ein schönes Muster geben oder die Höhe des Landes verwenden, um das Land mit 3D-Schattierung zu rendern, wie hier gezeigt:


Sie können die Visualisierung von Land und Meer deaktivieren, um zu überprüfen, wie viele SVG-Elemente erstellt wurden. Bei 256K Punkten:


Wow, die Anzahl der SVG-Elemente ist deutlich gesunken. Wie ich gehofft habe, wird die Karte jetzt ohne Absturz gerendert! Wenn Sie also vermeiden, ein Raster zum Rendern von Land und Wasser zu verwenden, können Sie ein viel dichteres Raster als zuvor erstellen.

Jetzt, da ich ein viel dichteres Voronoi-Gitter habe, möchte ich prüfen, ob es mir ermöglicht, die benötigten Landentlastungselemente wie Küsteninseln zu erzeugen. Das dichte Netz von Voronoi verursacht andere Probleme (insbesondere bei Flüssen). Daher schalte ich alles außer den Küsten aus, um die Tests zu beschleunigen und mich auf sie zu konzentrieren. Hier ist das Original-Rendering einiger Küstenlinien mit 256 KB Pixel und Standardrauschen:


Es stellt sich heraus, dass die Karte gut rendert und bereits eine viel schönere Küste schafft.

Auch ohne sorgfältige Abstimmung ist das Ergebnis viel besser. Der Lärm erzeugt die Arten von fraktalen Küsten und Küsteninseln, die ich auf der Karte oben angegeben habe.

Hier sind die Inseln mit einem Anstieg von 300%:


Mit dieser Erhöhung können Sie Artefakte von Dreiecken aus dem Basisgitter erkennen, aber dennoch können Inseln interessante Formen erzeugen. Sie können Anti-Aliasing verwenden (wie ich es in der aktuellen Version von Karten tue), um einige der auffälligsten Artefakte von Dreiecken zu entfernen. Bei Standardvergrößerung bietet dies eine weniger raue Küste, eliminiert jedoch auch einige kleine Details:


Sie müssen sich wahrscheinlich einstellen, um einen Mittelweg zu finden.

Die meisten prozeduralen Sushi-Generatoren verwenden Perlin-Rauschen, um eine Höhenkarte zu erstellen. Wir müssen die geeigneten Geräuschparameter finden, einen Startwert auswählen und dann den Geräuschwert an jedem Ort (x, y) verwenden, um die Landmasse festzulegen. Ein praktischer Aspekt beim Erstellen von Land ist, dass Sie die Geräuschparameter einfach anpassen können, wenn Sie weitere Details zur Küste benötigen.

Dragons Abound schafft jedoch kein Land auf diese Weise. (Oder zumindest schafft es mehr als das.) Dragons Abound verwendet viele verschiedene Methoden, um Sushi zu kreieren. Obwohl sie alle bis zu dem einen oder anderen Grad Lärm verwenden, schaffen nur sehr wenige Land direkt aus Lärm. Das Spiel verfügt beispielsweise über ein Verfahren zum Erstellen einer Insel, bei dem eine Maske für die Insel erstellt wird (normalerweise eine Ellipse), Rauschen verwendet wird, um die Ellipse natürlicher zu gestalten, und dann ein anderes Rauschen angewendet wird, um die Maske ungefähr zu füllen. Jede bestimmte Karte wird normalerweise durch eine Kombination mehrerer verschiedener Verfahren erstellt. Daher ist das Hinzufügen von Details durch Anpassen der Rauschparameter für Dragons Abound nicht sehr geeignet.

Für meine Zwecke ist es besser, das Problem aus einem etwas anderen Blickwinkel zu betrachten. Wenn ich eine bestimmte Höhenkarte habe, die Landmassen definiert, wie füge ich dann Details zu den Rändern dieser Landmassen hinzu? Dies könnte uns zu der Idee führen, dass wir die Ränder von Landmassen erkennen und den Rest der Karte usw. maskieren müssen. Andererseits bin ich überhaupt nicht dagegen, dem Rest der Karte zusätzliche Details hinzuzufügen. Wenn das Land etwas unebener ist oder der Grund des Ozeans etwas rauer ist, ist dies normal.

Was bedeutet das Hinzufügen von Details zur Küste? Eine Küstenlinie ist einfach eine Konturlinie, in der eine Höhenkarte den Wert Null hat. (Der Wert ist willkürlich, aber ein solches Prinzip wird in jedem prozeduralen Landgenerator verwendet.) Um diese Linie detaillierter zu gestalten, müssen Sie das Land neben dieser Konturlinie leicht nach oben und unten verschieben, damit einfache Küsten komplexer werden und Teile des Landes in den Ozean hineinragen und werden Inseln und so weiter. Dies sollte aber nicht zufällig geschehen, ich möchte, dass die Änderungen natürlich erscheinen. Wir fassen dies alles zusammen und es scheint, dass Sie der gesamten Karte ein wenig Rauschen hinzufügen müssen. Und genau das habe ich im oben gezeigten Originalbeispiel getan.

Dies muss natürlich sorgfältig geschehen, um die geschaffenen Landmassen nicht zu löschen und andere Probleme zu verursachen. Im Wesentlichen muss ich drei Parameter konfigurieren.

Das erste ist die Skala des Rauschens. Eine Skala ist einfach ein Werteintervall für dieses Rauschen. In unserem Fall möchte ich einige Bereiche senken und einige erhöhen, sodass der Wertebereich von negativ bis positiv reichen sollte. Ich möchte jedoch keine neuen Berge hinzufügen oder einen Ozean weit entfernt von der vorhandenen Küste schaffen, daher werde ich den maximalen (absoluten) Wert des Lärms zu einem kleinen Bruchteil der Standardlandhöhe machen.

Der zweite Parameter ist die Hauptfrequenz des Rauschens. Die Frequenz bestimmt, wie schnell sich das Rauschen innerhalb des Standorts ändert. Niederfrequentes Rauschen ändert sich sehr langsam, sodass ein positiver Bereich mit niederfrequentem Rauschen (sagen wir) die gesamte Karte abdecken kann. Hochfrequenzrauschen ändert sich schnell, so dass ein positiver Bereich mit Hochfrequenzrauschen (sagen wir) die Größe einer kleinen Insel haben kann. In unserem Fall bestimmt die Hauptrauschfrequenz die größten Reliefelemente, die wir im Rauschen sehen werden. Das heißt, wenn das Rauschen kleine Inseln (aber nichts Größeres als diese) zur Karte hinzufügen soll, muss ich die Hauptfrequenz in der Größe einer kleinen Insel auswählen.

Sie könnten denken, dass dies einfach ist (messen Sie einfach eine kleine Insel und weisen Sie diese Größe der Hauptfrequenz zu). Die Frequenz wird jedoch in den Koordinaten der Rauschfunktion gemessen, nicht in den Koordinaten der Karte! Eine typische Rauschfunktion kann in jeder Koordinate ein Intervall von 0 bis 255 haben, und eine Karte kann in jeder Koordinate ein Intervall von -1 bis 1 haben. Schlimmer noch, die Rauschkoordinaten sind reduziert, und viele Benutzer, die Rauschen verwenden, erkennen dies nicht einmal. Die Übersetzung von einer Einheit in eine andere und die Bestimmung geeigneter Frequenzen ist verwirrend. Daher ist es normalerweise am einfachsten, nur mit Frequenzintervallen zu experimentieren und diejenige auszuwählen, mit der die Kartenelemente mit der richtigen Größe erstellt werden.

Der dritte Parameter ist die Anzahl der Oktaven des Rauschens. Oktaven sind zusätzliche Rauschschichten. Jede Schicht verdoppelt normalerweise die Frequenz und halbiert die Rauschskala. Das heißt, jede neue Ebene fügt Reliefelemente zweimal weniger als die vorherige Ebene hinzu, aber auch zweimal schwächer. Das heißt, Sie müssen die Anzahl der Oktaven auswählen, die die wenigsten Elemente ergeben, die wir benötigen. Dazu müssen Sie möglicherweise die Rauschskala anpassen, da sie in der höchsten Oktave immer noch stark genug ist, um auf der Karte angezeigt zu werden. Da ich dies absichtlich mache, um die Küsten sehr kompliziert zu machen, werde ich einige Oktaven Lärm verwenden.

Beginnen wir mit dem Setup. Zu Beginn werde ich eine Beispielkarte ohne zusätzliches Rauschen erstellen:


Offensichtlich ist dies eine langweilige Küste mit glatten Linien und nur ein paar großen Inseln. Hier ist die gleiche Küste mit dem ursprünglichen Geräuschbeispiel:


Das Rauschen veränderte die Form der Karte erheblich und verwandelte große Landfragmente in einen Ozean und umgekehrt. Viele Inseln erschienen auch, auch weit ins Meer. All dies deutet darauf hin, dass die Rauschskala zu groß ist. Die größten einzelnen Reliefelemente, die durch Rauschen hinzugefügt werden, sollten die Größe der kleinen Inseln der Originalkarte sein. Dies ist wahrscheinlich die maximale neue Größe der Elemente, was beweist, dass die Hauptfrequenz des Rauschens ungefähr richtig gewählt ist. Schließlich erschienen viele kleine Details bis an die Grenzen der Anzeigegröße, und dies zeigt, dass genügend Oktaven vorhanden sind. (Die Anzahl der Oktaven kann jedoch höher als erforderlich sein. Dies wirkt sich nicht auf das Erscheinungsbild der Karte aus, ist jedoch ineffizient.) Grundsätzlich müssen Sie die Rauschskala anpassen.

Das Einstellen des Geräusches ist eine ziemlich komplizierte Operation, da ich möchte, dass dieses Geräusch hauptsächlich Land und Wasser an einer Konturlinie mit einer Höhe = 0 beeinflusst. Das heißt, ich benötige einen relativ kleinen Maßstab, aber es ist nicht klar, wie die richtige Zahl zu wählen ist, weil In verschiedenen Karten variiert die Höhenverteilung. Die Lösung besteht darin, im Handumdrehen die richtige Skala zu finden. Sie können alle absoluten Werte der Höhen auf der Karte nehmen, sie sortieren und den Grenzpunkt finden, der (sagen wir) 10% der Orte um Null auswählt. Alle diese Stellen fallen in das Intervall (zum Beispiel) [-0,05, 0,05], und dann kann ich den Wert 0,05 verwenden, um die Skala des hinzugefügten Rauschens zu bestimmen.

(Ich schreibe "Definitionen", weil Sie aus verschiedenen Gründen nicht nur 0,05 verwenden können. Zuerst müssen Sie Land in Wasser verwandeln und umgekehrt. Wenn Sie (sagen wir) 0,002 bis -0,05 hinzufügen, werden keine sichtbaren Änderungen an der Karte vorgenommen. Das heißt, das Intervall sollte viel mehr als 0,05 betragen Wenn ich einen signifikanten Anteil von Orten mit einer Höhe von -0,05 von Wasser in Land umwandeln möchte, sind die Rauschfunktionen nicht gleichmäßig verteilt , sodass die Rauschfunktion bei einer Skala von 0,05 niemals den Wert 0,05 zurückgibt. In der Praxis besteht die Schwierigkeit darin Der Maßstab sollte viel größer sein als die größten Werte, die wir oft genug sehen wollen.)

Nachdem ich experimentiert hatte, fand ich einen Wert, der die Küsten komplexer macht, ohne sie wesentlich zu verändern, und auch eine kleine Anzahl von Inseln schafft:


Wie immer können diese Parameter im Spiel ein Intervall von Werten annehmen, sodass ich eine große Auswahl an Karten erhalten kann: von Karten mit ziemlich glatten Küsten bis zu Karten mit kaputten und komplexen Ufern. Wenn ich das Programm die Werte auswählen lasse, erhalte ich das folgende Ergebnis:


Die Küsten sind glatter, aber es gibt immer noch den größten Teil der zusätzlichen Komplexität des mittleren Maßstabs und eine ausreichende Anzahl neuer Inseln.

Bei der Implementierung fraktaler Küsten erkannte ich die Möglichkeit, den Grad der Fraktalisierung mithilfe der Rauschfunktion zu steuern, sodass einige Gebiete glatte Küsten haben, während andere komplexe haben. Ich dachte, dass dies das Interesse der Karte stark erhöhen würde und weniger "generiert" aussehen würde, daher werde ich diese Funktion hier hinzufügen. Die Idee ist ganz einfach: Bevor ich der Karte Küstenrauschen hinzufüge, multipliziere ich es mit der Ausgabe der zweiten Rauschfunktion, die von Null bis 1 reicht. Wenn diese Funktion klein ist, werden den Küstenlinien kleine Details hinzugefügt. Wenn es nahe bei 1 liegt, werden zusätzliche Details vollständig hinzugefügt. Wenn ich den Maßstab der zweiten Rauschfunktion auswähle, der sich langsam auf der Karte ändert, erhalte ich einige Gebiete mit komplexen Küstenlinien, einige mit einfachen und logischen Übergängen zwischen ihnen:


Hier habe ich die Küstenparameter groß gemacht, damit der Unterschied besser sichtbar wird. Wir sehen wilde, zerklüftete Küsten im Nordosten und glattere Strände im Westen.

Wir haben die Erzeugung der Küstenlinie erheblich verbessert, aber ich kann immer noch keine Karte mit so vielen Delaunay-Dreiecken vollständig erstellen. Ich zeige nur Umrisskarten, weil viele andere Kartenelemente beschädigt sind. Es muss behoben werden.

Der Rest des Programms funktioniert nicht so gut mit so vielen Delaunay-Dreiecken (mit aktuellen Einstellungen von 256 KB). Das Hauptproblem ist, dass Dragons Abound Land und Wasser zeichnet, indem alle einzelnen Dreiecke gezeichnet werden, und so viele SVG-Elemente den Browser zum Absturz bringen. Also musste ich das Sushi-Rendering komplett deaktivieren. Es gibt wahrscheinlich einen Weg, um dieses Problem zu umgehen, aber so viele Dreiecke zu haben, schafft andere Probleme. Beispielsweise müssen einige Teile des Programms die gesamte Karte verarbeiten. Jeder von ihnen wird an 256K-Standorten sechzehnmal langsamer als an 16K-Standorten. Auch im Code gibt es Teile (zum Beispiel ein neues Niederschlagsmodell), die beim Arbeiten mit so vielen Dreiecken brechen. Und durch die Erstellung eines so detaillierten Standortrasters gewinnen wir nichts - nach der Erstellung der Küste verbessert sich nichts durch die zusätzliche Komplexität. Obwohl ich das Programm überprüfen und die Bereiche reparieren konnte, in denen eine große Anzahl von Orten den Code verlangsamt oder zu stark bricht, scheint es daher einfacher zu sein, die Auflösung des Kartenrasters nach dem Erstellen von Küstenlinien zu verringern.

Wie oben erwähnt, hat Azgaar bereits daran gearbeitet , die Auflösung des der Karte zugrunde liegenden Voronoi-Gitters zu ändern. Er erkannte die Möglichkeit, die Gitterauflösung im Generationsprozess im laufenden Betrieb zu ändern, dh er könnte (zum Beispiel) die Dichte der Standorte entlang der Küste erhöhen. Eine lokale Änderung der Dichte hat jedoch ihre Nachteile - insbesondere entstehen seltsame Dreiecke entlang der Grenze. Azgaar schlug später vor, dass das System zu komplex und die Mühe nicht wert sei. Azgaar weiß normalerweise, wovon er spricht, also werde ich sein Wort dafür nehmen und nicht versuchen, das fertige Netz neu zu verpacken.

Stattdessen habe ich ein zweites Raster mit der gewünschten (niedrigeren) Auflösung erstellt und dann die Höhenkarte in dieses neue Raster kopiert. (Vergessen Sie nicht, dass Dragons Abound die Küsten jetzt getrennt vom Raster speichert, sodass sie nach ihrer Erstellung nicht mehr von der genauen Anpassung des Rasters abhängen. Dies ist etwas kompliziert. Da das ursprüngliche Raster eine viel höhere Auflösung als das neue hat, befinden sich viele Stellen im Original Das Raster wird an einer Stelle im neuen Raster überlagert. Jeder dieser Quellorte hat eine andere Höhe auf der Höhenkarte. Wie kann ich sie kopieren? Verwenden Sie den Durchschnitt oder die maximale (minimale) Höhe.

Zu Beginn wähle ich nur einen zufälligen Ort aus, um zu sehen, ob das neue Raster mit dem Rest des Programms funktioniert:


Alles lief überraschend gut. Ein kleiner Fehler tritt auf, wenn neue Standorte nicht ordnungsgemäß als Land, Küste oder Wasser markiert sind. Nach dem Lösen dieses Problems funktionierte die Kartengenerierung jedoch einwandfrei. Sie müssen kleinere Fehler beseitigen (z. B. das Palmanor-Tag, das auf dem Wasser herauskam), aber insgesamt sieht es gut aus. Sogar die winzigen Inseln waren wunderschön.

Am Ende entschied ich, dass mit einer Verringerung der Auflösung des Voronoi-Gitters jeder Standort der Durchschnitt der Basisstandorte sein würde. Dies scheint eine kluge Entscheidung zu sein und kann bei Bedarf jederzeit geändert werden. Dieses Bild zeigt, wie die Küstenlinien vom fertigen Netz getrennt wurden:


Zusammenfassend lässt sich sagen : In Dragons Abound wird beim Generieren der Höhenkarte ein sehr hochauflösendes Delone-Dreiecksgitter verwendet. Nach seiner Fertigstellung definiert Dragons Abound Küstenlinien, indem Übergänge von negativen zu positiven Werten in der Höhenkarte verfolgt werden. Anschließend kopiert das Spiel das hochauflösende Raster in ein Raster mit viel niedrigerer Auflösung und mittelt die Positionen, die in eine Position des neuen Rasters fallen. Als nächstes wird das hochauflösende Raster verworfen, und der Rest der prozeduralen Generierung und Visualisierung wird auf dem niedrigauflösenden Raster fortgesetzt. Eine interessante Frage ist, ob die Verwendung des Delaunay-Netzes zu diesem Zeitpunkt von irgendeinem Wert ist. Es könnte sich lohnen, in ein Sechseckraster oder ähnliches zu kopieren.