Die Arbeit an Programmierung, Grafik und Sound in einigen neuen Spielen ist beendet - es bleiben nur Levels übrig. Einfache und angenehme Arbeit, aber aus irgendeinem Grund mit großen Schwierigkeiten verbunden. Vielleicht die Wirkung von allgemeiner Müdigkeit.
Als er überlegte, wie er sein Leben vereinfachen könnte, kam ihm die Idee der prozeduralen Generierung in den Sinn. Natürlich muss es auch geschrieben werden, aber wie in einem bekannten Werk gesagt wurde: "Es ist besser, einen Tag zu verlieren und dann in fünf Minuten zu fliegen."
Achtung! Unter dem Schnitt viel Text und "fette" Gifs.
Einführung
Die Ebenen werden weiterhin manuell poliert, sodass keine besonderen Anforderungen an Speicher, Geschwindigkeit oder sogar die Qualität der resultierenden Ebenen bestehen.
Anfangs hatte ich geplant, dass der Generator nur Räume und Türen wirft und alle weiteren Verfeinerungen (Handlung, Szenerie und Feinde) im manuellen Modus durchgeführt werden. Aber im Moment kann der Generator noch viel mehr. Trotzdem bleibt die manuelle Abstimmung bestehen - es ist notwendig, dass die Spieler das Gefühl haben, dass zumindest ein wenig Liebe in die Levels investiert wird.
Ich habe mir meine Wissensbasis über Spieleentwickler angesehen und in einem separaten Dokument Links zu Artikeln über die prozedurale Generierung geschrieben. Bei den meisten geht es natürlich darum, klassische Labyrinthe oder Gelände zu erzeugen (die Ergebnisse sind übrigens sehr beeindruckend), was für einen 3D-Shooter nicht geeignet ist. Aber einige waren nah an dem, was ich brauchte (mit einem Sternchen notierte ich diejenigen, die mir am besten geeignet erschienen):
Ich habe beschlossen, mit den letzten beiden zu beginnen - sie werden gerade implementiert und liefern gute Ergebnisse.
Generatorstruktur
Tatsächlich bin ich nicht sofort zu dieser Struktur gekommen, sondern habe gerade zahlreiche Umgestaltungen und Umschreibungen vorgenommen, aber ich schreibe sofort darüber, damit klar ist, was los ist:
- Generierung der Anfangsgeometrie (zur Auswahl - entweder "BSP" oder Raumaufteilung).
- Löschen von Müllabschnitten (solche Abschnitte, die im Spiel nicht existieren können).
- Verbindungen aufbauen.
- Löschen von Müll-Untergraphen (solche Gruppen von Abschnitten, die miteinander verbunden sind, aber keine Verbindung zu den verbleibenden Abschnitten bestehen).
- Löschen unnötiger Verbindungen (beim Erstellen eines Spanning Tree wird eine Verknüpfung zum Minimum Spanning Tree hergestellt, da dort ein Bild vorhanden ist, für den Generator jedoch kein Minimum erforderlich ist).
- Die Randomisierung von Verbindungen ist die Wiederherstellung einiger entfernter Verbindungen zurück (für eine „menschlichere“ Art von Ebene) sowie die Umwandlung einiger anderer in Passagen zwischen Abschnitten (wodurch mehrere Abschnitte zu einer komplexeren Form zusammengeführt werden).
- Geheime Raumgeneration.
- Generierung eines „Szenarios“ (wo befinden sich der Anfangs- und der Endabschnitt und welcher Pfad muss übergeben werden, um vom Anfang zum Finale zu gelangen).
- Verbindungsoptimierung.
- Türen und Fenster erstellen.
- Die Auswahl der in diesem Abschnitt auszuführenden Aktion (Drücken Sie den Schalter, heben Sie den Schlüssel oder suchen Sie die geheime Wand).
Es gibt noch ungefähr 12 Punkte, aber sie sind noch nicht abgeschlossen (wenn ich fertig bin, werde ich einen separaten Beitrag darüber schreiben).
Anfängliche Geometrieerzeugung: "BSP"
Diese Übersetzung wurde als Grundlage genommen. Ich bin mir nicht sicher, wie viel in diesem Algorithmus in der Nähe des tatsächlichen BSP passiert, daher schreibe ich "BSP" in Anführungszeichen.
Der Algorithmus ist recht einfach. Erstellen Sie zunächst ein Rechteck mit der Größe des gesamten Spielfelds:
Dann teilen wir es zufällig in zwei Teile - entweder horizontal oder vertikal. Wo die Trennlinie stattfinden wird, wählen wir auch zufällig aus:
Wir machen das gleiche rekursiv für die neuen Rechtecke:
Und bis zu einem gewissen Grad immer wieder:
Dann wählen wir in jedem Rechteck einen „Raum“ aus - ein Rechteck mit der gleichen Größe wie das Original oder kleiner (aber nicht weniger als 3x3 - mehr dazu weiter unten).
Dann sind die Räume durch Korridore verbunden. Aber nicht jeder, aber ein wenig knifflig, weil sie in einer "BSP" -ähnlichen Struktur gespeichert sind (siehe den ursprünglichen Algorithmus für weitere Details).
Der Korridor verbindet die lila und weißen Bereiche.
In dem ursprünglichen Algorithmus haben sowohl Räume als auch Korridore die gleiche Farbe (d. H. Sie sind äquivalent), so dass dort die Korridore einfach über die Räume gezeichnet werden. In meinem Fall sollten die ursprünglichen Räume erhalten bleiben, damit die Korridore wie "hinter" den Räumen gezeichnet werden.
Wenn der Raum (in der Abbildung türkis) den Korridor überquert, sollte er ihn in zwei verschiedene Abschnitte unterteilen (daher kann derselbe Korridor in verschiedenen Farben gezeichnet werden):
Und hier ist das Ergebnis:
Dann beginnt die Phase des Markierens von Müllzellen:
Wie ich bereits geschrieben habe, kann kein Sektor kleiner als 3x3-Zellen sein. Dies liegt an der Tatsache, dass der Sektor von Wänden umgeben sein muss (mindestens 1 Zelle auf jeder Seite) und mindestens eine Zelle mit freiem Raum haben muss:
Daher sind alle Zellen gekennzeichnet, die dieser Regel nicht entsprechen. Aber nimm es einfach und du kannst sie nicht entfernen - so viele Verbindungen verschwinden und das Level ist sehr spärlich.
Stattdessen wird für jede markierte Zelle nach dem Sektor gesucht, dem sie beitreten kann (unter Beachtung der 3x3-Regel):
Wenn die Zelle immer noch keinem Sektor zugeordnet werden kann, wird sie gelöscht (aber in diesem Fall nicht - hier ist alles in Ordnung).
In der letzten Phase wird dieses schöne Bild vektorisiert und die gezeichneten Sektoren werden zu Polyboxen - solchen Polygonen, bei denen jede Kante entweder streng vertikal oder streng horizontal ist (es gibt wahrscheinlich einen wissenschaftlicheren Namen):
Erste Geometrieerzeugung: Raumaufteilung
Ein weiterer Artikel wurde als Grundlage genommen. Dieser Algorithmus ist etwas komplizierter als der vorherige, aber auch keine Raketenwissenschaft.
Zuerst wird das Spielfeld mit einem bestimmten Stoppwert gefüllt, und dann wird zufällig ein rechteckiger Bereich darauf gelöscht:
Die Stufe des Reinigens eines zufälligen Rechtecks wird einige Male (auch zufällig) ausgeführt, und als Ergebnis werden die Außenkonturen des Niveaus erhalten:
Im freien Raum werden die Raumwachstumspunkte zufällig verteilt (die Mindestraumgröße beträgt 3x3):
Die erste Phase des Raumwachstums beginnt - für jeden Raum wird die größte Seite ausgewählt, die noch wachsen kann, und sie wächst um 1 Zelle (wenn es mehrere Seiten mit derselben Länge gibt - eine zufällige). Die Räume werden der Reihe nach so verschoben, dass es keine Kreuzungen gibt.
Dann werden die Räume in Polyboxen umgewandelt:
Und die zweite Wachstumsphase beginnt - in dieser Phase kann die Seite in mehrere Teile unterteilt werden. Im Gegensatz zur ersten Stufe wächst nicht eine Zelle nach der anderen, sondern sofort bis zum maximalen Stopp - dies vermeidet die "Leiter" an den Fugen der Räume. Wenn nach dem Durchgang durch alle Räume noch leere Zellen vorhanden sind, wird der Zyklus wiederholt.
Das Ergebnis ist ein vollständig gefüllter Raum:
Dann werden Polyboxen in Form eines Rasters gezeichnet, und (wie im Fall des "BSP" -Generators) beginnt die Phase des Markierens von "Müll" -Zellen:
Und sie mit bestehenden Sektoren verbinden:
Hier konnten nicht alle Zellen angebracht werden - die zusätzlichen wurden entfernt.
Das Ergebnis wird wieder in Polyboxen konvertiert:
Reinigung von Müllabschnitten
Manchmal entstehen Abschnitte, in denen die 3x3-Regel nicht eingehalten wird:
Sie können versuchen, solche Abschnitte "wiederherzustellen", aber ich bin den einfacheren Weg gegangen und habe sie einfach gelöscht:
Verbindungen aufbauen
Für jeden Abschnitt werden seine Nachbarn durchsucht, und an den Kontaktstellen dieser Abschnitte werden Verbindungen hergestellt. Auf beiden Seiten werden Verbindungen hergestellt. Wenn Abschnitt A mit Abschnitt B in Kontakt steht, besteht eine Verbindung von A nach B und von B nach A. Das Ergebnis ist ein bidirektionaler Graph.
Löschen von Müll-Untergraphen
Manchmal erhalten wir als Ergebnis der Reinigung von Müllabschnitten nicht ein Diagramm, sondern mehrere unabhängige, wie in diesem Beispiel:
In diesem Fall wird der Untergraph als Hauptgraph ausgewählt, dessen "Fläche" der Abschnitte maximal ist, und der Rest wird gelöscht (die "Fläche" steht in Anführungszeichen, da ich zwar die reale Fläche der Polybox berechnen kann, die Aufgabe jedoch vereinfacht habe und die Fläche des Begrenzungsrahmens betrachte - das ist falsch, aber für einen Generator geeignet).
Überschüssige Verbindungen entfernen
Wenn es einen Durchgang von jedem Sektor zu jedem gibt, mit dem er verbunden ist, gibt es zu viele Türen auf der Ebene, und es ist stärker zu spüren, dass er erzeugt wird. Daher werden in diesem Stadium überschüssige Verbindungen entfernt:
Für mehr Randomisierung generiere ich keinen Spanning Tree in der minimalen Anzahl von Durchgängen, sondern lösche jeweils eine zufällige Kante (wähle sie zufällig aus allen im aktuellen Schritt möglichen aus).
Obwohl, als ich dies schrieb, die Idee schien, dass es ziemlich zufällig wäre, den anfänglichen Sektor auszuwählen und die Kanten zu entfernen, die bereits effizienter sind.
Verbindungs-Randomisierung
Im Folgenden werden Illustrationen von einer anderen Generation stammen, weil im vorherigen gab es einen Fehler im Generator, aufgrund dessen weitere Bilder falsch waren.
Aber eine Ebene, in der es keine einzige überflüssige Verbindung gibt, sieht auch nicht sehr menschlich aus, so dass ein gewisses Chaos entsteht:
- Einige gelöschte Kanten werden wiederhergestellt.
- Und manche verwandeln sich in Gänge.
Ferner verschmelzen die Abschnitte, zwischen denen die Passagen gebildet wurden, zu einem:
Wenn es Ihnen so vorkam, als ob in dieser Abbildung die im vorherigen Schritt gelöschten Verbindungen wieder auftauchten - es schien Ihnen :). Als ich den Text las, kam es mir auch so vor, aber nachdem ich mir die vorherige Abbildung genau angesehen habe, wird klar, dass alles in Ordnung ist.
Geheime Raumgenerierung
Sektoren mit nur einer Verbindung werden in der Grafik ausgewählt:
Wenn es mehrere solcher Sektoren gibt, werden sie alle in einem Array zusammengefasst und nach "Bereich" sortiert. Dann wird dieses Array zufällig abgeschnitten (so dass mindestens ein Element darin verbleibt). Diese Sektoren werden zu geheimen Räumen:
Skriptgenerierung
Zunächst werden die Sektoren mit der minimalen Anzahl freier Verbindungen (dh diejenigen, die näher an der "Kante" des Diagramms liegen) ausgewählt:
In dieser Abbildung wird ein Sektor ausgewählt, aber wenn es mehr gäbe, würde ohnehin einer ausgewählt (zufällig).
NB. Während des Korrekturlesens des Artikels konnte ich eine Situation feststellen, in der ein Sektor mit einer minimalen Anzahl freier Verbindungen nicht nur nicht am Rande steht, sondern auch das Zuweisen eines Skripts zu einem unpassierbaren Level führt. Tatsächlich können Sie jeden Sektor auswählen, aber nur einen. Danach würde das Diagramm nicht mehr in mehrere Untergraphen unterteilt.
Wählen Sie als Nächstes Sektoren aus, die mit dem aktuellen Sektor verbunden sind und nur eine freie Verbindung haben. Sie werden mit einiger Wahrscheinlichkeit verwendet, um das Skript fortzusetzen. Wenn das Diagramm beispielsweise das gleiche wie in der folgenden Abbildung wäre, könnte der durch die Frage angegebene Sektor in die Liste aufgenommen werden.
Der geheime Raum ist grau markiert, die Kreuze sind die Verbindungen, die im Originaldiagramm entfernt werden sollten, und der Quellsektor ist ein Plus.
NB. Während des Korrekturlesens des Artikels schien es mir, dass die Bedingung für das Vorhandensein nur einer Verbindung zu streng war, genau wie im vorherigen Schritt - damit das Diagramm nach dem Löschen dieses Sektors nicht aufbricht.
Dann wird die Skriptnummer dieser Liste von Sektoren zugewiesen (nur eine Nummer, in diesem Stadium bedeutet dies nichts Bestimmtes), und die Verbindungen an den Rändern dieser Liste von Sektoren werden von diesem Skript als geschlossen markiert.
In diesen Abbildungen haben verschiedene Szenarien unterschiedliche Sektorfüllfarben. Sie haben nichts mit der Farbe des Sektors zu tun (in den nächsten Schritten wird es korrigiert, aber in diesem Schritt ist es für mich bequemer).
Als nächstes wird der nächste Sektor ausgewählt, eine Liste erstellt und diese Liste mit einem neuen Szenario markiert:
Achten Sie auf die kleinen blauen Punkte in den roten Quadraten - so wird der Szenarioöffner gezeichnet - d. H. Irgendwo innerhalb des Abschnitts mit der roten Schrift befindet sich ein Schlüssel oder Schalter, der den Durchgang zu Sektoren mit einer blauen Schrift öffnet.
Dies geht so lange weiter, bis keine freien Sektoren mehr vorhanden sind:
Dem neuesten Sektor wird kein Skript zugewiesen, sondern nur ein Szenarioeröffner. Dieser Sektor ist der Sektor, in dem der Spieler das Spiel startet.
Für dieses Level:
- Der Spieler startet im Startbereich, irgendwo findet er einen „Flaschenöffner“ zum gelben Bereich, geht dorthin.
- Im gelben Sektor öffnet sich der blaue Sektor, geht dorthin.
- Im blauen Sektor öffnet sich grün, geht dorthin.
- Im grünen Bereich öffnet sich lila, geht dorthin.
- In lila öffnet sich rot.
- In rot - blau.
- Wo er den Endpegelschalter findet.
Schematisch kann dies wie folgt gezeigt werden:
Ein „Öffner“ kann entweder ein Schlüssel oder ein Schalter sein oder etwas anderes, zum Beispiel eine Aufgabe, alle Feinde in einem Sektor zu zerstören (aber ich plane nicht, dass der Generator oder Motor dies in naher Zukunft unterstützen wird).
Verbindungsoptimierung
In diesem Schritt wird für jede Verbindung eine Seite ausgewählt (wie Sie sich erinnern, werden die Verbindungen zunächst in beide Richtungen generiert). Dies ist notwendig, um das Level „manueller“ aussehen zu lassen und die nächsten Schritte zu vereinfachen (aber für einen noch interessanteren Level-Typ plane ich in naher Zukunft den Schritt, einige Verbindungen zu „deoptimieren“) .
Türen und Fenster erstellen
Für jeden Sektor werden alle seine Verbindungen angezeigt (die nach dem vorherigen Schritt nur in eine Richtung schauen), und Türen und Fenster werden auf jeder angezeigten Verbindung platziert.
- Zunächst wird ein Punkt an der Verbindungsstelle ausgewählt, vorzugsweise näher an der Mitte.
- Dann wird an dieser Stelle entweder eine Tür oder ein Fenster platziert (und wenn es sich um eine Verbindung zu einem geheimen Raum handelt, dann zu einer geheimen Wand).
- Wenn eine Tür platziert wird, kann sie 1 bis 3 Zellen groß sein (eine ist eine normale Tür, zwei oder drei sind eine dicke hermetische Tür, die sich nach Drücken eines Schalters öffnet).
- Ferner ist die Verbindung in zwei Teile unterteilt - den Teil vor dem ausgewählten Punkt und den Teil danach. Und wenn vorher oder nachher noch Platz vorhanden ist, wird die Funktion rekursiv aufgerufen.
Um das Level interessanter aussehen zu lassen, besteht bei verschiedenen Schritten eine unterschiedliche Wahrscheinlichkeit, eine Tür oder ein Fenster zu platzieren:
- Im ersten Schritt wird die Tür immer platziert, weil Was nützt das Verbinden, wenn dort nur Fenster vorhanden sind?
- Im zweiten Schritt wird mit einer höheren Wahrscheinlichkeit (75%) ein Fenster als eine Tür platziert.
- Wenn es einen dritten Schritt gibt (zum Beispiel ist die Verbindung lang), muss ein Fenster darauf platziert werden.
- Im Fall des 4. Schritts wird die Tür oder das Fenster gleich wahrscheinlich platziert.
- Wenn die Verbindung besonders lang ist, kehrt der Generator zum zweiten Schritt zurück.
Aktionsauswahl
Obwohl dies nicht mit der Generierung zusammenhängt, ändert sich die Visualisierung in diesem Schritt - jetzt wird der Sektorrand in der Farbe des Skripts gezeichnet:
Der Startsektor ist hellgrau, der Endsektor ist blau. Beachten Sie auch, dass anstelle der Tür im Geheimraum (dunkelgrau links) eine Wand gezeichnet wird - alles ist korrekt, dies ist eine Geheimwand.
Wählen Sie als Nächstes die Sektoren aus, in denen Sie die Schlüssel platzieren können:
Sie werden ganz einfach ausgewählt:
- Wenn dies ein geheimer Raum ist, darf sich kein "Öffner" darin befinden, und der Schlüssel kann dort nicht platziert werden.
- Sie können den Schlüssel auch nicht im endgültigen Sektor platzieren, da er endgültig ist.
- Der Schlüssel kann auch keine Doppel- und Dreifachtüren öffnen - aufgrund der Merkmale des Motors können sie nur mit dem Schalter geöffnet werden (in der obigen Abbildung sind solche Sektoren nicht vorhanden) .
Danach wird die Anzahl der Schlüssel auf einer Ebene (von null bis drei) zufällig ausgewählt, und dann werden zufällig aus der verfügbaren Liste von Sektoren diejenigen ausgewählt, in denen Schlüssel vorhanden sein werden.
In den übrigen Sektoren wird es Schalter geben.