Comment puis-je implémenter quelque chose comme la grille de création de Minecraft?

55

Le système d'artisanat de Minecraft utilise une grille 2x2 ou 3x3. Vous placez les ingrédients sur la grille et si vous placez les bons ingrédients dans le bon motif, la recette sera activée.

Quelques points intéressants sur le design:

  • Certaines recettes peuvent échanger certains ingrédients contre d’autres. Par exemple, une pioche utilise des bâtons pour le manche et peut utiliser des planches de bois, des pavés, des lingots de fer, des lingots d'or ou des pierres précieuses en diamants pour la tête.
  • Ce qui compte, c’est la position relative dans le motif, et non la position absolue sur la grille. En d’autres termes, vous pouvez fabriquer une torche en plaçant le bâton et le charbon (ou le charbon de bois) selon le bon modèle, dans l’une des six positions de la grille 3x3.
  • Les motifs peuvent être retournés horizontalement.

J'y réfléchis peut-être, mais cela semble être un problème intéressant de recherche / réduction des ensembles. Alors, comment cela fonctionne-t-il (ou pourrait-il), de manière algorithmique?

David Eyk
la source
6
Super question! Je suis très intéressé! J'ai déjà quelques idées mais je les partagerai dès mon retour à la maison.
jcora
J'essaie en fait d'écrire une copie de Minecraft "aussi proche que possible". J'ai déjà écrit tout le matériel d'inventaire et de gestion des recettes et je dois dire que cela fonctionne très bien. Je suis satisfait du code propre. Cependant, il n'a pas été facile de l'écrire. J'ai écrit environ 10 cours pour que tout fonctionne correctement avec les recettes, les grilles, l'inventaire, etc. Quand je trouverai du temps, j'écrirai une réponse.
Martijn Courteaux
Vous devriez regarder comment Minecraft code leurs recettes d'artisanat.
Bradman175

Réponses:

14

Une autre solution consiste à utiliser un arbre un peu compliqué. Les nœuds de branche de votre arbre seraient créés en effectuant une itération sur la recette (à nouveau en utilisant for (y) { for (x) }); Il s'agit de l'arborescence standard du livre. Votre dernier nœud contiendrait une structure supplémentaire ( Dictionary/ HashMap) qui mapperait les dimensions aux recettes.

Ce que vous allez faire est essentiellement ceci:

Arbre de recette

Les nœuds noirs sont vos branches qui indiquent le type d'élément. Les rouges sont vos feuilles (terminateurs) qui vous permettent de différencier la taille / l'orientation.

Pour effectuer une recherche dans cet arbre, vous devez d'abord trouver le cadre de sélection (comme indiqué dans ma première réponse ), puis parcourir les nœuds dans le même ordre que vous avez parcouru. Enfin, il vous suffira de rechercher la dimension dans votre Dictionaryou HashMapet d’obtenir le résultat de la recette.

Juste pour le plaisir, j’ai mis en œuvre ceci - ce qui clarifiera probablement ma réponse. Aussi : je réalise que c'est une réponse différente - et à juste titre: c'est une solution différente.

Jonathan Dickinson
la source
Très simple. Je l'aime.
David Eyk
J'accepterai celui-ci, car j'aime les arbres, les hachages et les schémas qui vont droit au but. Un coup d’oeil au diagramme et j’ai compris votre algorithme presque immédiatement.
David Eyk
23

N'oubliez pas que Minecraft n'utilise qu'un très petit ensemble de recettes possibles. Il n'est donc pas nécessaire d'utiliser une solution aussi intelligente.

Cela dit, je voudrais trouver la plus petite grille qui convient (ignorer les lignes et les colonnes vides pour savoir s’il s’agit d’un 2x2 ou de 3x3 ou de 2x3 (porte)). Parcourez ensuite la liste des recettes de cette taille, en vérifiant simplement si le type d’article est identique (c’est-à-dire, au pire 9 comparaisons d’entiers dans Minecraft puisqu’il utilise un identifiant de type entier pour les articles et les blocs) et s’arrête lorsque vous trouvez une correspondance.

De cette manière, la position relative des objets n’a plus d’importance (vous pouvez placer une lampe de poche n’importe où sur la grille d’artisanat et elle fonctionnera car elle la verra comme une boîte 1x2 et non comme une boîte 3x3 généralement vide).

Si vous avez un grand nombre de recettes de sorte que faire une recherche linéaire parmi les correspondances possibles prend trop de temps, il serait possible de trier la liste et de faire une recherche binaire (O (log (N)) vs O (N)). Cela nécessiterait un travail supplémentaire lors de la construction de la liste, mais cela peut être fait au démarrage une fois et conservé en mémoire par la suite.

Une dernière chose, pour permettre de retourner la recette horizontalement plus simplement, serait simplement d’ajouter la version en miroir à la liste.

Si vous voulez le faire sans ajouter de seconde recette, vous pouvez vérifier si la recette en entrée contient un élément dans [0,0] avec un ID supérieur à celui dans [0,2] (ou [0,1] pour 2x2, aucune vérification nécessaire.) pour 1x2 et si c'est le cas, continuez de vérifier la ligne suivante jusqu'à la fin, sinon vérifiez que les recettes sont ajoutées dans la rotation correcte.

Elva
la source
1
Je me demandais si le petit nombre de recettes dans Minecraft ne se prêterait pas à une recherche linéaire.
David Eyk
1
C’est le cas et c’est ce que j’ai écrit plus haut (avec une optimisation possible de la recherche binaire). Cependant, cela laisse quelques options pour fabriquer des torches que vous pouvez adapter pratiquement n'importe où. En obtenant d'abord la taille de la recette, vous n'avez pas besoin d'ajouter 6 recettes pour les flambeaux et vous limitez votre recherche à celles de la taille correcte en une seule étape. - Les options de votre point 2 sont donc regroupées par taille, déplacez la recette dans un coin ou ajoutez des recettes en double.
Elva
15

Voir si une certaine configuration de grille correspond à une certaine recette est simple si vous codez la grille 3x3 sous forme de chaîne et utilisez une correspondance d' expression régulière . Accélérer la recherche est une autre affaire, dont je parlerai à la fin. Lisez la suite pour plus d'informations.

Étape 1) Encoder la grille en tant que chaîne

Donnez simplement un identifiant de caractère à chaque type de cellule et concaténez tout dans cet ordre:

123
456 => 123456789
789

Et comme exemple plus concret, considérons la recette du bâton, dans laquelle W représente le bois et E la cellule vide (vous pouvez simplement utiliser un caractère vide ''):

EEE
WEE => EEEWEEWEE
WEE

Étape 2) Match Recipe using Regular Expression (ou String.Contains avec un peu de traitement sur les données)

En reprenant l'exemple ci-dessus, même si nous déplaçons la formation, il reste un motif dans la chaîne (WEEW complété par E des deux côtés):

EEW
EEW => EEWEEWEEE
EEE

Ainsi, peu importe où vous déplacez le bâton, il correspondra toujours à l'expression régulière suivante: /^E*WEEWE*$/

Les expressions régulières vous permettent également d’effectuer le comportement conditionnel que vous avez mentionné. Par exemple (recette préparée), si vous vouliez une pioche en fer ou en pierre pour obtenir le même résultat, à savoir:

III    SSS
EWE or EWE
EWE    EWE

Vous pouvez combiner les deux dans l'expression régulière: /^(III)|(SSS)EWEEWE$/

Des retournements horizontaux peuvent également être ajoutés tout aussi facilement (en utilisant l'opérateur |).

Edit: Quoi qu’il en soit, la partie regex n’est pas strictement nécessaire. C'est juste une façon d'encapsuler le problème dans une seule expression. Mais pour le problème d'emplacement de variable, vous pouvez également couper la chaîne de grille de tout espace de remplissage (ou E dans cet exemple) et faire un String.Contains (). Et pour le problème des ingrédients multiples ou les recettes en miroir, vous pouvez simplement les traiter comme des recettes multiples (c.-à-d. Séparées) avec le même résultat.

Étape 3) Accélération de la recherche

En ce qui concerne la réduction de la recherche, vous devrez créer une structure de données pour regrouper les recettes et faciliter la recherche. Traiter la grille en tant que chaîne présente également certains avantages :

  1. Vous pouvez définir la "longueur" d'une recette comme étant la distance entre le premier caractère non vide et le dernier caractère non vide. Un simple Trim().Length()vous donnerait cette information. Les recettes peuvent être regroupées par longueur et stockées dans un dictionnaire.

    ou

    Une autre définition de "longueur" pourrait être le nombre de caractères non vides. Rien d'autre ne change. Vous pouvez également regrouper les recettes selon ce critère.

  2. Si le point 1 ne suffit pas, vous pouvez également regrouper les recettes en fonction du type de premier ingrédient figurant dans la recette. Cela serait aussi simple que de le faire Trim().CharAt(0)(et d' éviter que Trim ne crée une chaîne vide).

Ainsi, par exemple, vous stockeriez des recettes dans un:

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

Et effectuez la recherche comme suit:

// 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
la source
3
C'est ... très très intelligent.
Raveline
18
Vous avez un problème et vous voulez le résoudre en utilisant des expressions régulières? Maintenant, vous avez 2 problèmes :)
Kromster dit de soutenir Monica
2
@Krom Je suppose que vous plaisantez probablement, mais y a-t-il un raisonnement derrière ce commentaire? L'utilisation d'une expression régulière est juste un moyen concis (correspondance grille-recette avec une seule ligne de code) et flexible (s'adapte à toutes les exigences de ce problème) pour effectuer la correspondance sur un ensemble de données (le contenu de la grille). Je ne vois pas d'inconvénient majeur à utiliser votre propre algorithme d'appariement, ce qui simplifie l'ensemble du processus.
David Gouveia
2
@ David Gouveia, ce n'est qu'une phrase pour les personnes qui ne sont pas trop à l'aise avec Regex. S'ils décident de résoudre un problème avec regex, ils ont maintenant deux problèmes: (1) le problème qu'ils veulent résoudre (2) écrire le motif de regex pour résoudre ce problème
iamserious
2
Revenons à «maintenant vous avez deux problèmes» - Regex aura des problèmes dès que vous aurez plus d'éléments que la plage imprimable en ASCII, à moins que votre processeur regex ne prenne en charge l'unicode et que vous puissiez garantir que certaines combinaisons ne déclencheront pas le compilateur NFA regex. up. Vous pouvez créer votre propre DFA (assez facilement en réalité) pour faire correspondre les modèles; mais regex serait le meilleur moyen de prototyper.
Jonathan Dickinson
3

Je ne peux pas vous dire comment fonctionne celui de Minecraft - même si je suis sûr que si vous avez consulté MCP (si vous avez une copie légale de Minecraft), vous pourriez le savoir.

Je mettrais en œuvre ceci comme suit:

  1. Avoir un dictionnaire / hashmap sur disque ( B + Tree / SQL-Light ) - la valeur serait l’ID de l’article du résultat de la recette.
  2. Lorsqu'un utilisateur crée quelque chose, il suffit de trouver la première ligne / colonne avec un élément INDEPENDENT ; combinez ceux-ci dans un offset.
  3. Recherchez la dernière ligne / colonne avec un élément, à nouveau, indépendamment.
  4. Calcule la largeur et la hauteur des éléments et les ajoute à la clé.
  5. Boucle sur la plage de la boîte de sélection que vous venez de calculer et ajoutez l'ID de chaque élément (en utilisant votre habituel for (y) { for (x) }).
  6. Regardez la clé dans la base de données.

Donc, par exemple, disons que nous avons deux ingrédients; X et Y et les blancs étant *. Prenez la recette suivante:

**X
**Y
**Y

Nous élaborons d’abord la boîte englobante en cédant (2,0)-(2,2). Par conséquent, notre clé ressemblerait à ceci [1][3](1 largeur, 3 hauteur). Ensuite, nous passons en boucle sur chaque élément du cadre de sélection et ajoutons l’ID, ainsi la clé devient [1][3][X][Y][Y]: vous le recherchez ensuite dans votre dictionnaire / base de données et vous obtiendrez le résultat de cette recette.

Pour expliquer plus clairement l'indépendance à l'étape 2, considérez la recette suivante:

*XX
XXX
XX*

Le haut / gauche est clairement à 0,0 - cependant, le premier élément que vous rencontreriez généralement serait 0,1 ou 1,0 (selon votre boucle). Cependant, si vous trouvez la première colonne non vide ainsi que la première ligne non vide et combinez ces coordonnées, vous obtiendrez 0,0 - le même principe s'applique au bas / à la droite du cadre de sélection.

Jonathan Dickinson
la source
Le référentiel Bukkit n'a pas de code Minecraft, vous aurez besoin de MCP (et d'une copie de Minecraft)
BlueRaja - Danny Pflughoeft Le
N'est-ce pas l'inverse de votre autre réponse?
David Eyk
@ DavidEyk (Ceci est ma première réponse) pas vraiment, il est plus dépendant d'une structure de hashmap (que ce soit bigtable ou en mémoire). La raison pour laquelle j'ai de nouveau répondu, c'est parce que je m'inquiétais des collisions de hasch entraînant de mauvaises performances, du moins dans un hashmap en mémoire. Mon autre réponse fonctionnerait mieux pour plus d'éléments et une structure en mémoire - où cela fonctionnerait mieux si elle était en SQL / etc.
Jonathan Dickinson