Zu lösendes Problem: Erstellen Sie eine zufällige 2D-Dungeon-Karte für ein Spiel auf Kachelbasis, bei dem alle Räume miteinander verbunden sind.
Ich suche nach besseren Lösungen als bisher.
Meine aktuelle Lösung ist, dass ich zwei Algorithmen ausführe. Der erste erzeugt den Kerker mit seinen Räumen. Der zweite stellt sicher, dass alle Räume miteinander verbunden sind. Ich bin gespannt, welche anderen Lösungen es gibt. Schneller und / oder einfacher usw. Geschwindigkeit ist nicht wirklich ein Problem, aber wenn Geschwindigkeit ohne wirkliche Kosten gewonnen werden kann, ist das eine gute Sache. Wichtiger ist, dass ich und andere, die lesen, verschiedene Methoden kennenlernen, um das Problem anzugehen und zu lösen.
Nachfolgend finden Sie meine aktuelle Implementierung. Zimmer haben derzeit keine Ausgänge oder Ausgänge in 2, 3 oder 4 Richtungen.
Die Dungeonräume generieren
Setup: Stellen Sie den aktuellen Raum auf den oberen linken Raum ein.
- Holen Sie sich einen gültigen Zimmertyp für den Raum (wobei der gültige Zimmertyp ein Typ ist, der keine Ausgänge aus dem Dungeon hat und Ausgänge hat, die mit den Ausgängen des Raums oben und des Raums links übereinstimmen) Links wegen Schritt 2 unten).
- Stellen Sie den Raum ab und verschieben Sie die x-Koordinate um einen Schritt. Wenn die x-Koordinate die Dungeonbreite überschreitet, setzen Sie die x-Koordinate auf 0 und verschieben Sie die y-Koordinate um einen Schritt. Wenn die y-Koordinate die Dungeonhöhe überschreitet, sind wir fertig.
- Wiederholen Sie ab # 1.
Ich überprüfe dann, ob alle Räume verbunden sind. Wenn nicht alle miteinander verbunden sind, führe ich einen zweiten Algorithmus aus, der auf eine nicht sexy, aber definitiv gute Art und Weise in Bezug auf die Dungeon-Anordnung die Räume durchläuft und sie so ändert, dass sie alle enden verbunden zu sein.
Überprüfen, ob alle Räume verbunden sind
Setup: Erstellen Sie eine 2D-Karte mit Ganzzahlen, die Pfade darstellen, und initialisieren Sie die Einträge mit dem Wert -1 (noch nicht verarbeitet). Legen Sie eine Index-Ganzzahl für den Startpfad fest, die den aktuellen Pfad auf 1 verfolgt. Legen Sie den aktuellen Raum in den oberen linken Raum fest, indem Sie ihn zu einem Stapel von zu überprüfenden Räumen hinzufügen.
- Wenn der Stapel zu überprüfende Räume enthält, setzen Sie den Pfadindex des Raums auf den aktuellen Pfadindex. Wenn der Stapel keine Räume enthält, erhöhen Sie den Pfadindex und versuchen Sie, einen Raum zu erhalten, indem Sie spaltenweise, zeilenweise vorrücken, bis wir einen Raum erhalten, der noch nicht verarbeitet wurde. Wenn kein Platz gefunden werden kann, sind wir fertig.
- Überprüfen Sie, ob der Raum links einen Ausgang hat. Wenn es den linken Raum zum Stapel hinzugefügt hat, ist er dort nicht bereits vorhanden.
- Wiederholen Sie Schritt 2 für die Richtungen nach unten, rechts und oben (da wir einen Stapel verwenden, bei dem die Räume im Uhrzeigersinn durchlaufen werden, beginnend mit der Richtung nach oben).
- Wiederholen Sie ab Schritt 1.
- Wenn die Anzahl der Pfadindizes größer als eins ist, gibt es getrennte Räume.
Wenn es getrennte Räume gibt, gruppiere ich die Räume nach ihrem Pfadindex, erhalte den Index des größten Pfades und verbinde alle anderen Räume mit diesen Räumen. Dies ist eine laufende Arbeit, aber mein (aktueller, "brutaler") Plan ist es, in jedem Raum einer Raumgruppe (mit Ausnahme der ersten) zu prüfen, ob ein horizontaler oder vertikaler Pfad zur biggeset - Raumgruppe vorhanden ist, und Wenn ja, erstellen Sie dort einen horizontalen / vertikalen Pfad, indem Sie die Räume dazwischen einfügen / aktualisieren. Spülen und wiederholen. Hässlich, ja, aber es ist etwas, das sich in Bezug auf das visuelle Muster nicht bemerkbar macht, also funktioniert es in diesem Sinne.
quelle
Antworten:
Einer der besten und am häufigsten verwendeten Algorithmen, den ich dort gesehen habe, ist das Generieren von Dungeons mit Binary Space Partitioning.
Die beste allgemeine Erklärung, die ich gelesen habe, ist die in The Chronicles of Doryen (am Ende zu Sicherungszwecken beigefügt), weil sie den Vorgang erklärt, ohne in den Code einzusteigen , und die Implementierung dem Leser überlässt.
Zwei weitere Tutorials zum selben Thema mit Code finden Sie unter
quelle
Die BSP-Methode ist anscheinend die beliebteste Methode zum Generieren von Dungeons, aber nicht die einzige.
Der Vollständigkeit halber erkläre ich den Generator, der für mich funktioniert hat . Ich muss zugeben, dass ich mich nicht mehr daran erinnere, wo ich darüber gelesen habe, also sage ich nur, dass es nicht meine Erfindung ist (ein alter Artikel von Jamis Buck kommt mir sehr bekannt vor).
Ein Labyrinth mit Räumen
Die Grundidee ist, dass ein Dungeon ein Labyrinth mit Räumen ist. Der erste Schritt für diesen Algorithmus besteht darin, ein Labyrinth zu generieren :
Der nächste Schritt ist, es sparsam zu machen (Sackgassen entfernen):
Schritt Nummer 3 besteht darin, einige Schleifen hinzuzufügen ( nicht perfekt zu machen ), aber ich werde das Bild überspringen, weil es kaum wahrnehmbar ist (ich brauchte kein perfektes Labyrinth, also habe ich ein paar Abkürzungen für den Algorithmus zur Labyrinthgenerierung gemacht, also schon hatte Schleifen zu diesem Zeitpunkt).
Dann müssen wir für Schritt 4 isolierte Zellen entfernen:
An diesem Punkt sind wir mit den Korridoren fertig und wir sind bereit, Räume hinzuzufügen. Dafür machen wir folgendes:
Bisher wird unser Dungeon so aussehen:
Der letzte Schritt ist das Hinzufügen von Dekorationen.
Einige abschließende Gedanken
quelle