Algorithm for Finding Shapes on a Grid

Questions & Answers
1

Hey guys,

I'm working on a problem that is similar to the "inventory tetris" idea where you have an x by y grid upon which you have differently shaped inventory items. Like this: http://gangles.ca/images/screenshots/InventoryTetris_Title2.png

The problem I'm having is that, while the player is dragging an object, I'd like to highlight groups of grid cells that are the right size for the object to fit. So, if the player is dragging an L-shaped gun or something, all the L-shaped areas on the grid matching the object's orientation would light up so it is obvious where the object can be placed.

I'm having a lot of trouble figuring out what sort of algorithm I can use to achieve this. I imagine I might be able to use a depth-first search to find the different available areas. But I'm really unsure how I could detect if the area has the correct shape for whatever is being dragged.

I feel like this is the sort of problem that has been solved before, but I'm having trouble identifying existing algorithms that will be helpful. Does anyone have any leads on an algorithm or procedure that would help out with this?

2

Thought I’d get back and mention how I was able to solve this issue.

First off, I converted the rigidbody’s colliders into a 2D array of 1s and 0s. For example, an L shaped object would have this array:

100
100
111

I did this by using the minimum collision bounds of the object as the origin for a coordinate system, and then converting the min/max points of each contained collider to that coordinate system. This would give me something like “bounds.min = 0,0” and “bounds.max = 2, 0” - from there, I could fill in all intervening spaces with 1s.

After this, I also kept track of whether grid spaces were occupied using a 1 and 0 system. From there, it was a simple matter of iterating over the grid and seeing if the shape’s array would fit anywhere in the larger grid. If any 1s overlapped, the position was invalid.