Diese Woche habe ich angefangen, an einem neuen Thema zu arbeiten: der Erzeugung von Dungeons und Höhlen. Ich habe Raumpartitionierung verwendet, um Räume zu generieren, Labyrinth-Generierungsalgorithmen, um Korridore zu generieren, und zellulare Automaten, um den Höhlen ein natürlicheres Aussehen zu verleihen.

Raumaufteilung

Es gibt viele Möglichkeiten, Dungeonräume zu generieren ( zufällige Platzierung , agentenbasierte Generierung , Verwendung des Trennungslenkverhaltens oder einer physischen Engine usw.). Aber meine Lieblingsmethode ist es, den Raum zu teilen, weil er leicht zu steuern und zu erweitern ist.

Es gibt auch viele Möglichkeiten, den Raum zu teilen: Aufteilung in Gitter, binäre Aufteilung des Raums, Aufteilung des Raums durch einen Quadrantenbaum, Voronoi-Diagramme usw. Ich habe mich für eine binäre Raumaufteilung entschieden, da sie sich gut zur Erzeugung rechteckiger Räume eignet. Diese Methode hat dank eines Artikels über RogueBasin an Popularität gewonnen.

Die einzige Komplexität dieses Algorithmus ist die Wahl der Trennposition. Wenn wir die Trennposition nicht einschränken, erhalten wir seltsame Raumpartitionen:


Es gibt verschiedene Möglichkeiten, um dieses Verhalten zu vermeiden. Eine davon besteht darin, die Trennposition auf zwei Aspektverhältnisse zu beschränken, beispielsweise im Bereich von 30% bis 70% oder von 40% bis 60%. Eine andere Möglichkeit besteht darin, anstelle einer gleichmäßigen Verteilung Normal- oder Binomialwerte zu verwenden, wodurch die Wahrscheinlichkeit einer Trennung in der Mitte der Seite und nicht an den Rändern erhöht wird. Diese Methoden beheben das Problem, aber es ist schwer zu verstehen, wie genau sich die Parameter auf das Endergebnis auswirken.

Daher habe ich eine andere Methode verwendet, deren Vorteil darin besteht, dass sie einen Parameter hat und leicht zu verstehen ist: das maximal zulässige Verhältnis zwischen Länge und Breite der Zellen. Wenn ich eine neue Trennung abtaste, berechne ich zuerst die minimalen und maximalen Werte, die sie haben kann, damit das Verhältnis für zwei neue Zellen unter dem Grenzwert liegt, und führe dann eine einheitliche Abtastung zwischen diesen beiden Grenzen durch. Hier ist das Ergebnis beim Variieren des maximal zulässigen Verhältnisses:


Gute Ergebnisse werden mit einem maximalen Verhältnis von 2,0 zu 3,0 erzielt:

Raumgenerierung

Die nächste Stufe ist die Erzeugung in jeder Zelle des Raumes. Hier gibt es keine besonderen Probleme, ich habe nur Grenzen gesetzt, damit die Räume nicht zu klein und nicht zu nahe an den Zellwänden sind.

Hier sind die Ergebnisse:

Rippenauswahl

In binären Teilungs-Dungeon-Generatoren wird der im Teilungsschritt verwendete Binärbaum normalerweise wiederverwendet, um Korridore zu erzeugen. Ich habe das nicht getan, weil mir ein solcher Ansatz einschränkend erscheint.

Stattdessen baue ich beim Teilen des Raums die Struktur einer doppelt verbundenen Liste von Kanten auf , anhand derer wir erkennen können, welche Zellen sich nebeneinander befinden. Auf diese Weise erhalte ich folgende Grafiken:


Dieser Ansatz bietet drei Vorteile. Erstens: Wenn ich in Zukunft die Art der Raumteilung ändern möchte, bleibt der Rest des Generators gültig, da er am Eingang nur eine Halbkanten-Datenstruktur empfängt. Zweitens: Um nun die Kanten auszuwählen, die zu Korridoren werden sollen, kann ich einen beliebigen Algorithmus zum Erzeugen von Labyrinthen verwenden . Drittens: Wenn ich dem Dungeon Schleifen hinzufügen möchte, kann ich dies einfach implementieren.

Im Moment verwende ich nur den Kruskal-Algorithmus und den Abstand der Stadtblöcke, um Kanten auszuwählen. Hier sind die Ergebnisse:

Korridorgenerierung

Der nächste Schritt besteht darin, Korridore aus den ausgewählten Kanten zu generieren. Dies ist wahrscheinlich der schwierigste Teil des Generators, da ich vorsichtig sein muss, damit sich kein Korridor mit einem anderen schneidet.

Hier sind die Ergebnisse:

Höhlengeneration

Die vorherigen Ergebnisse waren für die Erstellung von Dungeons, Krypten und anderen künstlichen Strukturen geeignet, aber ich wollte den Höhlen und Minen ein natürlicheres Aussehen verleihen. Die klassische Art, Höhlen zu erzeugen, ist die Verwendung eines zellularen Automaten, wie in diesem RogueBasin- Artikel beschrieben . Das große Problem bei zellularen Automaten ist, dass ihre Ergebnisse nicht vollständig kontrolliert werden.

Wie auch immer, ich entschied mich dafür, zellulare Automaten zu verwenden, um ein natürliches Erscheinungsbild zu erzeugen, aber ihnen Einschränkungen aufzuerlegen, um ein kontrolliertes Ergebnis zu erzielen. Anstelle von nur zwei Zuständen: tot und lebendig verwende ich vier: absolut tot, tot, lebendig, definitiv lebendig. "Perfekt genaue" Zustände können sich dabei nicht ändern, sie werden verwendet, um die Ergebnisse einzuschränken.

Die in den vorherigen Schritten generierten Räume und Korridore sind mit „genau lebendigen“ Zellen gefüllt. Das heißt, wir haben noch unterstützende Räume und wir garantieren, dass sie miteinander verbunden werden. Die nicht ausgewählten Kanten werden mit „genau toten“ Zellen gefüllt, sodass keine neuen Pfade zwischen den Räumen angezeigt werden. Schließlich machen wir in Räumen und Korridoren zufällig einige Zellen lebendig. Hier ist die Erstkonfiguration:


Dann starten wir den zellularen Automaten:



Hier sind einige weitere Beispielergebnisse:


Später werde ich eine Füllung hinzufügen, um nicht erreichbare Teile zu entfernen.

Dies ist der erste Schritt auf einer langen Reise, um einen interessanten Dungeongenerator zu erstellen. Ich bin mit den Ergebnissen zufrieden. Ich bin besonders stolz auf die eingeschränkte Methode der zellularen Automaten, kontrollierte und natürliche Höhlen zu schaffen. Ich mag auch die Tatsache, dass jede Generationsstufe von den anderen getrennt ist und individuell modifiziert werden kann.

Isolierte Zellen löschen

Dann habe ich eine Füllung implementiert, um unzugängliche Zellen zu entfernen:

Mehrere Korridore zwischen den Räumen

Beim Experimentieren mit den Parametern des Generators stellte ich fest, dass Sie interessante Ergebnisse erzielen, wenn Sie zwischen den Verbindungsräumen ein wenig Rauschen hinzufügen.

Hier ist der Unterschied in den Ergebnissen vor dem Anlegen von Lärm an Verbindungsräume und unmittelbar danach ändert sich der Parameter nur um eine Einheit:



Wenn Sie die Räume etwas größer machen, wird das Ergebnis noch interessanter:


Es ist großartig, dass wir einen Unfall haben und schöne Strukturen entstehen, aber gleichzeitig bleiben die Struktur der Grafik und die Bezeichnungen der Räume erhalten, was nützlich sein wird:

Fliesenerzeugung für Höhlen

Ich habe die meiste Zeit damit verbracht, Fliesen zu generieren. Es ist nicht sehr schwierig, aber für die korrekte Implementierung sind ein paar Tricks erforderlich.

Hier sind Beispielergebnisse:


Das Tolle ist, dass Sie sehr einfach von einer Steinhöhle zu Sand oder Eis wechseln können:


Die nächsten Schritte bei der Erstellung des Dungeons sind das Hinzufügen von Landschaften und Monstern.