Kürzlich habe ich mehrere Roguelike gespielt, also habe ich beschlossen, meinen eigenen prozeduralen Dungeon-Generator zu schreiben. Es gibt viele Möglichkeiten, dieses Problem zu lösen, und ich habe den hier beschriebenen Algorithmus des Autors TinyKeep gewählt. Ich habe diesen Algorithmus so erweitert, dass er in 3D funktioniert und mehrstöckige Dungeons erstellen kann.
Beispielcode im
Github-Repository . Zur Demonstration verwende ich Unity3D, aber diese Konzepte gelten natürlich für jede andere Engine.
Zwei Dimensionen
Zuerst muss ich einen Algorithmus für zwei Dimensionen schreiben. Im Allgemeinen funktioniert es genauso wie der TinyKeep-Algorithmus, weist jedoch Unterschiede zum Erstellen interessanterer Ebenen auf.
Die Szene für dieses Beispiel heißt Dungeon2D. Der Code dafür befindet sich im Ordner Scripts2D.
Algorithmus
Die Welt ist in ein rechteckiges Gitter unterteilt. Ich gehe davon aus, dass 1 Einheit ausreicht, um den Korridor anzuzeigen. In einem vollständigen Spiel kann 1 Einheit der Einheit beispielsweise 5 Metern entsprechen. Für das Raster habe ich eine Größe von 30 × 30 gewählt.
1. Wir ordnen die Räume beliebig an, aber ohne dass sie sich überschneiden. Der Ort spielt keine Rolle, also gebe ich ihnen in diesem Beispiel nur einen zufälligen Ort und eine zufällige Größe. Außerdem habe ich auf jeder Seite einen Puffer mit einer Breite von 1 Einheit hinzugefügt (damit sich die Räume nicht berühren), aber dies ist nicht erforderlich, damit der Algorithmus funktioniert.
Rote Rechtecke sind Räume2. Erstellen Sie ein Delaunay-Triangulationsdiagramm für Räume. Ich habe dafür den Bower-Watson-Algorithmus verwendet. Es gibt viele Implementierungen dieses Algorithmus in vielen Sprachen. Ich habe eine ausgewählt, die sich leicht nach C # portieren lässt.
Delaunay-Triangulation3. Erstellen Sie einen Minimum Spanning Tree (MST) aus der Triangulation. Ich habe dafür den Prim-Algorithmus verwendet.
MST-Korridore4. Wir erstellen eine Liste von Korridoren, beginnend mit jeder Kante des Baums ab Stufe 3. Der Baum enthält alle Räume, sodass der Weg zu jedem Raum garantiert vorhanden ist. Fügen Sie der Liste die Kanten aus der Triangulation nach dem Zufallsprinzip hinzu. Wir werden also mehrere Schleifen in den Korridoren erstellen. In meinem Code habe ich die Wahrscheinlichkeit verwendet, dass jede Kante zu 12,5% addiert wird.
Korridore nach dem Hinzufügen mehrerer Kanten zum MST. Beachten Sie, dass Schleifen aufgetreten sind.5. Verwenden Sie für jeden Korridor in der Liste den A * -Algorithmus, um die Pfade vom Anfang des Korridors bis zum Ende zu ermitteln. Nachdem ein Weg gefunden wurde, ändert sich der Zustand der Welt, sodass zukünftige Korridore immer vorhandene umgehen können.
Die Kostenfunktion, die ich verwendet habe, macht es weniger kostspielig, sich entlang eines Korridors zu bewegen, der in einer anderen Iteration geschnitten wurde als das Erstellen eines neuen Korridors. Dies regt einen Wegfindungsalgorithmus an, um Korridore, die durch einen Raum verlaufen, zu kombinieren. Bewegung durch den Raum ist möglich, aber teuer. In den meisten Fällen vermeidet der Pfadfindungsalgorithmus daher lieber Räume.
Blaue Rechtecke sind KorridoreHier sind einige Beispiele für einen Algorithmus, der reale grafische Ressourcen verwendet (Ressourcen und Code für ihre Platzierung befinden sich nicht im Repository):
Drei Dimensionen
Nachdem ich einen funktionierenden 2D-Dungeon-Generator erstellt hatte, begann ich, ihn auf 3D zu übertragen. Alle verwendeten Algorithmen haben 3D-Versionen, es sollte also einfach sein, oder?
Algorithmus
Das Raster hat jetzt eine Größe von 30x5x30.
1. Die erste Änderung war die Erzeugung von Räumen in 3D. Diese Änderung ist trivial.
Bitte beachten Sie, dass die Zimmer mehrere Etagen hoch sein können.2. Dann finden wir die Delaunay-3D-Triangulation dieser Räume bzw. die Delaunay-Tetraeder. Nach der Suche nach Informationen zu den Abfragen „3D-Delaunay-Triangulation“ oder „Delaunay-Tetraederisierung“ habe ich viele Forschungsartikel gefunden, aber kein einziges Codebeispiel.
Das, was ich am ehesten brauchte, war die Implementierung der 3D-CGAL-Triangulation, aber es gab zwei Probleme. Erstens war dieses Modul nur unter der GPL-Lizenz verfügbar. Der zweite - der Code war so viel Vorlage und undurchsichtig, dass ich nicht herausfinden konnte, wo der Algorithmus implementiert wurde.
Am Ende musste ich das Prinzip des Bower-Watson-Algorithmus selbst studieren, um es selbst zu ändern. Ich verstehe immer noch nicht wirklich, warum die umschriebenen Kreise so wichtig sind, aber zumindest konnte ich den Algorithmus mit den beschriebenen Kugeln auf
dieser Seite mit Wolfram MathWorld umschreiben. Da es sich hauptsächlich um Operationen mit 4x4-Matrizen handelt, habe ich die gesamte komplexe Arbeit dem
Matrix4x4 Typ von Unity3D zugewiesen.
Diese neue Version befindet sich in
Scripts3D/Delaunay3D.cs , falls jemand einen leicht verständlichen Code mit einer MIT-Lizenz benötigt.
Es ist schwer zu bemerken, aber anstelle eines Dreiecks mit drei Eckpunkten erstellt der Algorithmus jetzt einen Tetraeder mit 4 Eckpunkten. Mindestens einer dieser Peaks befindet sich in einem anderen Stockwerk, da sonst das Tetraeder entartet ist. Dies gibt der Suchphase viele Möglichkeiten, sich zwischen den Stockwerken zu bewegen.
Die Kanten aus Stufe 2 mit völlig unbedeutenden Änderungen können an den Prim-Algorithmus übergeben werden.
3D-MST-KorridoreKorridore mit mehreren Rippen wieder hinzugefügt5. Schwierigkeiten beginnen bei der Implementierung in 3D-Algorithmus A *. Die 2D-Version ist schrecklich einfach, es ist eine Standardimplementierung von A *. Um es auf 3D zu übertragen, muss der Pfadsuchalgorithmus um die Fähigkeit erweitert werden, sich auf und ab zu bewegen und Räume auf verschiedenen Etagen zu verbinden. Ich beschloss, die Etagen nicht mit senkrechten Treppen zu verbinden, sondern mit Treppenläufen.
Das ist das Problem. Eine Treppe ist komplizierter als nur hochzuklettern. Um sich vertikal zu bewegen, müssen sich die Treppen horizontal bewegen. Das heißt, sie hat einen
Aufstieg und eine
Spannweite . Schauen Sie sich das Bild unten an. Die aktuelle Zelle ist ein ausgefülltes blaues Quadrat. Mögliche Nachbarn sind leere Quadrate. Der Pfadsuchalgorithmus kann nicht zu einer Zelle direkt über der aktuellen Zelle verschoben werden. Stattdessen muss er sich sowohl horizontal als auch vertikal bewegen.
Seitenansicht Sie können Knoten an den Seiten erstellen, aber keinen Knoten an der Spitze.Um einen Pfadsuchalgorithmus für eine Treppe zu erstellen, musste ich ihre Form auswählen. Ein Verhältnis von Höhe zu Länge von 1: 1 wäre zu steil, deshalb habe ich ein Verhältnis von 1: 2 gewählt. Für jede vertikale Maßeinheit bewegt die Leiter zwei horizontale Einheiten. Außerdem muss über der Treppe Platz sein, damit die Figur platziert werden kann. Das heißt, zwei Zellen über der Treppe müssen ebenfalls offen sein. Im Allgemeinen belegt eine Treppe vier Zellen:
Treppe und Freiraum darüberEs sollte auch einen Korridor am oberen und unteren Ende der Treppe geben. Der Pfadsuchalgorithmus sollte nicht in der Lage sein, von der Seite oder aus der entgegengesetzten Richtung zur Treppe zu gelangen. Es wird unpraktisch und seltsam sein, wenn die Treppe in den Korridor stürzt, wie unten gezeigt.
Das heißt, am Ende sollte das Format der Treppe wie im Bild unten aussehen. Der Pfadfindungsalgorithmus sollte die Existenz von Korridoren in zwei blauen Quadraten sicherstellen.
Die Treppe beginnt mit einem durchgezogenen blauen Quadrat und geht eine Etage höher.Der Pfadsuchalgorithmus sollte sich in einem Schritt vom Start- zum Endpunkt bewegen. Dies bedeutet, dass es 3 Einheiten horizontal und 1 Einheit nach oben oder unten verschoben werden muss. Der Algorithmus A * ist so ausgelegt, dass er sich bei jedem Schritt von einem Knoten zum nächsten bewegt. Um die Treppe zu schaffen, muss ich vier Zellen der Treppe "springen".
Die Schwierigkeit besteht darin, dass ich den Algorithmus irgendwie dazu bringen muss, um die Treppe herumzugehen, die er erzeugt. Ich kann sie nicht zu der
geschlossenen Menge A * hinzufügen, weil dann ein anderer Weg aus einer anderen Richtung durch diese Zellen nicht möglich ist. Aber ich kann sie auch nicht verlassen, da der Pfadsuchalgorithmus dann in der Lage ist, sich entlang der neu erstellten Leiter zu bewegen, wodurch die oben gezeigten unerwünschten Situationen entstehen.
Die Lösung bestand darin, dass jeder Knoten alle vorherigen Knoten in seinem Pfad verfolgen sollte. Wenn dann ein benachbarter Knoten betrachtet wird, wird er abgelehnt, wenn er sich auf den Pfad des aktuellen Knotens bezieht. Der Korridor am Ende der Treppe enthält alle Zellen, die von der Treppe besetzt sind, den Knoten am Anfang der Treppe und alle Knoten auf dem Weg dorthin und so weiter bis zum Anfang. Der Pfadsuchalgorithmus erstellt möglicherweise einen anderen Pfad, der durch die Treppe führt, da der zweite Pfad nichts über die Treppe weiß.
Das oben beschriebene Verhalten wird nur für einige mögliche Pfade innerhalb desselben Pfadfunktionsaufrufs benötigt. Um alle Korridore zu generieren, bleiben noch viele Herausforderungen, um den Weg zu finden. Nachfolgende Iterationen umgehen einfach vorhandene Treppen wie zuvor.
Der Algorithmus ist zu diesem Zeitpunkt nicht mehr vollständig A *. Es gibt zu viele Sonderfälle, nur um Treppen abzurechnen. Die Notwendigkeit, den gesamten vorherigen Pfad in jeder Phase zu überprüfen, ist ein kostspieliger Prozess. Eine naive Implementierung folgte allen Knoten vor dem Start und las sie als verknüpfte Liste. Dann würde es O (N) Zeit brauchen, um den Pfad für jeden benachbarten Knoten zu überprüfen.
Ich entschied mich für diese Implementierung: Speichern einer Hash-Tabelle in jedem Knoten, deren Schlüssel die vorherigen Knoten sind. Dank dessen wird die Pfadprüfung in O (1) durchgeführt. Wenn Sie jedoch einen Knoten zum Pfad hinzufügen, muss die Hash-Tabelle kopiert werden, und dies ist O (N). Ich entschied mich für diese Methode, weil ich feststellte, dass der Algorithmus Pfade häufiger liest als ändert.
Wie auch immer, die Gesamtkomplexität wird ungefähr 0 (N ^ 2) sein, obwohl ich nicht weiß, wie ich das richtig analysieren soll. Diese Modifikation ist der Haupt- "Engpass" des Algorithmus zur Dungeon-Generierung.
Nach all diesen Änderungen war das Ergebnis wie folgt:
Grüne Rechtecke sind TreppenGeneratorpfade können einfach sein ...... oder kompliziertSo sieht ein 3D-Dungeon mit echten Grafikressourcen aus:
Dungeon mit mehreren EtagenDer Dungeon-Generierungsalgorithmus ist in der Lage, interessante neue Verhaltensweisen zu erzeugen.
Zwei Treppen bilden eine doppelt breite TreppeSchwer zu erklärende dreifach breite LeiterEin Pfad, der zwei Stockwerke hinunterführt, kann zwei Treppen mit einer Plattform in der Mitte erzeugenWenn mehrere Wege nebeneinander verlaufen, können die Korridore recht groß seinZwei Stufen führen zu einer EtageFazit
Der schwierigste Teil des Projekts war die Erstellung der für die 3D-Version erforderlichen Algorithmen. Ich konnte keine einzige Implementierung von Delaunays 3D-Triangulation finden, also musste ich es selbst tun. Die Anforderungen an den Pfadsuchalgorithmus waren sehr spezifisch, also habe ich es auch selbst gemacht.
Aber die Arbeit hat sich gelohnt. Die mit diesem Algorithmus erstellten Dungeons sind interessant und können die Grundlage für ein gutes Spiel werden.