Determine inventory item position shape

Question

Not a great title but couldnt think of a shorter way to describe it.

I am trying to think of the best way to determine the shape of items placed in the players inventory. I guess the best examples to explain would be something like the Horadric Cube in Diablo 2 or I suppose also, the Workbench in Minecraft. There are others, I just can't remember them.

Currently the best way I can think of involves multiplying the cell numbers each item is in. This way I can look at the product of that multiplication and know from a short list of values, what shape the items are in.

Example

My inventory is ordered like so:

1 | 2 | 3
4 | 5 | 6
7 | 8 | 9

I would also have various arrays of preset values like:

FourSquares - 40, 180, ..., ...
VLines - 28, 80, ...
HLines - 6, 120, ...
Backslash - 45
Forwardslash - 105

etc, etc

So, say the user places items in 1, 2, 4 and 5 - That would give 40 and I could loop through each shape array and determine that it matched a value in the FourSquares array and go from there.

Does this seem like the best way to do it? Is there maybe a way that I wouldnt have to loop through the arrays? Would this be possible with bitwise operations maybe?

Answer 1

The product will Not work for this as there are too many collisions (different shapes with the same product). For example, 1 2 4 and 5 == 40, but so does 2 4 5 and 5 8. A number on its own and then the 1 position would also be mathematically the same.

You can use something like what minecraft does and just do a string comparison for patterns that must have matches or character counting for the ones that are shapeless (there is just a boolean that marks a pattern as shapeless or not). The values used in the strings are up for you to decide but here is just a quick example, again using minecraft recipes as a basis.

The stone pick axe recipe. "SSS s s " - This makes a T shape when displayed with 3 characters per row. The S represents stone the 's' represents a stick (this association is also set up within the recipe when it is made). When displayed in the 3x3 grid the 'S' would be across the top with the next two rows containing a space, a 's' and then another space so the handle goes down the middle.

If you wanted to get more tricky you could represent the layouts as bitmasks and then just scan for patterns that way but you would potentially lose the 'What type of material' is there and be reduced to just pattern recognition. This seems to be ok with what you were doing however so I figured I would include it.

Hope this helps.

Answer 2

Multiplying their positions seems like an interesting approach but I am skeptical of it's ability to work in every case you'd want. There are, usually, many ways to multiply numbers to reach a common result which would give false positives (or surprisingly incorrect recipes). For example, 6 * 2 = 4 * 3 = 12, 8 * 5 = 4 * 2 * 5 = 40, etc.

I think it depends on exactly what you need to match.

If any types items can be in any orientation, just making a specific shape, you can treat each block as a boolean value (true if something is in the slot, false if not) and write an algorithm to verify true/false values for the shapes you're looking for. (I can expand on this if you have specific shapes you'd want help identifying.)

If you need specific items to be in a particular shape regardless of which item is where (like 3 wood and 1 stone in a square), you can use the above to verify the shape, then check the contents against the required types of objects. For example, if you've verified you have a square, check the contents, find you have 3 wood and 1 stone in the inventory, then you have a match.

If you need specific items in specific orientation, it's probably best to just maintain a list of usable recipes and verify them each in turn. If you need wood | stone | wood across the top row, check against a master recipe list that includes wood | stone | wood across the top row one cell at a time (also verifying the other cells are empty) and find you have a match.

Answer 3

Here's an idea. You could store your inventory as a bool array from 0 to 8 (9 spaces total). Step through each n element, and if it's true add 2^n or 1<<n to a running total. At the end, you'll have a unique number for every possible shape, as each spot is represented by its own bit.

So a square (all positions occupied but the center) would end up being:

2^0  + 2^1  + 2^2  + 2^3  + 2^5  + 2^6  + 2^7  + 2^8

or

1<<0 + 1<<1 + 1<<2 + 1<<3 + 1<<5 + 1<<6 + 1<<7 + 1<<8

which ends up being

1    + 2    + 4    + 8    + 32   + 64   + 128  + 256

and has its own unique identifier of 495 with a binary representation of 0000000111101111 as an unsigned 16-bit integer. Then it's just a matter of cataloging every shape you want and it's value.

If you want the shapes to be able to be anywhere in the grid, then it gets a bit harder. You'll likely have to write a special-case to check for each shape.

For instance, in this array, to check for four squares (which I'm interpreting as 4 items in a square pattern), then you would check if the first item is NOT in positions 2 or 5 (as these sit on the right edge and cannot then have an item to their right), and not in 6, 7 or 8, the bottom row, (as there couldn't be any items below them). Then you would check if n+1 (item to the right), n+3 (item below), and n+4 (to the right and below) exist.