Plankton has gotten really close to figuring out how to make a crabby patty. But no matter how hard he tries, he still can't figure out the ingredients for that bread + lettuce + tomato + patty sandwich.
So how did Block Story succeed where Plankton failed? How does the game know that when you combine certain items in some order and quantity you get the crabby patty?
You have a grid 2x2 or 3x3 (or any arbitrary grid size for that matter). You have potentially hundreds of recipes, each one with 1 to 9 items in any quantity. For example:
When the user enters ingredients, the goal is to recognize that his ingredients match one of the recipes and can produce some output.
Notice we would like to make it so that if the ingredients are in the first, second or last column, it still matches.
We would also like to make it so that if the user puts 10 of each ingreadients, it still matches, produces 1 crabby patty, and then he is left with 9 of each ingredients.
Another thing to watch out for: it could be possible to have more than 1 recipe matching the user input. So the recipes should be designed carefuly so that they are never ambiguous
The naive approach, would be: every time the table changes contents, look at each recipe and see if it matches. Notice if you have say 500 recipes, this could actually take some time. There also remains the issue of dealing with alignment problems (having the ingredients in any column). Checking one by one would require comparing each recipe and for each recipe, comparing all cells, so its performance is O(n*s) where n is the amount of recipes, and s is the size of the grid.
If you think this is a reasonable approach. Then what the heck are you doing building a block engine? just quit right now and come back in a few years.
Solving the Alignment problem
The alignment problem is easy to solve. When reading a recipe, only store columns and rows that have something, throw away all empty columns and rows. For example, Plankton would only have to remember this:
Meaning, he only has to remember that 1 column with bread, patty and bread produces a crabby patty, and forget that this is for 3x3 or 10x10 grid.
When matching the user input, he can do the same process: eliminate all empty columns and rows. So if the user enters any one of these:
The result will be exactly the same:
Now we compare the results with the recipes. This solves the alignment problem for all recipes regardless of grid size. But I have still not touched on making it efficient.
Matching recipes efficiently
I don't do it exactly like this, but this is a convenient way to explain the algorithm. For both the recipe and the user input, you can encode it as a string, like this:
Which means the recipe is 1 column by 3 rows, and it has from left to right top to bottom Bread, Patty and Bread.
You can build an entire table from these strings with all the recipes. For example:
|1x3BPB||1 crabby patty||1 column 3 rows recipe for crabby patty|
|1x1R||3 red dyes||just 1 cell with 1 ruby ore produces 3 red ores|
1 rows with 3 wood,
Now, when the user puts something in the crafting table, encode what he enters into a string using the same algorithm, and then it is just a matter of looking up the string in this table.
The simplest way to do this, is to store that table in a Dictionary or Hash table, then the lookup can be done in O(1), meaning it does not matter how many recipes there are.
So the algorithm is:
- At game startup,
- eliminate all empty rows and columns from all recipes
- encode each recipe into a string
- put all encoded recipes into a hash table indexed by the encoded string
- When the user puts something in the crafting table
- eliminate all empty rows and columns from the input
- encode the result into a string
- lookup that string in the recipe hash table
- if matches, then show the output for that recipe
At game startup, the algorithm performs O(n*s) which is fine because it is done only once while the user enjoys our cool loading screen.
When the user enters something, the algorithm does the matching in O(s) where s is the size of the grid.