Einschränkungsbasierter Kachelplatzierungsalgorithmus

In diesem Beitrag wird der in Generate Worlds verwendete Algorithmus beschrieben. Mit diesem Tool können Benutzer prozedurale Welten erstellen und erkunden, indem sie kleine Mengen von Voxel-Kacheln erstellen. Ich werde den Algorithmus kurz beschreiben und in den folgenden Beiträgen auf seine Vorteile in Bezug auf Geschwindigkeit und Flexibilität im Vergleich zu anderen Methoden eingehen. Um mehr darüber zu erfahren, was Constraint-basierte Prozedurgenerierung ist und worin sie interessant ist, empfehle ich, meinen vorherigen Beitrag zu lesen.

Wenn Sie Ihre Stärken bei der Erstellung von prozeduralen Welten mit diesem System testen möchten, können Sie Generate Worlds erwerben . Wenn der Preis für Sie zu hoch ist, lesen Sie weiter: In diesem Beitrag erfahren Sie, wie Sie den Generate Worlds-Algorithmus unabhängig implementieren können.

Fliesen-Sets

In Generate Worlds wird jede Welt aus einer Reihe von Kacheln (Kachelsatz) zusammengesetzt. Im Wesentlichen sind Fliesen nur kleine Voxelmodelle. Beginnen wir mit einem Beispiel. Das Bild unten besteht aus 9 Kacheln. Wie Sie sehen, besteht jede Kachel aus Voxeln, die als farbige Würfel angezeigt werden.


Wenn Sie diese Voxelmodelle logisch anordnen, können Sie eine schöne pastorale Szene wie in der folgenden Animation erstellen. Mit "Logik" meine ich, dass Fliesen zusammenpassen, wenn ihre Farben am Rand der Fuge übereinstimmen.


Die Aufgabe des Generate Worlds-Algorithmus besteht darin, eine solche Assembly schnell und automatisch zu vervollständigen. Sehen wir uns die Erklärung des Problems an, bevor wir mit dem Algorithmus beginnen.

Wir verbinden Fliesen untereinander

Schauen Sie sich das Kachelset mit 4 Kacheln an:


Diese Kacheln ähneln den oben gezeigten dreidimensionalen Kacheln.

Der Algorithmus zum Generieren von Welten erstellt gültige Kachelkombinationen nach einer einfachen Regel: Wenn sich zwei Kacheln berühren, müssen alle Farben am Rand der Berührung übereinstimmen . Diese Regel formalisiert den Ansatz eines lebenden Designers, eine 3D-Welt aus Voxelfliesen zu erstellen.

In einer zulässigen Kombination der oben dargestellten 4 Kacheln sollten helle Zellen entlang der Ränder nur helle Zellen berühren, und eine dunkle Zelle sollte nur dunkle Zellen berühren. Zum Beispiel:


Beispiele für richtige und falsche Verbindungen.

Das Beispiel auf der rechten Seite ist nicht akzeptabel, da das helle Quadrat entlang der Kante der Kachel das dunkle Quadrat berührt. Zwei gültige Kombinationen, die für dieses Kachelset generiert wurden, sind nachfolgend aufgeführt:


Im Allgemeinen ist das Erstellen gültiger Kachelkombinationen keine triviale Aufgabe. Betrachten Sie beispielsweise die folgende einfache „gierige“ Strategie: Wir beginnen mit einem leeren Raster. In jeder Iteration platzieren wir die Kachel an einem bestimmten Punkt und wählen eine akzeptable Kachel aus, wobei bereits platzierte Kacheln berücksichtigt werden. Das folgende Diagramm zeigt die Probleme einer solchen Strategie.


Wenn wir Kacheln platzieren, ohne vorherzusehen, wie sich die Platzierung auf zukünftige Entscheidungen auswirkt, kommt der „gierige“ Algorithmus schnell zum Stillstand. Im obigen Diagramm kann kein gültiges Plättchen in das rote Quadrat gelegt werden. Und das ist das Hauptproblem: Bisher veröffentlichte Kacheln können die Anzahl der aktuellen Optionen auf Null reduzieren. Wir brauchen einen Schutz vor dem Verlegen von Fliesen, der uns in eine Sackgasse führen kann. Der in Generate Worlds implementierte Algorithmus berücksichtigt zunächst, dass alle Kacheln an allen Rasterpunkten platziert werden können. Wenn wir eine Kachel in das Raster legen, ist es offensichtlich, dass einige der zukünftigen Optionen nicht mehr zugänglich sind. Nachdem der Algorithmus diese Optionen entfernt hat, können wir die verbleibenden Optionen erneut untersuchen und andere Kacheln entfernen, die jetzt nicht mehr mit der geringeren Anzahl möglicher Kacheln an benachbarten Punkten kompatibel sind.

Betrachten Sie das folgende Beispiel. Der Algorithmus beginnt mit einem 3x3-Raster, in dessen Mitte sich eine einzelne Kachel befindet. Die Position dieser Kachel impliziert, dass 9 mögliche Kacheln an benachbarten Gitterpunkten nicht zulässig sind. Er wirft sie ab und berücksichtigt sie nicht mehr. Nach dem Löschen dieser Kacheln kann er Kacheln löschen, die nicht mit allen Kacheln kompatibel sind, die als Kandidaten für die Platzierung an benachbarten Rasterpunkten gelten. Die roten Quadrate im Diagramm markieren die Punkte, an denen die Kacheln gelöscht werden, da sie nicht mit allen Nachbarn kompatibel sind, die noch berücksichtigt werden. Wenn der Algorithmus diesen Vorgang so lange fortsetzt, bis Kacheln gelöscht werden können, kehrt er in den Zustand zurück, der in der unteren linken Ecke der Schaltung angezeigt wird. Wie Sie sehen, wurden viele Kacheln von der Betrachtung ausgeschlossen. Wenn die Strategie des Platzierens von Kacheln nur darin bestand, Kacheln aus diesen verbleibenden Gruppen auszuwählen, wäre die Wahrscheinlichkeit, in eine Sackgasse zu geraten, viel geringer als bei dem oben beschriebenen "gierigen" Ansatz.


Das Problem bei diesem Ansatz ist, dass jedes Mal, wenn eine Kachel platziert wird, ein teurer iterativer Prozess erforderlich ist. Beachten Sie jedoch, dass jedes Mal, wenn ich eine Kachel mit einem umgekehrten T platziere, diese 19 Kacheln, die ich im obigen Beispiel entfernt habe, aus der Berücksichtigung um diese Platzierung entfernt werden können. Ich bezeichne die Sammlung von Kacheln, die gültige Optionen rund um die gehostete Kachel bleiben, als gültige Nachbarschaft dieser Kachel.

Schnelle Platzierung der Kacheln dank Informations-Caching

Das wichtigste Prinzip des Generate Worlds-Algorithmus besteht darin, dass die Informationen, die über mögliche Kachelnachbarn gesammelt wurden, bei jeder Platzierung dieser Kachel wiederverwendet werden können. Im Fall eines umgekehrten T für die acht umgebenden Quadrate des Gitters können wir beispielsweise 19 Kacheln unmittelbar nach dem Platzieren dieser Kachel aus der Betrachtung entfernen, indem wir uns die zwischengespeicherte Version der zulässigen Nachbarschaft für diese Kachel ansehen.

Beispiel: Im folgenden Beispiel füllt der Algorithmus das 5 x 5-Raster mit Kacheln, wobei eine zwischengespeicherte zulässige Nachbarschaft von 4 Kacheln verwendet wird. Nachdem er das erste Plättchen platziert hat, entfernt er 19 Plättchen, die im obigen Beispiel nicht möglich waren. Nach dem Platzieren jeder Kachel werden alle Optionen, die in der akzeptablen Umgebung der platzierten Kachel fehlen, aus der Betrachtung entfernt.


Wenn Sie auf diese Weise fortfahren, können Sie das gesamte Raster mit nur schnellen lokalen Aktualisierungen des Kachelsatzes füllen, die für jeden der Punkte noch gültige Optionen sind.

Zulässige Nachbarschaften können beliebig groß sein, sodass Sie entfernte inkompatible Kacheln bei jedem Platzieren von Kacheln aus der Überlegung entfernen können. Obwohl die Erzeugung einer akzeptablen Nachbarschaft ziemlich langsam ist, muss sie nur einmal durchgeführt werden. Nach dieser Zeit hängt jede linear von der Größe der Nachbarschaft ab, um jede Kachel aufzunehmen.

Erweiterung des Systems in 3D

Der Algorithmus zum Generieren von Welten erweitert sich natürlich auf Welten mit einer dritten Dimension. Anstelle von farblich passenden 2D-Kacheln mit 4 benachbarten Kacheln entlang gemeinsamer Flächen haben wir jetzt 3D-Kacheln, die farblich mit ihren Nachbarn entlang 6 Flächen übereinstimmen sollten. Betrachten Sie die folgenden 3D-Kacheln:


Der Zusammenbau dieser Kacheln in 3D sieht wie folgt aus:


In diesem Fall sind die zulässigen Nachbarschaften keine zweidimensionalen, sondern dreidimensionale Gitter, und der Algorithmus generiert sie in einem ähnlichen 2D-Fall.

Ergebnisgalerie

Im Folgenden werden die durch die Implementierung dieses Algorithmus erzeugten Welten zusammen mit kurzen Beschreibungen gezeigt.


Screenshot von Generate Worlds mit Raum mit Ausgang. Die Leisten an der Decke fallen mit den Fliesenrändern zusammen.


Ein Screenshot von einem anderen Tool, das ich erstellt habe und das auch den Algorithmus "Welten generieren" verwendet. Es werden verschiedene Arten von Räumen und Fluren gezeigt.


Eine Welt ähnlich der vorherigen, aber jetzt in einer schönen isometrischen Ansicht


Die Welt, deren Schöpfung mich der neunte Kreis von Dantes Hölle inspirierte: Sünder, die im Eis gefroren waren. In MagicaVoxel gerendert.


Die Welt, deren Entstehung mich die zweite Runde von Dantes Hölle inspiriert hat: die Landschaft, die von brennendem Regen bewässert wird und die Brücke überquert. In MagicaVoxel gerendert.


Eine Welt grasbewachsener Plattformen mit Wasserfällen und Flüssen. In MagicaVoxel gerendert.


Landschaft einer mittelalterlichen Stadt mit Gebäuden und Wänden. In MagicaVoxel gerendert.