How could I implement something like Minecraft's crafting grid?

Question

The crafting system in Minecraft uses a 2x2 or 3x3 grid. You place ingredients on the grid, and if you put the right ingredients in the right pattern, it will activate the recipe.

Some interesting points about the design:

• Some recipes can exchange certain ingredients for others. For example, a pick uses sticks for the haft, and may use wooden planks, cobblestone, iron ingots, gold ingots, or diamond gems for the head.
• Relative position within the pattern is what matters, not absolute position on the grid. That is, you can craft a torch by placing the stick and coal (or charcoal) in the correct pattern in any of six positions on the 3x3 grid.
• Patterns may be flipped horizontally.

I may be overthinking it, but this seems like an interesting search/set-reduction problem. So, how does (or could) this work, algorithmically speaking?

Answer 1

Another solution is to use a somewhat complicated tree. The branch nodes in your tree would be created by iterating over the recipe (once again using for (y) { for (x) }); this is your stock-standard by-the-book tree structure. Your final node would contain an additional structure (Dictionary/HashMap) that maps dimensions to recipes.

Essentially what you are going for is this:

The black nodes are your branches that indicate item type - the red ones are your leaves (terminators) which allow you to differentiate size/orientation.

To search over this tree you would first find the bounding box (as outlined in my first answer) and then iterate over the nodes in the same order traversing the tree as you go. Finally you would simply look up the dimension in your Dictionary or HashMap and you would get the result of the recipe.

Just for kicks I went and implemented this - which will probably clarify my answer. Also: I realise this is a different answer - and rightfully so: it's a different solution.

Answer 2

You have to remember that Minecraft only uses a very small set of possible recipes, so there is no need for anything all that smart.

That said what I would do is find the smallest grid that fits (i.e. ignore empty rows and columns to find out if it's a 2x2 or 3x3, or 2x3 (door)). Then loop through the list of recipes with that size, simply checking whether the item type is the same (i.e., at worst 9 integer comparisons in minecraft since it uses an integer type id for items and blocks) and stop when you find a match.

This way also makes the relative position of the items irrelevant (you can put a torch anywhere on the crafting grid and it will work because it sees it as a 1x2 box, not a 3x3 box which is mostly empty).

If you have a huge amount of recipes so that doing a linear search through the possible matches takes to long it would be possible to sort the list and do a binary search (O(log(N)) vs O(N)). This would cause some extra work in building the list, but this can be done at startup once and kept in memory afterwards.

Also one last thing, to allow flipping the recipe horizontally simplest would be to just add the mirrored version to the list.

If you want to do it without adding a second recipe you can check whether the input recipe has an item in [0,0] with higher id than in [0,2] (or [0,1] for 2x2, no check needed for 1x2 and if so mirror it, if not continue checking the next row until you've reached the end. Using this you also have to make sure the recipes are added in the correct rotation.

Answer 3

Seeing if a certain grid configuration matches a certain recipe is simple if you encode the 3x3 grid as a string and use a regular expression match. Speeding up the look up is a different matter, which I'll talk about in the end. Read on for more information.

Step 1) Encode grid as String

Simply give a char id to each type of cell and concatenate everything side by side in this order:

123
456 => 123456789
789

And as a more concrete example, consider the stick recipe, where W stands for wood and E is an empty cell (you could simply use an empty char ' '):

EEE
WEE => EEEWEEWEE
WEE

Step 2) Match Recipe using Regular Expression (or String.Contains with a bit of processing on the data)

Continuing from the example above, even if we move the formation around, there's still a pattern in the string (WEEW padded by E on both sides):

EEW
EEW => EEWEEWEEE
EEE

So no matter where you move the stick around, it will still match the following regular expression: /^E*WEEWE*$/

Regular expressions also let you perform the conditional behavior you mentioned. For instance (made up recipe), if you wanted a pickaxe made of iron or stone to give the same result, i.e:

III    SSS
EWE or EWE
EWE    EWE

You could combine both into the regular expression: /^(III)|(SSS)EWEEWE$/

Horizontal flips can also be added just as easily (using the | operator too).

Edit: Anyway, the regex part is not strictly necessary. It's just one way to encapsulate the problem in a single expression But for the variable location problem you could just as well trim the grid string of any padding spaces (or E's in this example) and do a String.Contains(). And for the multiple ingredient problem or the mirrored recipes, you could just handle all of them as multiple (i.e. separate) recipes with the same output.

Step 3) Speeding up Lookup

As for reducing the search, you will need to create some data structure to group recipes together and help with lookup. Treating the grid as string has some advantages here too:

1. You could define the "length" of a recipe as being the distance between the first non-empty character and the last non-empty character. A simple Trim().Length() would give you this information. Recipes could be grouped by length and stored in a dictionary.

   or

   An alternative definition of "length" could be the number of non-empty characters. Nothing else changes. You could group recipes by this criteria too.

2. If point number 1 is not enough, recipes may also be further grouped by the type of the first ingredient that appears in the recipe. This would be as simple as doing Trim().CharAt(0) (and guarding against Trim resulting an empty string).

So for instance you would store recipes in a:

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

And perform the lookup as something like:

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

Answer 4

I can't tell you how the Minecraft one works - although I am sure if you looked at MCP (if you have a legal copy of Minecraft) you could find out.

I would implement this as follows:

1. Have some disk-based dictionary/hashmap (B+Tree/SQL-Light) - the value would be the item ID of the recipe result.
2. When a user is crafting something simply find the first row/column with an item INDEPENDENTLY; combine those into an offset.
3. Find the last row/column with an item, again, independently.
4. Compute the width and height from the items and add it to the key.
5. Loop over the range of the bounding box you just computed and append the ID of each item (using your usual for (y) { for (x) }).
6. Look the key up in the database.

So for example lets say we have two ingredients; X and Y and blanks being *. Take the following recipe:

**X
**Y
**Y

First we work out the bounding box, yielding (2,0)-(2,2). Therefore our key would look like this [1][3] (1 width, 3 height). Next we loop over each item within the bounding box and append the ID, thus the key becomes [1][3][X][Y][Y] - you then look this up in your dictionary/DB and you will get the result of that recipe.

To explain the independence in step 2 more clearly, consider the following recipe:

*XX
XXX
XX*

The top/left is clearly at 0,0 - however the first item you would typically encounter would be either 0,1 or 1,0 (depending on your loop). However if find the first non-empty column as well as the first non-empty row and combine those co-ordinates you will get 0,0 - the same principal applies to the bottom/right of the bounding box.

Answer 5

Here is how I did it in Block Story: