Was ist prozedurale Generierung?

Die prozedurale Generierung umfasst viele generative Algorithmen, deren Prinzip darin besteht, Daten nicht manuell, sondern algorithmisch zu erstellen: Anstatt das, was wir erstellen möchten (Karten, Musik, Gelände ...), manuell herzustellen, wird ein Algorithmus geschrieben, ohne den verschiedene Beispiele erfolgreich erstellt werden können denselben Vorgang mehrmals ausführen. Dieser Ansatz ist besonders in Videospielen nützlich, bei denen eine ganze Karte oder Ebene zufällig generiert werden kann (z. B. Karten in Minecraft, Terraria oder Factorio oder Ebenenschemata in den meisten Roguelike).

Der Kollapsalgorithmus der Wellenfunktion und sein Umfang

In diesem Artikel untersuchen wir den von Maxim Gumin vorgeschlagenen Kollapsalgorithmus für Wellenfunktionen (WaveFunctionCollapse, WFC) (auf seinem Twitter gibt es eine Sammlung erstaunlicher Inhalte, die mit diesem Algorithmus von anderen Entwicklern erstellt wurden!) Bild in einem Raster einer bestimmten Größe.

Der Algorithmus basiert auf der Idee, schrittweise ein fertiges Bild zu erstellen und zu verfolgen, welche Kacheln einem bereits teilweise erstellten Bild „entsprechen“. Für eine detaillierte Beschreibung des Algorithmus empfehlen wir, dass Sie sich auf das ursprüngliche WFC-Repository auf Github und den vierten Abschnitt des Artikels " WaveFunctionCollapse ist Constraint Solving in the Wild " beziehen .


Beispiele für prozedural erzeugte Samenbilder

Ein weiteres Anwendungsgebiet des WFC-Algorithmus ist neben der Erzeugung ähnlicher Bilder die Erzeugung von Kachelkarten. Die Erstellung von Kachelkarten wird das Hauptthema des Artikels sein, da es einfacher ist, unsere Ideen klar zu erklären. Anstelle eines Beispielbilds können Sie nur Kacheln und Kachelpaare speichern, die über Runden miteinander verbunden werden können. In diesem Fall kann der Algorithmus verwendet werden, um Bilder ähnlich dem unten gezeigten zu erstellen.


Beispiele für zufällig generierte Kacheln

Die Herausforderung und unsere Lösung

Wir haben es uns zur Aufgabe gemacht, auf Basis des Brettspiels Carcassonne („Carcassonne“) eine Kachelkarte zu generieren, bei der das Feld von den Spielern „manuell“ (siehe Animation unten) aus Kacheln generiert wird, die miteinander kombiniert werden müssen.


Erstaunlicherweise ähnelt dies konzeptionell dem WFC-Algorithmus zum Erstellen beliebiger Kachelkarten, indem einer unvollständigen Lösung neue Teile hinzugefügt werden. Und da WaveFunctionCollapse als Kachelkartengenerator verwendet werden kann, können auch "Carcassonne" -Felder generiert werden!

Im Spiel selbst gibt es jedoch zu viele verschiedene Kacheln, und das Kodieren aller ihrer Verhältnisse ist eine übermäßig umfangreiche Aufgabe für einen 24-Stunden-Hackathon. Aus diesem Grund haben wir beschlossen, eine sehr vereinfachte Version von "Carcassonne" ohne Burgen und Flüsse zu spielen, nur mit Straßen, Gras und Klöstern. Wir haben also 6 mögliche Kacheln mit ihrer Rotation und Symmetrie. Aber auch unter solchen Bedingungen sieht das Ergebnis in Carcassonne gut aus und sieht aus wie ein echtes Spiel!


Visualisierung der Füllung im Carcassonne-Feldalgorithmus


Beispiel für in den Algorithmus eingeführte Regeln

Das obige Bild enthält ein Beispiel für Eingaberegeln, die dem Algorithmus hinzugefügt wurden. Wir müssen jedoch noch bestimmte Aspekte des Erscheinungsbilds des Feldes kontrollieren. Sollte der Algorithmus „Straßen“ aus Straßen erstellen, die mit Klöstern gefüllt sind und einer Stadt ähneln, oder sollte das Feld höchstens aus Gras mit umliegenden Dörfern bestehen? In dem ursprünglichen Algorithmus gibt es keine Möglichkeit, solche Bedingungen (wie jede andere) zu steuern, aber für die Möglichkeit der Steuerung ist es möglich, eine einfache Verbesserung vorzunehmen.

Bayesian a priori Wahrscheinlichkeitsverteilung

Wie oben erwähnt, fügt der Algorithmus dem Feld bei jedem Schritt eine neue Kachel hinzu, damit sie mit bereits platzierten Kacheln übereinstimmt. Wir haben jedoch nicht gesagt, was passieren würde, wenn mehrere verschiedene Kacheln an der ausgewählten Position platziert werden könnten (wir haben auch nicht darüber gesprochen, wie Im Allgemeinen wählen Sie diesen Ort, aber im Artikel werden wir es nicht berücksichtigen!). In dem ursprünglichen Algorithmus wird jede geeignete Kachel gleichmäßig zufällig ausgewählt. Bei unserer Entscheidung können wir jedoch bestimmte Fliesen bevorzugen, z. B. Gras, damit es häufiger auf dem Feld vorkommt. Dies kann erreicht werden, indem eine ungleichmäßige Verteilung der Fliesen „Wahrscheinlichkeit vor“ erzeugt wird, bei der das Gras eine größere Chance hat, als die Straße verwendet zu werden, wenn beide Arten von Fliesen verwendet werden können. Dies erinnert an Bayesianische Techniken. Im vereinfachten Fall der Wahl zwischen zwei Optionen, Gras und Straßen, können wir Gras mit einer Wahrscheinlichkeit von p> 0,5 und nicht mit der üblichen Wahrscheinlichkeit von 0,5 hinzufügen, die mit einer einheitlichen Wahrscheinlichkeit erhalten wird. Diese Aufgabe kann leicht verallgemeinert werden, indem jeder Kachel ein Prioritätswert zugewiesen und mit diesem Wert die Wahrscheinlichkeit als Wert dividiert durch die Summe der Werte aller möglichen Kacheln festgelegt wird. Die folgende Abbildung zeigt zwei geeignete Lösungen mit sehr unterschiedlichen Koeffizientenwerten, um zu verstehen, wie empfindlich der Algorithmus sein kann.


Unterschiedliche Lösungen für unterschiedliche Anfangswahrscheinlichkeitsverteilungen

Ein weiteres Beispiel: Bedingte Wahrscheinlichkeiten und Gruppierungen

Sie können diese Idee erweitern, und um dies zu veranschaulichen, werden wir anstelle von Carcassonne-Feldern zweidimensionale Karten von Minecraft-Erz erstellen. Verschiedene Erzarten in Minecraft sind normalerweise in großen Formationen zu finden. Zusammen mit der Festlegung der Wahrscheinlichkeiten für jedes Erz werden wir die Wahrscheinlichkeiten von den Nachbarn abhängig machen, die bereits auf der Karte platziert sind. Auch wenn die Anordnung von Eisen in der Nähe von Kohle nichts „Verbotenes“ ist, erhält eine andere Kohle neben bereits platzierter Kohle eine höhere Priorität.

Obwohl dies im Bild unten nicht berücksichtigt wird, hängt die Wahrscheinlichkeit im Spiel auch von der Höhe der Kacheln ab, sodass die Position im Bild auch die Verteilungsbedingungen der Kachelwahrscheinlichkeiten beeinflussen kann.


Minecraft Ore Tile Map Beispiel Erstellt von WFC

Fazit

Die Erstellung von Prozeduren ist ein leistungsstarkes Werkzeug, das es sich lohnt, auf Lager zu sein. Insbesondere wird WFC aktiv in der Weltgeneration eingesetzt, und es ist zu berücksichtigen, dass die Verteilung neuer Kacheln möglicherweise ungleichmäßig ist und von anderen Faktoren beeinflusst werden kann, z. B. von bereits auf der Karte platzierten Nachbarn, neuen Kacheln und der Position im Bild. Wir haben eine sehr einfache Anwendung erstellt, aber die Entwicklungsmöglichkeiten sind nahezu unbegrenzt!