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

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

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.