Dungeons in der Bindung von Isaac generieren

Binding of Isaac und sein Remake Binding Of Isaac: Rebirth sind einige meiner Lieblingsspiele. Sie gehören zum Roguelite Twin Stick Shooter-Genre und sind Enter the Gungeon sehr ähnlich .



Die durch diese Spiele erzeugten Dungeons sind besonders berühmt. Ich habe im Internet unzählige Tutorials zum Erstellen einer Generation im Isaac-Stil gesehen, aber ich habe mich gefragt, wie sie im Original implementiert wurde. Zu meiner Überraschung beschreiben die meisten Tutorials den Prozess falsch. In diesem Artikel werde ich darüber sprechen, wie die Generierung funktioniert, und ein Beispiel dafür in einer Javascript-Demo zeigen.



Obwohl ich mein staubiges Flash-Wissen dekompilieren und aktualisieren musste (ich habe einmal meinen eigenen Actionscript-Dekompiler geschrieben), hatte ich auch großes Glück: Entwickler IsaacFlorian Himsl und einer der Hauptentwickler von Rebirth, Simon Parser , beantworteten meine Fragen gerne. Tatsächlich hat Florian kürzlich sogar ein Video aufgenommen , das den Algorithmus beschreibt. Auf seinem Kanal können Sie auch die Details der Entwicklung seines neuen Spiels Squid Invaders erfahren.



Angesichts des Vorhandenseins seiner Geschichte kann mein Artikel als überflüssig angesehen werden. Wenn Sie jedoch blutige Details wünschen, lesen Sie weiter.

Grundlegender Algorithmus

Isaacs Entwickler waren stark von den 2D-Spielen der Zelda-Serie inspiriert und erstellten Karten, die ihren Dungeons ähnelten.





Dies ist eine Reihe von quadratischen Räumen, die durch Kanten miteinander verbunden sind. Einige Zimmer sind etwas Besonderes - auf jeder Etage gibt es immer ein Geschäft , eine Schatzkammer und einen Chef . Darüber hinaus werden mehrere andere spezielle Räume nach dem Zufallsprinzip ausgewählt. Außer dem geheimen Raum gibt es keine Schleifen im Verlies.



Das Spiel selbst besteht aus einer linearen Passage solcher Levels, normalerweise gibt es zwei davon pro "Kapitel". Während des Passierens werden die Karten etwas größer und der Inhalt der Räume ändert sich, aber der Algorithmus zum Erstellen ihrer Struktur bleibt tatsächlich jedes Mal der gleiche.



Die erste Version von Isaac wurde in weniger als 3 Monaten entwickelt, daher musste Himslu seine Zeit unglaublich effizient nutzen. Das grundlegende Design des Spiels ist schlank und einfach. Zunächst wird ein Grundriss (Ebene) erstellt. Dann werden einige Räume als besonders ausgewählt. Dann wird das Innere jedes Raumes aus dem entsprechenden Pool ausgewählt.

Gebäudeplan

Isaac wird in einem 9x8-Raster generiert. Der Einfachheit halber werden die Zellen durch Zahlen gekennzeichnet - Einsen geben die X-Position an, Zehner - die Y-Position. Dies bedeutet, dass Sie sich nach oben, unten, links und rechts bewegen können, indem Sie einfach +10, -10, +1 und -1 hinzufügen. Zellen mit einer X-Position von 0 werden nicht verwendet (immer leer), was bedeutet, dass sich der größte Teil des Codes nicht um Kartengrenzen kümmern muss. Das heißt, die obere linke Zelle der Karte ist 01 und die untere rechte Zelle ist 79.



Der Grundriss bestimmt nur, welche Zellen Räume enthalten - der Inhalt des Raums wird später ausgewählt.



Zunächst bestimmt die Formel random(2) + 5 + level * 2.6die Anzahl der Räume. Jene. Die Level beginnen bei 7 oder 8 Räumen und erhöhen sich jedes Mal um 2 oder 3 Räume.



Das Spiel stellt dann den Startraum (Zelle 35) in die Warteschlange. Dann durchläuft es die Warteschlange. Für jede Zelle in der Warteschlange werden die 4 Hauptrichtungen durchlaufen und die folgenden Schritte ausgeführt:

• Bestimmt die benachbarte Zelle durch Hinzufügen von + 10 / -10 / + 1 / -1 zur aktuellen Zelle.
• Wenn die benachbarte Zelle bereits belegt ist, führt das Spiel nichts aus.
• Wenn die Nachbarzelle selbst mehr als einen gefüllten Nachbarn hat, tut das Spiel nichts.
• Wenn auf dem Level bereits genügend Räume vorhanden sind, führt das Spiel nichts aus.
• Das Spiel macht nichts mit einer Wahrscheinlichkeit von 50%.
• Andernfalls markiert das Spiel die benachbarte Zelle als den Raum enthaltend und fügt ihn der Warteschlange hinzu.

Wenn eine Zelle keiner der benachbarten Zellen einen Raum hinzufügt, ist dies eine Sackgasse und kann zur weiteren Verwendung zur Liste der Zielräume hinzugefügt werden.



Wenn Karten mehr als 16 Räume benötigen, wird der Startraum regelmäßig erneut in die Warteschlange gestellt, um das Wachstum zu stimulieren.



Da der oben beschriebene Algorithmus mit einem einzelnen Raum beginnt und sich viele Male nach außen ausdehnt, handelt es sich im Wesentlichen um eine umfassende erste Untersuchung. Die Einschränkung, dass ein Raum nicht hinzugefügt werden darf, wenn bereits zwei Nachbarn vorhanden sind, unterteilt Räume in separate Korridore, die niemals in Schleifen zusammenkommen.



Der Grundriss wird dann auf Konsistenz geprüft. Es sollte die erforderliche Anzahl von Räumen enthalten, und der Chefraum sollte sich nicht neben dem Startraum befinden. Andernfalls beginnt die Generierung von vorne.

Besondere Räume

Boss-Räume werden platziert, indem der letzte Punkt aus der Endraumliste gelesen wird. Aufgrund der Tatsache, dass die Erzeugung als nach außen gerichtetes Wachstum durchgeführt wird, wird dies immer einer der Räume sein, die sich am weitesten vom Startraum entfernt befinden.



Dann wird die Position des geheimen Raums angezeigt. Diese Räume werden dem Grundriss hinzugefügt; Sie sind eine der wenigen Ausnahmen von der Regel, die das Platzieren von Räumen neben mehreren vorhandenen verbietet. Tatsächlich zieht der Algorithmus es im Gegenteil vor, sie so zu platzieren. Der Generator sucht zufällig nach einer leeren Zelle neben mindestens drei Räumen und nicht in der Nähe eines der Endräume. Wenn er es nach 300 Versuchen nicht findet, schwächt es das Suchkriterium leicht und nach 600 Versuchen schwächt es es noch mehr. Dieses Verfahren stellt sicher, dass der geheime Raum immer auf der Ebene platziert wird, aber normalerweise werden sie in der Nähe von Kreuzungen zusammengedrückt, was bedeutet, dass sich immer viele Räume in ihrer Nähe befinden.



Fast alle anderen speziellen Räume befinden sich in zufälligen Endräumen. Einige Zimmer sind garantiert, andere haben eine kleine Chance oder ein kleines Kriterium. Zum Beispiel erscheinen Opferräume eines von sieben Mal; Wenn der Spieler bei voller Gesundheit ist, treten sie ungefähr jedes dritte Mal auf.

Regelmäßige Zimmer

Benachbarte Räume haben immer eine Tür (oder eine zerbrechliche Wand) genau in der Mitte, und jeder Raum ist so konzipiert, dass er aus allen vier Richtungen zugänglich ist. Daher sind bei der Auswahl der Räume keine besonderen Überlegungen erforderlich - jede Kombination reicht aus.



Die Zimmer werden zufällig aus dem Pool ausgewählt. Informationen über Räume enthalten sowohl Strukturen (Gruben, Feuer, Steine ​​usw.) als auch Monster. Beide unterliegen zufälligen Variationen, wie dem Aussehen von Champion-Monstern und roten Kaminen.



Für normale Zimmer gibt es drei Pools: leicht, mittel und schwer. Die erste Stufe des Kapitels wählt aus einfachen und mittleren Räumen und die zweite aus mittleren und schwierigen. Das erste Kapitel (Keller) enthält 174 gewöhnliche Räume in Pools. "Alternative Kapitel" wie "Keller", der zufällig den Keller ersetzt, haben etwas andere Räume.

Fluch des Labyrinths

Eine der interessantesten zusätzlichen Funktionen des Codes sind die Karten mit doppelter Größe. Sie werden zufällig und nur für einige Herausforderungsmodi erstellt. Neben der offensichtlichen Verdoppelung der Anzahl der Sonderräume und zweier benachbarter Chefräume weisen sie auch viele kleine Details auf:

• 80% mehr normale Räume (max 45)
• Nur die 6 entfernten Räume werden für spezielle Räume verwendet
• Ebenen wählen Zimmer aus Pools von einfachen, mittleren und komplexen Zimmern.
• Zusätzliche normale Räume werden dem Grundriss zufällig mit einer Platzierungslogik hinzugefügt, die geheimen Räumen ähnelt.

Demo

Ich habe ein vereinfachtes Beispiel für einen Generator in Javascript erstellt, damit Sie damit experimentieren können. Den vollständigen Code finden Sie hier und ein funktionierendes Beispiel finden Sie im Originalartikel .

Wiedergeburt

Bindung von Isaac: Rebirth ist ein Remake der ursprünglichen Bindung von Isaac von Nicalis , die zu dieser Zeit für ihre VVVVV- und Cave Story- Ports berühmt war . Das Spiel wurde auf C ++ portiert und alle Sounds und Grafiken wurden überarbeitet. Im Laufe der Jahre hat das Spiel viele DLCs erhalten, die der bereits beeindruckenden Liste des Originals neue Gegenstände und Feinde hinzufügen.



Während Rebirth eine Reihe interessanter Innovationen aufweist, war der Hauptbeitrag zur Levelgenerierung die Hinzufügung größerer, unregelmäßiger Räume.





Mit einem vollständigen Satz von DLCs (zum Zeitpunkt dieses Schreibens ist dies Afterbirth +) verfügt das Spiel über 11 große Räume: 2 × 2, 2 × 1, L-förmige und schmale Korridore in verschiedenen Rotationsoptionen.





Typischer L-förmiger Raum, dreimal so groß wie ein normaler Raum. Es wurde von Simon Parser durch sorgfältige Änderung des Himsla-Quellcodes implementiert.



Anstatt alle Richtungen zu durchlaufen, umgeht der Algorithmus alle Ausgänge aus dem Raum. In einem 2x2-Raum können bis zu acht davon vorhanden sein.



Wenn es darum geht, einen Raum einzufügen, versucht er zufällig, stattdessen einen großen Raum einzufügen. Nachbarkontrollen werden weiterhin angewendet, jedoch nur für die erste Zelle neben der Tür. Der Algorithmus prüft jedoch, ob genügend Platz für den Rest des Raums vorhanden ist. Dies bedeutet, dass in großen Räumen ebene Scharniere entstehen können. Normalerweise werden zwei große Räume nebeneinander erzeugt und durch ein Paar Türen ergänzt, die sie verbinden.



Wenn nicht genügend Platz für den Raum vorhanden ist, versucht der Algorithmus, einen anderen Kandidaten einzufügen. Wenn große Räume erfolgreich eingefügt werden, besteht eine Wahrscheinlichkeit von 95%, dass sie aus dem Pool entfernt werden.



Für die großen Chefräume wird noch mehr Code benötigt. Denken Sie daran, dass sich die Chefräume immer so weit wie möglich vom Startraum entfernt befinden. Wenn ein größerer Raum gewünscht wird, ersetzt der Generator den vorgesehenen Einzelraum. Da Boss-Räume beim Ersetzen immer Sackgassen sind, prüft der Algorithmus, ob sie an einige zusätzliche Räume angrenzen. Manchmal ist ein Austausch immer noch nicht möglich, daher werden alle Endpunkte in maximaler Entfernung vom Startraum überprüft. Wenn sie nicht passen, gibt der Algorithmus auf.



Bei geheimen Räumen werden benachbarte Räume auf dem Grundriss für die Platzierung berücksichtigt, und Räume werden nur ausgewählt, wenn der Algorithmus feststellt, dass keine Türen benötigt werden.





In Isaac sind Abgründe normalerweise nicht zu überwinden

Ausgabe

Der Isaac Level Generator ist nicht der raffinierteste, den ich je gesehen habe, aber trotz der geringen Menge an Code funktioniert er unglaublich gut. Dies ist wahrscheinlich der Grund, warum sie versuchen, es so oft neu zu erstellen. Seine Einfachheit ermöglicht Änderungen und Erweiterungen, wie wir am Beispiel der Wiedergeburt sehen können. Ein unglaubliches Ergebnis.



Sie können auch feststellen, dass dieses Spiel den Trend fortsetzt, Grundrisse getrennt von Raumdetails zu erstellen. In meinen Artikeln über Diablo 1 [ Übersetzung in Habré] und Enter the Gungeon [ Übersetzung in Habré] habe ich gesagt, warum dieser Ansatz sehr mächtig sein kann.



Beim Dekompilieren des Codes habe ich keine besonders interessanten Details gefunden. Das Interessanteste, was ich sagen kann, ist, dass der Ort der Schatzkammer in einer Variablen namens "boner" gespeichert ist - wahrscheinlich die Abkürzung für Bonus Room. Der Code enthält auch Feinheiten in Bezug auf geringfügige Nebenwirkungen verschiedener Elemente, aber ich überlasse dieses Thema den Analysatoren .



Als nächstes können Sie Himslas Videoserie über die Interna des Spiels ansehen oder sogar Isaac spielen und alle Level live sehen. Ich habe gehört, dass der neue Repentance DLC dieses Jahr herauskommt. Ich empfehle auch, andere Spiele von Chefdesigner Edmund McMillen (insbesondere Super Meat Boy) zu spielen.