Feststellen, ob die vom Spieler erstellte Struktur mit einer Vorlage in einem 3D-Blockspiel übereinstimmt

8

Haftungsausschluss: Dies ist eine dieser gefürchteten Fragen im Minecraft-Stil, aber ich denke, es ist eher eine Frage zu Datenstrukturen und Algorithmen

Ich bin wirklich neu in 3D-Datenstrukturen und frage mich, wie ich eine 3D-Blockstruktur am besten speichern und anpassen kann.

Im Moment kann der Spieler Blöcke in einem beliebigen Raum platzieren. Wenn diese Blöcke mit einer vordefinierten Struktur übereinstimmen, tritt ein Ereignis auf. Wenn ein Spieler einen Block platziert, überprüft das Spiel rekursiv jeden benachbarten Block, um den Block mit der niedrigsten x-, y-, z-Koordinate zu finden, und macht diesen Block zum Wurzelblock. Anschließend werden die restlichen Blöcke basierend auf dem Stammblock überprüft, um sicherzustellen, dass sie mit einer bestimmten Vorlage übereinstimmen. Das Problem ist, dass mit der Kompliziertheit der Vorlage auch mein (schrecklich ineffizienter) Code komplizierter wird.

Ich denke, der beste Weg, dies zu tun, besteht darin, eine Art Matrix zu speichern, die die Struktur definiert, und dann mit der Matrix abzugleichen, wenn ein Spieler einen Block platziert. Gibt es bereits Datenstrukturen / Algorithmen, die zu dieser Art von Problem passen würden?

3d algorithm data-structure minecraft-modding WillP
quelle
1
Denken Sie beispielsweise darüber nach, wie Sie Strukturen wie ein Minecraft-Portal vorlegen können?
verzögert
1
@ Daniel Eigentlich denke ich, das wäre ein gutes Beispiel. Mein Ziel wäre jedoch eine beliebig große / komplexe Struktur. Die Portale sind ziemlich einfach.
WillP
1
Keine Antwort, sondern nur ein Gedanke - wenn die Strukturen beliebig groß werden und die Liste der Zielstrukturen (die Sie suchen müssen, um eine Übereinstimmung zu finden) unglaublich groß wird, wird dies zu einem Mustererkennungsproblem, z. B. beim Erkennen von Text oder Sprache. Dann entfernen Sie sich vom Brute-Force-Vergleich hin zu statistischen Methoden wie Hidden-Markov-Modellen, die auf Ihre Zielstrukturen trainiert wurden. Das wäre so cool.
Pieter Müller
@ Harikawashi Oh Mann, das wäre sehr cool. Auch wenn mein Ziel nicht astronomisch groß ist, kann ich es trotzdem tun, nur damit ich damit herumspielen kann. Vielen Dank!
WillP

Antworten:

10

Um ehrlich zu sein, würde ich die einfache Lösung nehmen.

Erstellen Sie eine Matrix, die die Struktur definiert. Wenn ein Block geändert wird, versuchen Sie, diese Matrix auf alle Speicherorte anzuwenden, an denen möglicherweise die neue Struktur erstellt wurde. Das sind Positionen für Breite * Tiefe * Höhe, da der Spieler jeden Punkt auf der Struktur hätte beenden können, aber es sollte nicht so schlimm sein, da die meisten dieser Positionen vorzeitig beendet werden, wenn die erste Prüfung fehlschlägt.

Grundsätzlich haben Sie eine 3D-Matrix und vergleichen sie mit einer anderen 3D-Matrix mit einer Reihe von Offsets.

Von hier aus können Sie eine Reihe völlig optionaler Optimierungen vornehmen. Wenn Ihre Struktur beispielsweise extrem spärlich ist - dh der Spieler baut einen hohen Turm mit einer Kugel oben, aber es ist Ihnen egal, ob die Unterseite des Turms von Bäumen umgeben ist -, können Sie daraus eine Liste von erstellen Blöcke anstelle einer Matrix. (Ich würde die Liste aus der Matrix generieren - die Matrix ist viel einfacher direkt zu pflegen.)

Wenn Sie super klug sein wollen, teilen Sie die Struktur in Blocktypen auf. Wenn Sie wissen, dass der Spieler gerade Block 1,2,3 geändert hat und Sie wissen, dass für das Platzieren Ihrer Struktur bei den Koordinaten 0,0,0 Block 1,2,3 Obsidian sein muss und Block 1,2,3 Holz ist , dann müssen Sie nicht einmal Block 1,2,3 ausprobieren. Generieren Sie alle möglichen Offsets für die Struktur, vorausgesetzt, der Spieler hat gerade einen bestimmten Blocktyp platziert. Wenn der Spieler diesen Block platziert, überprüfen Sie einfach die vorgenerierten möglichen Offsets.

Aber im Ernst, das ist alles Optimierung. Erstellen Sie einfach eine Matrix und vergleichen Sie Ihre Matrix mit dem Brute-Force-Stil der Welt. Angenommen, Sie machen etwas Minecrafty, platzieren die Leute wirklich nicht so viele Blöcke - höchstens ein paar Blöcke pro Sekunde. Wenn Sie nicht Hunderte von riesigen Strukturen haben, können Sie dies einfach testen.

ZorbaTHut
quelle
3
Du hast recht. Brute Forcing sollte eigentlich kein großes Leistungsproblem sein. Ich habe das Gefühl, in die Falle einer vorzeitigen Optimierung geraten zu sein. Vielen Dank für Ihren Einblick.
WillP
0

Nun, Sie haben ein interessantes Problem. Ich würde Folgendes vorschlagen: Verwenden Sie Ihre Blöcke als Pixel und führen Sie eine Kollisionserkennung pro Pixel durch, bei der alle Blöcke übereinstimmen müssen, um eine echte Kollision zurückzugeben.

Dies würde gut funktionieren, stellen Sie jedoch sicher, dass Sie dies nur tun, wenn sich Objekte / Blöcke ändern. Daher würde ich ein einfaches Ereignissystem empfehlen, um eine Änderung an einen Objektprüfer zu übergeben, der sicherlich Ihren Algorithmus verwenden kann. Welches würde dann tun, was immer Sie wollen, dass dieses Objekt tut. Außerdem würde ich empfehlen, Höhe und Breite zu überprüfen, bevor Sie den Algorithmus ausführen, da er offensichtlich nicht übereinstimmt, wenn er nicht hoch genug / zu hoch ist.

In Bezug auf eine Datenstruktur würde ein einfacher Vektor oder möglicherweise eine benutzerdefinierte Datenstruktur ausreichen.

Interessante Frage.

Avlagrath
quelle