Wie könnte ich so etwas wie Minecrafts Handwerksgitter implementieren?

55

Das Crafting-System in Minecraft verwendet ein 2x2- oder 3x3-Raster. Sie legen Zutaten auf das Gitter und wenn Sie die richtigen Zutaten in das richtige Muster setzen, wird das Rezept aktiviert.

Einige interessante Punkte zum Design:

  • Einige Rezepte können bestimmte Zutaten gegen andere austauschen. Zum Beispiel verwendet ein Pick Stöcke für den Griff und kann Holzbretter, Kopfsteinpflaster, Eisenbarren, Goldbarren oder Diamantedelsteine ​​für den Kopf verwenden.
  • Es kommt auf die relative Position innerhalb des Musters an, nicht auf die absolute Position auf dem Gitter. Das heißt, Sie können eine Fackel herstellen, indem Sie den Stab und die Kohle (oder Holzkohle) im richtigen Muster an einer der sechs Positionen des 3x3-Gitters platzieren.
  • Muster können horizontal gespiegelt werden.

Ich mag es überdenken, aber dies scheint ein interessantes Problem bei der Suche / Reduzierung von Sätzen zu sein. Wie funktioniert (oder könnte) das algorithmisch?

David Eyk
quelle
6
Ehrfürchtige Frage! Ich bin sehr interessiert! Ich habe schon einige Ideen, aber ich werde sie teilen, sobald ich nach Hause komme.
JCORA
Ich versuche tatsächlich, eine Minecraft-Kopie so nah wie möglich zu schreiben. Ich habe das gesamte Inventar- und Rezeptmanager-Material bereits geschrieben und ich muss sagen, dass es sehr gut funktioniert. Ich bin zufrieden mit dem sauberen Code. Es war jedoch nicht einfach, es zu schreiben. Ich habe ungefähr 10 Klassen geschrieben, damit alles gut funktioniert, Rezepte, Gitter, Inventar usw. Wenn ich etwas Zeit finde, schreibe ich eine Antwort.
Martijn Courteaux
Sie sollten sich ansehen, wie minecraft ihre Herstellungsrezepte codiert.
Bradman175

Antworten:

14

Eine andere Lösung besteht darin, einen etwas komplizierten Baum zu verwenden. Die Verzweigungsknoten in Ihrem Baum werden erstellt, indem Sie das Rezept durchlaufen (erneut verwenden for (y) { for (x) }). Dies ist Ihre Standard-Baumstruktur. Ihr letzter Knoten würde eine zusätzliche Struktur ( Dictionary/ HashMap) enthalten, die den Rezepten Dimensionen zuordnet.

Im Wesentlichen geht es um Folgendes:

Rezeptbaum

Die schwarzen Knoten sind Ihre Zweige, die den Elementtyp angeben - die roten sind Ihre Blätter (Abschlusszeichen), mit denen Sie Größe / Ausrichtung unterscheiden können.

Um diesen Baum zu durchsuchen, müssen Sie zuerst den Begrenzungsrahmen finden (wie in meiner ersten Antwort beschrieben ) und dann die Knoten in der gleichen Reihenfolge durchlaufen, in der Sie den Baum durchlaufen. Schließlich würden Sie einfach die Dimension in Ihrem Dictionaryoder nachschlagen HashMapund das Ergebnis des Rezepts erhalten.

Nur zum Spaß habe ich das implementiert - was wahrscheinlich meine Antwort verdeutlichen wird. Außerdem : Mir ist klar, dass dies eine andere Antwort ist - und das zu Recht: Es ist eine andere Lösung.

Jonathan Dickinson
quelle
Sehr einfach. Ich mag das.
David Eyk
Ich werde dieses akzeptieren, weil ich Bäume, Haschisch und Diagramme mag, die den Kern der Sache treffen. Ein Blick auf das Diagramm und ich habe Ihren Algorithmus fast sofort verstanden.
David Eyk
23

Sie müssen sich daran erinnern, dass Minecraft nur einen sehr kleinen Satz möglicher Rezepte verwendet, so dass nichts allzu Schlaues erforderlich ist.

Das heißt, ich würde das kleinste Gitter finden, das passt (dh leere Zeilen und Spalten ignorieren, um herauszufinden, ob es ein 2x2 oder 3x3 oder 2x3 (Tür) ist). Durchlaufen Sie dann die Liste der Rezepte mit dieser Größe und überprüfen Sie einfach, ob der Elementtyp derselbe ist (dh im schlimmsten Fall 9 Ganzzahlvergleiche in Minecraft, da eine Ganzzahltyp-ID für Elemente und Blöcke verwendet wird), und hören Sie auf, wenn Sie eine Übereinstimmung finden.

Auf diese Weise wird auch die relative Position der Gegenstände irrelevant (Sie können eine Fackel an einer beliebigen Stelle auf dem Herstellungsgitter platzieren und es funktioniert, da es sich um eine 1x2-Box handelt, nicht um eine 3x3-Box, die größtenteils leer ist).

Wenn Sie eine große Anzahl von Rezepten haben, so dass eine lineare Suche durch die möglichen Übereinstimmungen zu lange dauert, ist es möglich, die Liste zu sortieren und eine binäre Suche durchzuführen (O (log (N)) vs O (N)). Dies würde einige zusätzliche Arbeit beim Erstellen der Liste verursachen, kann jedoch beim Start einmal ausgeführt und anschließend im Speicher behalten werden.

Um das Rezept am einfachsten horizontal spiegeln zu können, fügen Sie einfach die gespiegelte Version zur Liste hinzu.

Wenn Sie dies tun möchten, ohne ein zweites Rezept hinzuzufügen, können Sie überprüfen, ob das Eingangsrezept einen Eintrag in [0,0] mit einer höheren ID als in [0,2] (oder [0,1] für 2x2 hat, ohne dass eine Überprüfung erforderlich ist für 1x2 und wenn ja, spiegeln Sie es, wenn Sie die nächste Zeile nicht bis zum Ende durchsehen, und stellen Sie sicher, dass die Rezepte in der richtigen Rotation hinzugefügt wurden.

Elva
quelle
1
Ich fragte mich, ob sich die geringe Anzahl an Rezepten in Minecraft möglicherweise nicht für eine lineare Suche eignet.
David Eyk
1
Es funktioniert und ist im Grunde das, was ich oben geschrieben habe (mit möglicher Optimierung der binären Suche). Das lässt jedoch ein paar Optionen für die Herstellung von Taschenlampen, die Sie im Grunde überall einsetzen können. Wenn Sie zuerst die Größe des Rezepts erhalten, müssen Sie keine 6 Rezepte für Fackeln hinzufügen und beschränken Ihre Suche in einem Schritt auf diejenigen, die die richtige Größe haben. - Grundsätzlich sind die Optionen für Punkt 2 nach Größe gruppiert, verschieben Sie das Rezept in eine Ecke oder fügen Sie weitere doppelte Rezepte hinzu.
Elva
15

Zu sehen, ob eine bestimmte Gitterkonfiguration mit einem bestimmten Rezept übereinstimmt, ist einfach, wenn Sie das 3x3-Gitter als Zeichenfolge codieren und eine Übereinstimmung mit regulären Ausdrücken verwenden . Das Nachschlagen zu beschleunigen ist eine andere Sache, über die ich am Ende sprechen werde. Lesen Sie weiter für weitere Informationen.

Schritt 1) ​​Codiere das Gitter als String

Geben Sie einfach eine Zeichen-ID für jeden Zellentyp an und verknüpfen Sie alles in dieser Reihenfolge nebeneinander:

123
456 => 123456789
789

Betrachten Sie als konkretes Beispiel das Stabrezept, bei dem W für Holz steht und E eine leere Zelle ist (Sie könnten einfach ein leeres Zeichen '' verwenden):

EEE
WEE => EEEWEEWEE
WEE

Schritt 2) Rezept mit regulärem Ausdruck abgleichen (oder String.Contains mit ein wenig Verarbeitung der Daten)

Selbst wenn wir die Formation bewegen, befindet sich im obigen Beispiel noch ein Muster in der Zeichenfolge (WEEW wird auf beiden Seiten mit E aufgefüllt):

EEW
EEW => EEWEEWEEE
EEE

Unabhängig davon, wo Sie den Stick bewegen, entspricht er dem folgenden regulären Ausdruck: /^E*WEEWE*$/

Mit regulären Ausdrücken können Sie auch das von Ihnen erwähnte bedingte Verhalten ausführen. Zum Beispiel (erfundenes Rezept), wenn Sie eine Spitzhacke aus Eisen oder Stein haben möchten , um das gleiche Ergebnis zu erzielen:

III    SSS
EWE or EWE
EWE    EWE

Sie können beide zu einem regulären Ausdruck kombinieren: /^(III)|(SSS)EWEEWE$/

Genauso einfach können auch horizontale Flips hinzugefügt werden (auch mit dem Operator |).

Bearbeiten: Wie auch immer, der Regex-Teil ist nicht unbedingt erforderlich. Dies ist nur eine Möglichkeit, das Problem in einem einzelnen Ausdruck zu kapseln. Für das Problem mit der variablen Position können Sie jedoch auch die Rasterzeichenfolge aller Auffüllbereiche (oder in diesem Beispiel die von "E") abschneiden und ein String.Contains () ausführen. Und für das Problem mit mehreren Zutaten oder die gespiegelten Rezepte könnten Sie einfach alle als mehrere (dh separate) Rezepte mit derselben Ausgabe behandeln.

Schritt 3) Beschleunigen der Suche

Um die Suche zu reduzieren, müssen Sie eine Datenstruktur erstellen, um Rezepte zu gruppieren und bei der Suche zu helfen. Das Behandeln des Gitters als Zeichenfolge hat auch hier einige Vorteile :

  1. Sie können die "Länge" eines Rezepts als den Abstand zwischen dem ersten nicht leeren Zeichen und dem letzten nicht leeren Zeichen definieren. Ein einfacher Trim().Length()würde Ihnen diese Informationen geben. Rezepte können nach Länge gruppiert und in einem Wörterbuch gespeichert werden.

    oder

    Eine alternative Definition von "Länge" könnte die Anzahl nicht leerer Zeichen sein. Sonst ändert sich nichts. Sie können Rezepte auch nach diesen Kriterien gruppieren.

  2. Wenn Punkt Nummer 1 nicht ausreicht, können die Rezepte auch nach der Art der ersten Zutat, die im Rezept enthalten ist, weiter gruppiert werden. Dies wäre so einfach wie das Ausführen Trim().CharAt(0)(und das Sichern gegen Trimmen, was zu einer leeren Zeichenfolge führt).

So würden Sie beispielsweise Rezepte speichern in:

Dictionary<int, Dictionary<char, List<string>>> _recipes;

Und führen Sie die Suche wie folgt aus:

// A string encode of your current grid configuration 
string grid;

// Get length and first char in our grid
string trim = grid.Trim();
int length = trim.Length();
char firstChar = length==0 ? ' ' : trim[0];

foreach(string recipe in _recipes[length][firstChar])
{
    // Check for a match with the recipe
    if(Regex.Match(grid, recipe))
    {
        // We found a matching recipe, do something with it
    }
}
David Gouveia
quelle
3
Das ist ... sehr sehr schlau.
Raveline
18
Sie haben ein Problem und möchten es mit regulären Ausdrücken lösen? Jetzt haben Sie 2 Probleme :)
Kromster sagt Unterstützung Monica
2
@Krom Ich nehme an, du machst wahrscheinlich nur Spaß, aber irgendwelche Gründe für diesen Kommentar? Die Verwendung eines regulären Ausdrucks ist nur eine kurze (Übereinstimmung von Raster und Rezept mit einer einzigen Codezeile) und flexible (entspricht allen Anforderungen dieses Problems) Möglichkeit, einen Abgleich für einen Datensatz (den Rasterinhalt) durchzuführen. Ich sehe keine wesentlichen Nachteile gegenüber dem Rolling Ihres eigenen Matching-Algorithmus, und dies vereinfacht den gesamten Prozess.
David Gouveia
2
@DavidGouveia, das ist nur ein Satz für Leute, die sich mit Regex nicht so wohl fühlen. Wenn sie sich entscheiden, ein Problem mit Regex zu lösen, haben sie jetzt zwei Probleme: (1) das eigentliche Problem, das sie lösen möchten, (2) das Regex-Muster zu schreiben, um dieses Problem zu lösen
bösartig
2
Zurück zu "Jetzt haben Sie zwei Probleme" - Regex wird Probleme haben, sobald Sie mehr Elemente als den druckbaren ASCII-Bereich haben, es sei denn, Ihr Regex-Prozessor unterstützt Unicode und Sie können garantieren, dass bestimmte Kombinationen den Regex-NFA-Compiler nicht auslösen Nach oben. Sie können Ihren eigenen DFA (eigentlich ganz einfach) zusammenstellen, um Muster abzugleichen. Aber Regex wäre der beste Weg beim Prototyping.
Jonathan Dickinson
3

Ich kann dir nicht sagen, wie Minecraft funktioniert - obwohl ich mir sicher bin, dass du es herausfinden könntest, wenn du dir MCP ansiehst (wenn du eine legale Kopie von Minecraft hast).

Ich würde das wie folgt umsetzen:

  1. Habe ein festplattenbasiertes Wörterbuch / Hashmap ( B + Tree / SQL-Light ) - der Wert wäre die Item-ID des Rezept-Ergebnisses.
  2. Wenn ein Benutzer etwas herstellt, findet er einfach die erste Zeile / Spalte mit einem UNABHÄNGIGEN Gegenstand . Kombinieren Sie diese zu einem Offset.
  3. Suchen Sie die letzte Zeile / Spalte mit einem Element erneut unabhängig.
  4. Berechnen Sie die Breite und Höhe der Elemente und fügen Sie sie dem Schlüssel hinzu.
  5. Durchlaufen Sie den Bereich des Begrenzungsrahmens, den Sie gerade berechnet haben, und hängen Sie die ID jedes Elements an (wie gewohnt for (y) { for (x) }).
  6. Schlagen Sie den Schlüssel in der Datenbank nach.

Nehmen wir zum Beispiel an, wir haben zwei Zutaten; X und Y und Leerzeichen sind *. Nimm das folgende Rezept:

**X
**Y
**Y

Zuerst erarbeiten wir den Begrenzungsrahmen und geben nach (2,0)-(2,2). Daher würde unser Schlüssel so aussehen [1][3](1 Breite, 3 Höhe). Als nächstes durchlaufen wir jedes Element innerhalb des Begrenzungsrahmens und hängen die ID an, so dass der Schlüssel wird [1][3][X][Y][Y]- Sie sehen dies dann in Ihrem Wörterbuch / Ihrer Datenbank nach und erhalten das Ergebnis dieses Rezepts.

Beachten Sie das folgende Rezept, um die Unabhängigkeit in Schritt 2 klarer zu erläutern:

*XX
XXX
XX*

Oben / links steht eindeutig 0,0 - das erste Element, auf das Sie normalerweise stoßen, ist jedoch entweder 0,1 oder 1,0 (abhängig von Ihrer Schleife). Wenn Sie jedoch die erste nicht leere Spalte sowie die erste nicht leere Zeile finden und diese Koordinaten kombinieren, erhalten Sie 0,0 - das gleiche Prinzip gilt für die untere / rechte Ecke des Begrenzungsrahmens.

Jonathan Dickinson
quelle
Das Bukkit-Repository hat keinen Minecraft-Code, Sie benötigen MCP (und eine Kopie von Minecraft)
BlueRaja - Danny Pflughoeft
Ist das nicht nur die Umkehrung Ihrer anderen Antwort?
David Eyk
@DavidEyk (Dies ist meine erste Antwort) nicht wirklich, es hängt mehr von einer Hashmap-Struktur ab (ob es bigtable-like oder in-memory ist). Der Grund, warum ich erneut geantwortet habe, ist, dass ich mir Sorgen über Hash-Kollisionen machte, die zu einer schlechten Leistung führten - zumindest in einer speicherinternen Hashmap. Meine andere Antwort würde für mehr Elemente und eine In-Memory-Struktur besser funktionieren - wo dies besser funktionieren würde, wenn es in SQL / etc wäre.
Jonathan Dickinson