Delaunay-Triangulation. Wo soll man anfangen?

7

Ich versuche, prozedurale Generierungstechniken zu lernen. Speziell für Dungeons. Ich habe mit einem 2D-Array angefangen und meine Räume gut generiert. Jedes Zimmer enthält Wandfliesen (siehe Abbildung unten).

! [generierte Räume] http://i.imgur.com/JpYLKip.png

Im Moment benutze ich A *, um die Räume miteinander zu verbinden. Dies hat jedoch einige Wege, die direkt durch andere Räume oder um Räume herum führen. Nachdem ich ein bisschen gegoogelt hatte, fand ich diese Demo, die mich auf die Idee brachte, Delaunay Triangulation zu verwenden, um die Räume richtig zu verbinden, ohne bereits vorhandene Verbindungen / Räume zu durchlaufen.

Aber wie wende ich es auf mein 2D-Array-Setup an? Mein erster Gedanke ist, dass ich über den Tellerrand hinaus denken sollte (2d Array haha) und meine Räume greifen und daraus ein vollständiges Diagramm erstellen und dann die Delaunay-Triangulation anwenden sollte.

Ich habe noch nie etwas mit Grafiken gemacht. Was ich also wissen möchte, ist: a) Ist mein Denken richtig, wenn ich das Diagramm mit allen verknüpften Räumen erstelle und dann die Triangulation anwende und b) wo soll ich anfangen?

[kleine Bearbeitung] Nachdem ich mich ein bisschen mehr im Stackoverflow umgesehen hatte, fand ich diesen Beitrag, in dem die Grafiken ausführlicher erklärt wurden. /programming/15306040/generate-an-adjacency-matrix-for-a-weighted-graph

path-finding procedural-generation graph triangulation Superflach
quelle
Ich folge nicht ganz dem, wofür Sie die Delaunay-Triangulation verwenden möchten. Ist die Idee, dass Sie einen Scheitelpunkt pro Raum einfügen und die Kanten der Triangulation als Verknüpfungen zwischen Räumen verwenden? Wie kommt A * in all das? Schließlich, wenn Sie wissen wollen , wie zu tun Delaunay - Triangulation, google es einfach. Es gibt Unmengen von Artikeln, ganz zu schweigen von Bibliotheken.
Nathan Reed
3
Was hast du versucht? Was ist Ihre eigentliche Frage? Dies ist eine Q & A-Site, kein allgemeines Diskussionsforum. Leider ist es kein Thema, nur nach Tipps oder Vorschlägen zu fragen.
Sean Middleditch

Antworten:

9

Das ist eine nette Demo. Die beste Referenz für Delaunay-Triangulationen und Voronoi-Diagramme, die ich gefunden habe, ist Jonathan Shewchuks Buch und Vorlesungsnotizen . Das Buch ist wesentlich weiter fortgeschritten als die Vorlesungsunterlagen und befasst sich mehr mit der Verfeinerung von Maschen . Ich schlage vor, Sie beginnen mit den Vorlesungsunterlagen.

Müssen Sie zur Schule gehen, um eine Delaunay-Triangulation zu erzeugen? Mist nein! Eine Delaunay-Triangulation ist nur die eindeutige Triangulation, so dass der Umkreis jedes Dreiecks (scrollen Sie nach unten zu Shewchuks Antwort) nur die 3 Eckpunkte jedes Dreiecks und nichts weiter einschließt.

Geben Sie hier die Bildbeschreibung ein (Bild aus Shewchuks Vorlesungsunterlagen, oben verlinkt)

Algorithmen

Ein Artikel, der zwei Algorithmen zur Konstruktion einer Delaunay-Triangulation beschreibt, ist ein guter Anfang.

Die Hauptmethode, über die die Leute sprechen, besteht darin, zuerst das Voronoi-Diagramm zu erstellen.

Geben Sie hier die Bildbeschreibung ein

Fortunes Algorithmus

Ich kann Ihnen hier nur ein paar Hinweise geben, nachdem ich angefangen habe, mit dem Fortune-Algorithmus zu arbeiten, aber das Projekt abgebrochen habe, weil Fortunes Code extrem schwer zu verstehen ist. Es ist eine JavaScript - Implementierung hier .

Ein paar andere Fortune-Ressourcen:

Ich weiß, dass ich hier viele Links gepostet habe, aber mein Rat ist, den Fortune-Algorithmus zu vermeiden . Eine einfachere Möglichkeit besteht darin, die unten beschriebenen Kippkanten zu verwenden.

Kanten umdrehen

Ein viel einfacherer Weg, dies zu tun, heißt Flipping Edges . Was Sie tun, ist mit einer beliebigen Triangulation zu beginnen und dann einfach "Kanten umzudrehen", so dass jedes Dreieck zu "Delaunay" wird (der Kreis jedes Dreiecks enthält keine anderen Punkte als seine eigenen 3 Eckpunkte). Sobald alle Tris Delaunay sind, haben Sie die Delaunay-Triangulation.

Bobobobo
quelle
Danke @bobobobo. Sehr informativ! Haben Sie Ressourcen, die zeigen, wie Sie mit der Implementierung einiger dieser Algorithmen beginnen können? Ich weiß jetzt, dass ich kein Diagramm haben muss, um eine Triangulation durchzuführen, sondern nur eine Reihe von Punkten, die ich habe. Nachdem ich das triangulierte Diagramm habe, kann ich Dinge wie minimale Spannbäume ausführen, um interessantere Ergebnisse zu erzielen.
Superflat
Wenn Sie nur eine Reihe von Punkten haben, können Sie entweder den Fortune-Algorithmus O (nlogn) verwenden oder einfach versuchen, mit allen anderen Punktpaaren Dreiecke zu bilden . Nur dann wirklich Dreiecke bilden, wenn der Dreieckskreis keine anderen Punkte einschließt
Bobobobo
Wenn Sie dies zum Generieren von Navigationsnetzen verwenden, müssen Sie sich darüber im Klaren sein, dass Delaunay nur für konvexe Polygone funktioniert. Wenn Sie also Ihr Netz nicht zerschneiden und die konvexen Unterteile triangulieren möchten, suchen Sie in dieser Frage nach Alternativen. Bearbeiten: Es scheint erweiterte Versionen von Delaunay zu geben, die anscheinend komplexere Strukturen unterstützen.
PeterT
@PeterT Nein, es geht nur darum, die Raumkonnektivität zu bestimmen. Ich möchte die Verwendung eines Navmesh vermeiden und einfach A * verwenden, um über das quadratische Gitter zu iterieren ... Obwohl ... ich das Mesh nach der Generierung immer kombinieren und dann einen Navmesh-Generator ausführen könnte.
Superflat