Graph Node Dungeon Generator

In diesem Beitrag werde ich den Algorithmus zur prozeduralen Erzeugung von Ebenen eines zweidimensionalen Dungeons mit einer vorgegebenen Struktur beschreiben. Im ersten Teil wird eine allgemeine Beschreibung und im zweiten Teil die Implementierung des Algorithmus vorgestellt.

Einführung

Der Algorithmus wurde im Rahmen einer Bachelorarbeit geschrieben und basiert auf einem Artikel von Ma et al. (2014) . Ziel der Arbeit war es, den Algorithmus zu beschleunigen und durch neue Funktionen zu ergänzen. Ich bin sehr zufrieden mit dem Ergebnis, da wir den Algorithmus schnell genug gemacht haben, um ihn während der Ausführung des Spiels zu verwenden. Nachdem wir die Bachelorarbeit abgeschlossen hatten, beschlossen wir, sie in einen Artikel umzuwandeln und an die Game-ON 2018-Konferenz zu senden.

Algorithmus

Um ein Spiellevel zu erstellen, erhält der Algorithmus als Eingabe einen Satz polygonaler Bausteine ​​und ein Diagramm der Level-Konnektivität (Level-Topologie). Die Knoten des Diagramms geben die Räume an, und die Kanten bestimmen die Verbindungen zwischen ihnen. Der Zweck des Algorithmus besteht darin, jedem Knoten des Diagramms die Form und Position des Raums zuzuweisen, so dass sich keine zwei Raumformen schneiden und jedes Paar benachbarter Räume durch Türen verbunden werden kann.


(a)


(b)


(c)


(d)

Die Abbildungen (c) und (d) zeigen die Diagramme, die aus dem Eingabegraphen (a) und den Bausteinen (b) erzeugt wurden.

Mithilfe des Konnektivitätsdiagramms kann ein Spieledesigner den Spielfluss einfach steuern. Benötigen Sie einen gemeinsamen Weg zum Chefraum mit mehreren optionalen Seitenwegen? Beginnen Sie einfach mit dem Pfaddiagramm und geben Sie dann einige Knoten an, in denen der Spieler wählen kann: Gehen Sie entweder den Hauptpfad entlang oder erkunden Sie den Nebenpfad, wobei mögliche Schätze und / oder Monster darauf warten. Müssen Sie den Weg abschneiden? Wählen Sie einfach die beiden Knoten im Diagramm aus und fügen Sie eine kurze Straße hinzu, die sie verbindet. Die Möglichkeiten dieses Schemas sind endlos.




Beispiele für Eingabediagramme. Der Hauptpfad ist rot dargestellt, die Hilfspfade sind blau, der kurze Pfad ist orange.

Der Algorithmus ermöglicht es Spieldesignern nicht nur, die Struktur der generierten Karten auf hoher Ebene zu verwalten, sondern bietet auch die Möglichkeit, das Erscheinungsbild einzelner Räume zu steuern und sie miteinander zu verbinden.

Unterschiedliche Formen für unterschiedliche Räume

Ich erwähnte den Chefraum am Ende des Levels. Wir wollen nicht, dass der Chefraum wie ein anderer gewöhnlicher Raum aussieht, oder? Mit dem Algorithmus können Sie Formulare für jeden Raum festlegen. Zum Beispiel können wir einen Raum am Anfang des Levels und einen Chefraum erstellen, der ihre eigenen Sätze von Raumformen haben sollte, und einen gemeinsamen Satz für alle anderen Räume.



Zwei aus dem Eingangsgraphen erzeugte Schaltkreise, in denen der Raumnummer 8 eine spezielle Form von Räumen zugeordnet ist.

Explizit angegebene Türpositionen

Stellen Sie sich vor, Sie haben ein hochwertiges Boss-Meeting-Skript und der Spieler muss den Raum des Chefs von einem bestimmten Plättchen aus betreten. Oder wir haben eine Raumvorlage, in der einige Fliesen für Wände und andere Hindernisse reserviert sind. Mit dem Algorithmus können Designer mögliche Türpositionen für einzelne Raumformen explizit festlegen.

Aber manchmal kann das Ziel das Gegenteil sein. Wir können Raumvorlagen so erstellen, dass die Türen zu ihnen fast überall sein können. Aus diesem Grund legen wir dem Algorithmus weniger Einschränkungen auf, daher läuft er häufig schneller und die erzeugten Schaltkreise wirken möglicherweise weniger eintönig und organischer. In solchen Situationen kann einfach die Länge der Türen angegeben werden und wie weit sie von den Ecken entfernt sein sollten. Der Abstand von den Ecken ist eine Art Kompromiss zwischen der manuellen Anordnung aller Türen und dem Vorhandensein von Türen überall.


(a)


(b)

Abbildung (a) zeigt die verschiedenen Arten der Türplatzierung: Ein quadratischer Raum hat 8 klar definierte Türpositionen, und ein rechteckiger Raum verwendet Länge und Abstand von den Ecken. Abbildung (b) zeigt ein einfaches generiertes Diagramm mit den Formen der Räume in Abbildung (a).

Korridore zwischen den Zimmern

Wenn wir über Dungeonebenen sprechen, stellen wir uns oft Räume vor, die durch enge Korridore verbunden sind. Ich würde gerne annehmen, dass die Verbindungen im Eingabediagramm die Korridore anzeigen, aber sie sind es nicht. Sie garantieren einfach, dass alle benachbarten Knoten direkt durch Türen verbunden werden. Wenn wir möchten, dass die Räume durch Korridore verbunden sind, müssen wir einen neuen Knoten zwischen allen benachbarten Raumpaaren einfügen und so tun, als wären dies Korridorräume (mit bestimmten Raumformen und bestimmten Türpositionen).


(a)


(b)

Eine Illustration, wie wir das Eingabediagramm ändern können, um Korridore zwischen Räumen hinzuzufügen. Abbildung (a) zeigt das Eingabediagramm vor dem Hinzufügen der Korridorräume. Abbildung (b) zeigt das aus (a) erstellte Eingabediagramm, indem neue Räume zwischen allen benachbarten Räumen des ursprünglichen Diagramms hinzugefügt werden.

Leider erschwert dies die Aufgabe des Algorithmus erheblich, da sich die Anzahl der Knoten häufig verdoppelt. Aus diesem Grund habe ich eine Version des Algorithmus implementiert, die Korridore berücksichtigt und es ermöglicht, den Leistungsabfall beim Anordnen von Korridorräumen zu verringern. Im Moment unterstützt der Algorithmus entweder Korridore zwischen allen Räumen oder das völlige Fehlen von Korridoren, aber in Zukunft plane ich, ihn flexibler zu gestalten.

Beispiele

Mehrere Schemata, die aus verschiedenen Bausteinsätzen und mit aktivierten Korridoren generiert wurden.





Mehrere Schemata, die aus verschiedenen Bausteinsätzen mit ein- und ausgeschalteten Korridoren generiert wurden.

Im zweiten Teil des Beitrags werde ich über die interne Funktionsweise des Algorithmus sprechen.

Ich arbeite auch an einem Unity-Plugin für die prozedurale Dungeon-Generierung, das diesen Algorithmus enthalten wird. Ich mache das, weil trotz der Möglichkeit, diesen Algorithmus direkt in Unity zu verwenden (er ist in C # geschrieben), die Bequemlichkeit, damit zu arbeiten, alles andere als ideal ist. Das Erstellen von Raumvorlagen ohne GUI nimmt viel Zeit in Anspruch, und es wird viel Code benötigt, um die Ausgabe des Algorithmus in die im Spiel verwendete Darstellung zu konvertieren.

Da ich selbst kein Spieleentwickler bin, ist es mein Ziel, das Plugin so gut zu machen, dass andere es verwenden können. Wenn alles gut geht, werde ich versuchen, Updates zu veröffentlichen, wenn ich etwas Interessantes zu sagen habe. Ich habe bereits einige Ideen zum Generator selbst und zum Testen seiner Fähigkeiten.





Screenshots des Unity-Plugins (das Projekt befindet sich in der Entwicklung)

Teil 2. Implementierung des Algorithmus

In diesem Teil werde ich über die Grundideen sprechen, die in der Grundlage des im ersten Teil des Beitrags beschriebenen Algorithmus festgelegt wurden. Zunächst wollte ich die grundlegenden Konzepte sowie die wichtigsten Verbesserungen beschreiben, die erforderlich sind, damit der Algorithmus schnell genug ist. Wie sich jedoch herausstellte, sind selbst die Grundkonzepte für diesen Beitrag mehr als ausreichend. Aus diesem Grund habe ich beschlossen, Leistungsverbesserungen in einem zukünftigen Artikel aufzuzeigen.

Motivation

Bevor ich zur Implementierung übergehe, möchte ich das Ergebnis dessen zeigen, was wir tun werden. Das folgende Video zeigt 30 verschiedene Schaltkreise, die aus einem Eingangsgraphen und einem Satz von Bausteinen generiert wurden. Der Algorithmus stoppt nach dem Erzeugen der Schaltung immer für 500 ms und versucht dann, die nächste zu erzeugen.

Wie funktioniert es?

Der Zweck des Algorithmus besteht darin, jedem Knoten im Diagramm die Form und Position des Raums zuzuweisen, sodass sich keine zwei Räume schneiden und benachbarte Räume durch Türen verbunden sind.

Eine Möglichkeit, dies zu erreichen, besteht darin, alle möglichen Kombinationen von Raumformen und deren Positionen auszuprobieren. Wie Sie vielleicht erraten haben, wird dies jedoch sehr ineffizient sein, und wir werden wahrscheinlich keine Schaltungen erzeugen können, selbst wenn sehr einfache Eingabegraphen verwendet werden.

Anstatt nach allen möglichen Kombinationen zu suchen, berechnet der Algorithmus, wie alle einzelnen Räume (die sogenannten Konfigurationsräume) korrekt verbunden werden, und verwendet diese Informationen, um die Suche zu steuern. Leider ist es trotz dieser Informationen immer noch schwierig, das richtige Schema zu finden. Für eine effektive Untersuchung des Suchraums verwenden wir daher eine probabilistische Optimierungstechnik (in diesem Fall eine Tempersimulation). Zur weiteren Beschleunigung der Optimierung teilen wir die Eingabeaufgabe in kleinere und einfacher zu lösende Unteraufgaben auf. Dies erfolgt durch Aufteilen des Diagramms in kleinere Teile (als Ketten bezeichnet) mit anschließender Erstellung von Schemata für jeden von ihnen in der angegebenen Reihenfolge.

Konfigurationsbereiche

Für ein Paar von Polygonen, in denen eines an Ort und Stelle fixiert ist und das andere sich frei bewegen kann, ist der Konfigurationsraum die Menge der Positionen eines freien Polygons, an denen sich zwei Polygone nicht schneiden und durch Türen verbunden werden können. Bei der Arbeit mit Polygonen kann jeder Konfigurationsraum als möglicherweise leerer Satz von Linien dargestellt und mit einfachen geometrischen Werkzeugen berechnet werden.


(a)


(b)

Raumkonfigurationen. Abbildung (a) zeigt den Konfigurationsraum (rote Linien) eines freien Rechtecks ​​relativ zu einem festen L-förmigen Polygon. Es bestimmt alle Positionen der Mitte des Quadrats, an denen sich die beiden Blöcke nicht schneiden und berühren. Abbildung (b) zeigt den Schnittpunkt (gelbe Punkte) der Konfigurationsräume eines sich bewegenden Quadrats in Bezug auf zwei feste Rechtecke.

Der folgende Algorithmus wird verwendet, um den Konfigurationsraum eines festen und eines freien Blocks zu berechnen. Wir wählen einen Referenzpunkt auf dem beweglichen Block aus und berücksichtigen alle Positionen in $$$\ mathbb {R} ^ 2$, so dass sich beim Verschieben des Polygons so, dass sich sein Referenzpunkt an dieser Stelle befindet, sowohl der bewegliche als auch der feste Block berühren, sich jedoch nicht schneiden. Die Menge all dieser Punkte bildet den Konfigurationsraum von zwei Blöcken (Abbildung (a) oben). Um den Konfigurationsraum des sich bewegenden Blocks relativ zu zwei oder mehr festen Blöcken zu erhalten, wird der Schnittpunkt der einzelnen Konfigurationsräume berechnet (Abbildung (b) oben).

Der Algorithmus verwendet Konfigurationsräume auf zwei Arten. Anstatt die zufälligen Positionen einzelner Räume auszuprobieren, verwenden wir zunächst Konfigurationsräume, um nach Positionen zu suchen, die zu einer möglichst großen Anzahl benachbarter Räume führen, die durch die Türen verbunden sind. Dazu müssen wir den maximalen nicht leeren Schnittpunkt der Konfigurationsräume der Nachbarn erhalten. Zweitens verwenden wir Konfigurationsräume, um zu prüfen, ob alle Paare benachbarter Räume mit Türen verbunden werden können. Dies erfolgt durch Überprüfen, ob sich die Position des Raums innerhalb des Konfigurationsraums aller seiner Nachbarn befindet.

Da sich die Formen der Räume während der Ausführung des Spiels nicht ändern, können wir die Konfigurationsräume aller Paare von Raumformen vor dem Start des Algorithmus vorberechnen. Dadurch wird der gesamte Algorithmus erheblich beschleunigt.

Inkrementelles Schema

Bei der Lösung eines komplexen Problems besteht einer der möglichen Ansätze darin, es in kleinere und einfachere Teilaufgaben zu unterteilen und diese bereits zu lösen. Genau das tun wir mit der Aufgabe, einzelne Räume zu platzieren. Anstatt alle Räume gleichzeitig anzuordnen, teilen wir das Eingabediagramm in kleinere Untergraphen auf und versuchen, daraus nacheinander Diagramme zu erstellen. Die Autoren des ursprünglichen Algorithmus nennen diese Untergraphen aufgrund des Prinzips dieser Graphen, in denen jeder Knoten nicht mehr als zwei Nachbarn hat, "Ketten", und daher ist es recht einfach, ihr Schema zu erstellen.

Die endgültige Ausgangsschaltung ist immer eine verbundene Komponente, daher ist es nicht sinnvoll, die einzelnen Komponenten in die Schaltung einzubinden und dann zu versuchen, sie zu kombinieren, da der Kombinationsprozess sehr kompliziert sein kann. Daher ist nach dem Platzieren der Kette die nächste verbundene Kette immer diejenige, die mit den Scheitelpunkten verbunden ist, die bereits in der Schaltung aufgereiht sind.

Layout GenerateLayout(inputGraph) { var emptyLayout = new Layout(); var stack = new Stack<Layout>(); stack.Push(emptyLayout); while(!stack.Empty()) { var layout = stack.Pop(); var nextChain = GetNextChain(layout, inputGraph); Layout[] partialLayouts = AddChain(layout, nextChain); if (!partialLayouts.Empty()) { if (IsFullLayout(partialLayouts[0])) { return partialLayouts[0]; } else { stack.Push(partialLayouts); } } } return null; } 

Pseudocode, der einen inkrementellen Ansatz zum Finden des richtigen Schemas zeigt.

Der oben gezeigte Pseudocode demonstriert die Implementierung eines inkrementellen Schemas. Bei jeder Iteration des Algorithmus (Zeilen 6 - 18) nehmen wir zuerst die letzte Schaltung aus dem Stapel (Zeile 7) und berechnen, welche Kette als nächstes hinzugefügt werden soll (Zeile 8). Dies kann durch einfaches Speichern der Nummer der letzten Schaltung erfolgen, die zu jeder Teilschaltung hinzugefügt wurde. Im nächsten Schritt fügen wir der Schaltung (Zeile 9) die folgende Kette hinzu, erzeugen mehrere detaillierte Schaltungen und speichern sie. Wenn die Erweiterungsphase fehlschlägt, dem Stapel jedoch keine neuen Teilschemata hinzugefügt werden und der Algorithmus mit dem zuletzt gespeicherten Teilschema fortfahren muss. Wir nennen diese Situation eine Rückgabesuche, da der Algorithmus das aktuelle Teilschema nicht erweitern kann und zurückgehen und mit einem anderen gespeicherten Schema fortfahren muss. Dies ist normalerweise erforderlich, wenn nicht genügend Platz vorhanden ist, um zusätzliche Schaltungen mit den bereits in der Schaltung zusammengesetzten Scheitelpunkten zu verbinden. Eine Rückgabesuche ist auch der Grund, warum wir immer versuchen, mehrere erweiterte Schemata zu generieren (Zeile 9). Andernfalls hätten wir nichts, worauf wir zurückkommen könnten. Der Prozess endet, wenn wir eine vollständige Schaltung erzeugen oder der Stapel leer ist.


(a) Eingabediagramm


(b) Teildiagramm


(c) Teildiagramm


(d) Vollständiger Überblick


(e) Vollständige Gliederung

Inkrementelles Schema. Die Abbildungen (b) und (c) zeigen zwei Teildiagramme nach der Planung der ersten Schaltung. Fig. (D) zeigt die vollständige Schaltung nach der Erweiterung (b) um eine zweite Schaltung. Fig. (E) zeigt die vollständige Schaltung nach der Erweiterung (c) um eine zweite Schaltung.

Um das Diagramm in Teile zu unterteilen, müssen Sie eine flache Einbettung des Eingabediagramms finden, dh eine Zeichnung in der Ebene, in der sich die Kanten nur an den Endpunkten schneiden. Dieser Anhang wird dann verwendet, um alle Flächen des Diagramms abzurufen. Die Hauptidee der Zerlegung besteht darin, dass es schwieriger ist, eine Schaltung aus Zyklen zu erstellen, da ihre Knoten mehr Einschränkungen aufweisen. Daher versuchen wir, die Zyklen zu Beginn der Zerlegung so anzuordnen, dass sie so früh wie möglich verarbeitet werden und die Wahrscheinlichkeit verringert wird, dass in nachfolgenden Phasen zurückgegangen werden muss. Die erste Zerlegungskette wird durch die kleinste Fläche des Anhangs gebildet, und nachfolgende Flächen werden dann in der Reihenfolge der Breitensuche hinzugefügt. Wenn andere Flächen ausgewählt werden können, wird die kleinste verwendet. Wenn keine Flächen mehr vorhanden sind, werden die verbleibenden nichtzyklischen Komponenten hinzugefügt. Fig. 4 zeigt ein Beispiel der Zersetzung in einer Kette, die gemäß diesen Schritten erhalten wurde.


(a)

(b)

Zersetzung in Ketten. Abbildung (b) zeigt ein Beispiel für die Anordnung von Abbildung (a) auf einer Schaltung. Jede Farbe repräsentiert eine separate Kette. Zahlen geben die Reihenfolge an, in der die Ketten erstellt werden.


(c) Gutes Teildesign

(d) Vollständiger Überblick


(a) Eingabediagramm


(b) Schlechter Teilgraph

Suche mit Rückgabe. Abbildung (b) zeigt ein Beispiel für eine schlechte Teilschaltung, da nicht genügend Platz vorhanden ist, um die Knoten 0 und 9 zu verbinden. Um die vollständige Schaltung (d) zu erzeugen, ist eine Rückkehr zu einer anderen Teilschaltung (c) erforderlich.

Simuliertes Glühen

Der Tempersimulationsalgorithmus ist eine probabilistische Optimierungstechnik, deren Zweck darin besteht, den Raum möglicher Schaltungen zu untersuchen. Es wurde von den Autoren des Originalartikels ausgewählt, weil es sich in der Vergangenheit in ähnlichen Situationen als nützlich erwiesen hat. Bei der Implementierung des Algorithmus habe ich mich für dieselbe Methode entschieden, weil ich mit dem beginnen wollte, was sich bereits als wirksam bei der Lösung dieses Problems erwiesen hat. Ich denke jedoch, dass es durch eine andere Methode ersetzt werden kann und meine Bibliothek so geschrieben ist, dass das Ersetzen der Methode recht einfach ist.

Der Tempersimulationsalgorithmus wertet iterativ kleine Änderungen in der aktuellen Konfiguration oder Schaltung aus. Dies bedeutet, dass wir eine neue Konfiguration erstellen, indem wir zufällig einen Knoten auswählen und seine Position oder Form ändern. Wenn die neue Konfiguration die Energiefunktion verbessert, wird sie immer akzeptiert. Andernfalls besteht ohnehin nur eine geringe Chance, die Konfiguration zu akzeptieren. Die Wahrscheinlichkeit, schlechtere Entscheidungen zu treffen, nimmt mit der Zeit ab. Die Energiefunktion ist so ausgelegt, dass sich kreuzende Knoten und benachbarte Knoten, die sich nicht berühren, mit hohen Bußgeldern belegt werden.

$$

$$E = e ^ {\ frac {A} {\ omega}} e ^ {\ frac {D} {\ omega}} - 1$$

A ist die gesamte Schnittfläche zwischen allen Blockpaaren im Diagramm. D ist die Summe der Quadrate der Abstände zwischen den Mittelpunkten der Blockpaare im Eingabediagramm, die Nachbarn sind, sich aber nicht berühren. Wert $$$\ omega$beeinflusst die Wahrscheinlichkeit, dass simuliertes Tempern in die schlechteste Konfiguration gelangen darf; Dieser Parameter wird aus der durchschnittlichen Fläche der Bausteine ​​berechnet.

Nachdem Sie einen zu ändernden Knoten ausgewählt haben, ändern wir entweder seine Form oder Position. Wie wählen wir eine neue Position? Sie können es zufällig auswählen, aber dies verschlechtert häufig die Energiefunktion und der Algorithmus konvergiert sehr langsam. Können wir eine Position wählen, die die Energiefunktion eher erhöht? Sehen Sie, wohin ich führe? Wir verwenden Konfigurationsräume, um eine Position auszuwählen, die die Grenzen der größten Anzahl benachbarter Räume erfüllt.

Um die Form zu ändern, wählen Sie einfach eine der verfügbaren Raumformen aus. Der Algorithmus versucht zwar nicht zu entscheiden, welche Form uns am wahrscheinlichsten zum richtigen Schema führt. Es wäre jedoch interessant, diese Funktion auszuprobieren und zu prüfen, ob sie den Algorithmus beschleunigt.

 List<Layout> AddChain(chain, layout) { var currentLayout = GetInitialLayout(layout, chain); var generatedLayouts = new List<Layout>(); for (int i = 1; i <= n, i++) { if (/*       */) { break; } for (int j = 1; j <= m, j++) { var newLayout = PerturbLayout(currentLayout, chain); if (IsValid(newLayout)) { if (DifferentEnough(newLayout, generatedLayouts)) { generatedLayouts.Add(newLayout); } } if (/* newLayout ,  currentLayout */) { currentLayout = newLayout; } else if (/* ,   ,    newLayout */) { currentLayout = newLayout; } } /*      */ } return generatedLayouts; } 

Dies ist der Pseudocode des Verfahrens, das für die Erzeugung einer separaten Schaltungsschaltung durch Simulation des Temperns verantwortlich ist.

Um den gesamten Prozess zu beschleunigen, werden wir versuchen, die anfängliche Niedrigenergiekonfiguration zu finden. Zu diesem Zweck ordnen wir die Knoten in der aktuellen Kette für eine Breitensuche an, beginnend mit denen, die an die bereits im Schema enthaltenen Knoten angrenzen. Dann werden die geordneten Knoten einzeln platziert und für sie wird die Position mit der niedrigsten Energie aus dem Konfigurationsraum ausgewählt. Hier machen wir kein Backtracking - dies ist ein einfacher gieriger Prozess.

Bonus Video

Das folgende Video zeigt die Diagramme, die aus demselben Eingabediagramm wie im ersten Video erstellt wurden. Diesmal wird jedoch ein inkrementeller Ansatz gezeigt. Möglicherweise stellen Sie fest, dass der Algorithmus nacheinander Knotenketten hinzufügt. Es ist auch ersichtlich, dass es manchmal zwei aufeinanderfolgende Teilschaltungen mit der gleichen Anzahl von Knoten gibt. Dies geschieht, wenn der Algorithmus zurückkehrt. Wenn die ersten Versuche, der ersten Teilschaltung eine weitere Schaltung hinzuzufügen, fehlschlagen, versucht der Algorithmus eine andere Teilschaltung.

Herunterladbare Materialien

Die Implementierung des Algorithmus in .NET finden Sie in meinem Github . Das Repository enthält die .NET-DLL und die WinForms-GUI-Anwendung, die von YAML-Konfigurationsdateien gesteuert werden.