Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
6  
Awesome question! I'm very interested! I do have some ideas already but and I'll share them as soon as I get home. –  jco Dec 28 '11 at 8:45
    
I'm actually trying to write an "as-close-as-possible" Minecraft copy. I wrote all the inventory and recipe manager stuff already and I have to say it is working very neat. I'm satisfied about the clean code. However, it was not easy to write it. I wrote about 10 classes to make it all working nicely the recipes, grids, inventory, etc. When I find some time, I'll write an answer. –  Martijn Courteaux Jan 2 '12 at 0:18
add comment

5 Answers 5

up vote 12 down vote accepted

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:

Recipe Tree

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.

share|improve this answer
    
Very straightforward. I like it. –  David Eyk Dec 29 '11 at 23:51
    
I'll accept this one, because I like trees, hashes and diagrams that cut to the heart of the matter. One look at the diagram, and I understood your algorithm almost immediately. –  David Eyk Jan 2 '12 at 4:55
add comment

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.

share|improve this answer
1  
I wondered if the small number of recipes in Minecraft might not lend itself to a linear search. –  David Eyk Dec 28 '11 at 10:40
1  
It does, and is basically what I wrote above (with possible optimization of binary search). However that leaves a few options for crafting torches which you can fit basically anywhere. By first getting the size of the recipe you don't need to add 6 recipes for torches and you limit your search to only those of the correct size in one step. -- So basically the options for your point 2 are group by size, move the recipe to a corner or add more duplicate recipes. –  Kevin van der Velden Dec 28 '11 at 10:57
add comment

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
    }
}
share|improve this answer
3  
This is... very very smart. –  Raveline Dec 28 '11 at 13:47
14  
You have a problem and you want to solve it using regular expressions? Now you have 2 problems :) –  Krom Stern Dec 28 '11 at 14:13
2  
@Krom I figure you're probably just joking, but any reasoning behind that comment? Using a regular expression is just a concise (match grid against recipe with a single line of code) and flexible (fits all the requirements of this problem) way to perform matching on a set of data (the grid contents). I see no significant disadvantages over rolling your own matching algorithm, and it simplifies the whole process. –  David Gouveia Dec 28 '11 at 14:47
1  
@DavidGouveia, that's just a phrase for people who are not too comfortable with Regex. If they decide to solve a problem with regex, they now have two problems: (1) the actual problem they want to solve (2) writing the regex pattern to solve that problem –  iamserious Dec 28 '11 at 14:52
2  
Going back to the 'now you have two problems' - Regex will have problems as soon as you have more items than the ASCII printable range, unless your regex processor supports unicode and you can guarantee that certain combinations won't trip the regex NFA compiler up. You could throw together your own DFA (quite easily actually) to match patterns; but regex would be the best way to go while prototyping. –  Jonathan Dickinson Dec 29 '11 at 13:57
show 12 more comments

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.

share|improve this answer
    
The Bukkit repository doesn't have any Minecraft code, you'd need MCP (and a copy of Minecraft) –  BlueRaja - Danny Pflughoeft Dec 28 '11 at 18:44
    
Isn't this just the inverse of your other answer? –  David Eyk Dec 29 '11 at 23:56
    
@DavidEyk (This is my first answer) not really, it is more dependant on a hashmap structure (whether it is bigtable-like or in-memory). The reason I answered again is because I was worried about hash collisions leading to poor performance - at least in a in-memory hashmap. My other answer would work better for more items and an in-memory structure - where this would work better if it was in SQL/etc. –  Jonathan Dickinson Dec 30 '11 at 8:52
add comment

Here is how I did it in Block Story:

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.