👨🏽‍🎓 ◼️ 🧑‍🤝‍🧑 Tipps zur Verwendung des Wave Function Collapse-Algorithmus 🐮 😿 💩

In letzter Zeit habe ich viel mit prozeduraler Constraint-basierter Generierung experimentiert. Insbesondere mit dem Wave Function Collapse- Algorithmus (WFC, Wave Function Collapse ). Ich habe sogar meine eigene Open-Source-Bibliothek und mein Unity-Asset geschrieben .

WFC ist ein sehr flexibler Algorithmus, insbesondere mit den von mir entwickelten Verbesserungen. Gleichzeitig fiel es mir jedoch schwer, mit seiner Hilfe praktische Ebenen für Computerspiele zu erstellen . Die Hauptschwierigkeit besteht darin, dass der WFC keine globale Struktur hat. Alles, was er tut, ist, die Ausgabegenerierung lokal ähnlich wie die Eingabe aussehen zu lassen, indem er beispielsweise einzelne kleine Rechtecke der Ausgabe betrachtet.

In diesem Artikel werde ich Ihnen erzählen, was ich gelernt habe und was Generatoren basierend auf Einschränkungen auf ein neues Niveau bringen kann.

Die Grundlagen

Es ist schwierig, WFC zu verwenden, wenn Sie nicht wissen, wie es funktioniert. Dies ist ein auf Einschränkungen basierender prozeduraler Generierungsalgorithmus , dem in letzter Zeit viel Aufmerksamkeit geschenkt wurde. Tatsächlich hat es praktisch nichts mit dem Konzept der Quantenphysik zu tun, zu dessen Ehren es benannt wurde.

WFC ist einfach zu konfigurieren. Sie geben dem Algorithmus lediglich ein Beispiel für eine Karte. Anschließend werden neue Karten generiert, die aufgrund der wiederholten Verwendung ihrer kleinen Fragmente wie die Originalkarte aussehen .

Es gibt zwei Arten - mit einer benachbarten Anordnung oder mit einer Überlagerung von Elementen. Dies kann in 2D oder 3D und sogar auf Gittern mit Sechsecken oder Unebenheiten erfolgenGitter. Die meisten meiner Tipps gelten unabhängig davon, wie Sie den Algorithmus verwenden.

Ich schlage vor, dass Sie mit dieser Demo spielen , um sich ein Bild über den Algorithmus zu machen, und diese Einführung [ Übersetzung auf Habré] lesen, wenn Sie an technischen Details interessiert sind.

Fliesenset-Design

Der WFC-Algorithmus basiert auf Kacheln. In diesem Sinne hängt die Qualität von den Kacheln ab, die Sie zur Arbeit darauf übertragen. Ich bin kein Künstler, daher kann ich wenig beim Zeichnen schöner Kachelsätze helfen (obwohl Sie hier sehen können ), aber ein guter Kachelsatz erfordert auch technisches Wissen.

Marschwürfel

Marching Cubes ist ein Algorithmus, der auswählt, welche Kacheln festgelegt werden sollen, je nachdem, ob jeder Scheitelpunkt der Kachel voll oder leer ist. Hier ist die Liste der für 2D verwendeten Kacheln.

Wenn Sie Kacheln so erstellen, dass die schwarzen und weißen Ecken immer übereinstimmen, werden die roten Linien immer korrekt verbunden.

Hier brauchen wir kein Verständnis des gesamten Algorithmus, aber es sollte beachtet werden, dass die Idee, Kacheln nur unter Berücksichtigung ihres Verhaltens in den Ecken zu entwerfen, eine sehr leistungsfähige Technik ist. Es wird in vielen der besten Kachelsätze verwendet, da es sicherstellt, dass die Kacheln immer gut verbunden sind.

Diese Technik ist besonders leistungsfähig für WFC. Es ist passiert, denn wenn Sie ein paar Kacheln verpassen, spielt WFC keine Rolle. Er wird dieses Problem umgehen und niemals Konfigurationen erstellen, für die fehlende Kacheln erforderlich sind. Dies ist sehr praktisch für 3D, da es Dutzende potenzieller Kacheln gibt, von denen einige nur in sehr schwierigen Situationen erforderlich sind. Siehe den Abschnitt „Foundation“ weiter unten, in dem ich diesen Trick noch häufiger verwende.

Es mag auch hilfreich sein , andere Kachelmuster zu kennen , aber Marching Cubes ist das Beste.

Die Räume

Manchmal ist es am einfachsten, mit einfachen Kachelsätzen zu arbeiten. Diese Kombination von 4 Kacheln (eine Kachel ist leer) erzeugt leicht quadratische Räume.

Die Größe der Räume kann leicht geändert werden, indem das Gewicht jeder Fliese geändert wird. Nachdem Sie die Tür- und Korridorfliesen hinzugefügt haben, können Sie die Vielfalt schaffen, die für die Grundrisse der Menschen charakteristisch ist.

Stiftung

Bei der Arbeit mit WFC ist es interessant, mit Kachelsätzen zu experimentieren. Wenn Sie einfach eine Kachel legen, versucht WFC, den verbleibenden Platz optimal zu nutzen. Manchmal führt dies zu radikal unterschiedlichen Ergebnissen, wie das Bild von Maxim Gumin zeigt:

Wir können dieses Verhalten verwenden, um WFC zu stimulieren, viele erkennbare Strukturen zu erzeugen.

Hier ist ein Beispiel eines Schlosses (inspiriert von @greentecq ):

Darin habe ich folgendes Kachelset verwendet:

Diese Fliesen haben eine wichtige Eigenschaft - alle Fliesen an der Basis haben eine Breite, die nicht geringer ist als an der Oberseite. Dies bedeutet, dass es nicht möglich ist, diese Kacheln ohne Unterstützung zu erstellen. Der WFC reagiert sofort darauf und schafft Gebäude mit einem guten Fundament.

Fractal Split Approximation

Als ich das Thema der Stimulierung bestimmter Verhaltensweisen durch Auswahl des geeigneten Kachelsatzes untersuchte, stellte ich fest, dass Sie eine gute Annäherung an die rekursive Aufteilung erhalten können (ohne den „rekursiven“ Teil) , wenn der Kachelsatz aus geraden Straßen und Zweigen besteht, jedoch ohne Ecken . Dies ist ziemlich gut für Rasterebenen.

Große Fliesen

Sie können WFC hinzufügen, um Kacheln zu unterstützen, die um ein Vielfaches größer sind als normale Kacheln. Dies wird beispielsweise in meinem Tessera-Addon unterstützt .

Große Fliesen können auf verschiedene Arten verwendet werden. Da sie sich über die Grenzen des Rasters hinaus erstrecken, können Sie sie verwenden, um glattere und breitere Kurven hinzuzufügen, als dies normalerweise beim Einrasten am Raster möglich ist. Sie eignen sich auch hervorragend für Elemente aus einer großen Anzahl von Kacheln oder einfach zum Maskieren, dass die Generierung auf Kacheln basiert.

Hier ist ein Beispiel, um von Oscar Stalberg aus dem Spiel Bad North zu lernen . Oscar demonstriert, wie er große Fliesen verwendete, um sanft geschwungene Küsten, große Häuser und Klippenvariabilität hinzuzufügen.

Einschränkungen

WFC ist im Kern ein auf Einschränkungen basierender Algorithmus. Dies bedeutet, dass er versucht, Ebenen zu generieren, die einem bestimmten Satz von Kriterien entsprechen. In reinem WFC gibt es nur ein Kriterium: Die Pegel sehen lokal wie eine Beispieleingabe aus. Im Folgenden werde ich auf WFC-Verbesserungen eingehen, um neue Arten von Einschränkungen hinzuzufügen.

Feste Kacheln

Es ist sehr einfach, einzelne Kacheln zu reparieren, bevor ein Level in WFC generiert wird. Später integrieren sie sich nahtlos in die generierte Ebene.

Vor der Generation

Nach der Generierung

Diese Technik kann auf viele verschiedene Arten verwendet werden. Hier sind ein paar Ideen:

- , WFC .
,
/ WFC

Begrenzungspfade (Pfadbeschränkung) - Dies ist mein eigener Beitrag zum WFC. Dies ist eine äußerst leistungsfähige Technik, für einen vollständigen Artikel ist jedoch höchstwahrscheinlich ein separater Artikel erforderlich.

Diese Einschränkung durchsucht global alle generierten Ausgaben und gibt an, dass ein Pfad zwischen den markierten Kacheln verlaufen muss. Mit anderen Worten, es weist eine Teilmenge von Kacheln an, eine einzelne Komponente des Diagramms zu bilden . Aufgrund seiner globalen Natur ergänzt es das übliche WFC-Verhalten, bei dem nur lokale Kacheln berücksichtigt werden.

Ich fand heraus, dass das Hinzufügen dieser Einschränkung das Erscheinungsbild des generierten Levels stark beeinflusst. Ohne sie erzeugt WFC oft mehrere unterteilte Räume oder Bereiche, die unrealistisch aussehen und nicht von Menschen geschaffen wurden.

. .

Eine andere Situation, in der eine Pfadbeschränkung angebracht ist, ist ... das Zeichnen von Pfaden. Standardmäßig stellt die Pfadbeschränkung nur sicher, dass zwischen den Kacheln eine Route besteht. Es kann nicht garantiert werden, dass der Pfad so einfach wie möglich ist. Daher zeichnet er bei Flüssen und Straßen häufig an optionalen Stellen T-förmige Fugen. Der Trick besteht darin, entweder einfach alle Fliesen der T-Gelenke zu entfernen oder ihnen ein sehr geringes Gewicht zu geben, so dass sie nur ausgewählt werden, wenn dies unbedingt erforderlich ist.

Ich liebe es, feste Kacheln zu verwenden, um die Endpunkte eines Pfades zu fixieren. Aus diesem Grund ist die Pfadbeschränkung erforderlich, um Kacheln einzufügen, die den Rest des Pfads verbinden.

Die Pfade, die durch Festlegen aller vier Ecken als Endpunkte der Pfade generiert werden

Wenn Sie mit Pfaden experimentieren möchten, habe ich eine kleine Javascript-Demo, die hier dargestellt ist .

Vielfalt

Alternative Fliesen

Es ist sehr einfach, dem WFC-Algorithmus Kacheloptionen hinzuzufügen. Fügen Sie einfach die Kacheln zur Liste der möglichen Kacheln hinzu, sodass sie dieselben Verbindungen haben wie die Kacheln, die sie ersetzen. Oder es kann in der Nachbearbeitungsphase durchgeführt werden, wie dies normalerweise bei anderen Arten der prozeduralen Generierung der Fall ist.

Zwei Wandfliesen, eine davon mit Fenster. Sie sind vollständig austauschbar und verleihen dem Design einfach mehr Variabilität.

Fliesenvariabilität nach Ebene

Wenn Sie sich viel Mühe geben, um ein Fliesenset-Design zu erstellen, werden Sie feststellen, dass die Zufälligkeit von WFC ihm zu schaden beginnt. Es wird das gesamte Kachelset verwendet, dh Sie können ein Level mit gemischter Lava, Schnee und Wüste erreichen. Oft sieht das völlig unlogisch aus.

Sie können die Integrität auf einfache Weise wiederherstellen: Entscheiden Sie im Voraus, zu welchem Biom das Level gehören soll, und deaktivieren Sie dann alle Kacheln, die für dieses Biom nicht geeignet sind.

Bad North (wieder) ist ein hervorragendes Beispiel dafür. In einigen Ebenen sind Felsen völlig verboten, in anderen gibt es viel Vegetation, in den dritten Ruinen werden Friedhöfe hinzugefügt. Dies gibt jedem Level einen einzigartigen Stil, ohne dass der Generierungsstil wesentlich geändert werden muss.

Nur etwa 10% der Inseln haben Elemente von Höhlen, die in der oberen rechten Ecke sichtbar sind.

Variabilität der Kacheln innerhalb der Karte

Das Mischen von Kachelsätzen kann noch weiter gehen.

Wenn Sie WFC verwenden, um eine große Karte zu generieren, sieht sie sehr einheitlich aus. Dies ist eine weitere Folge der Tatsache, dass der Algorithmus ein Löser lokaler Einschränkungen ist.

Die beste Lösung für dieses Problem habe ich im Spiel Caves of Qud gesehen . In der Entwicklergeschichte über die Generation ( 1 , 2 ) heißt es, dass sie die Karte in verschiedene Bereiche aufteilen und dann WFC mit separaten Parametern für die Teilmengen der Karte starten. Dies bedeutet, dass sich auf der Karte möglicherweise ein Ruinenbereich und ein Stadtbereich befinden, in dem völlig unterschiedliche Vorlagen und Kacheln verwendet werden.

Beispiel aus Mathematik für Spieleentwickler: Kachelbasierte Kartengenerierung mit Wellenfunktionskollaps in 'Cuds of Qud'

Fazit

Der WFC-Algorithmus hat wie alle auf Einschränkungen basierenden Generierungstechniken das Prinzip, mit Ihren Wünschen vorsichtig umzugehen . Es ist einfach anzupassen und schöne Ergebnisse zu erzielen, aber es kann sehr schwierig sein, die spezifischen Details zu implementieren, die für Ihr Spiel benötigt werden.

Ich hoffe, dass die von mir vorgestellten Techniken Ihnen helfen werden, dieses Monster zu zähmen, aber am Ende ist es am besten, ein Spieldesign zu erstellen, das auf den Stärken der prozeduralen Generierung basiert, und nicht zu versuchen, es zu zwingen, zu viel für Sie zu erstellen.

Ich empfehle dir, Bad North und Caves of Qud zu spielen . Beide Spiele sind großartige Beispiele für die Verwendung von WFC unter realen Bedingungen, und die Entwickler haben die optimale Verwendung des Algorithmus in ihren Spielen gut durchdacht.

Tipps zur Verwendung des Wave Function Collapse-Algorithmus