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

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?

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:

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.

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.

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
    }
}

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.

Voici comment je l'ai fait dans Block Story: