# What algorithm can I use to detect simple shapes in a 4x4 matrix?

I'm working on a simple multiplayer game that receives a random 4x4 matrix from a server and extracts a shape from it.

For example:

``````XXOO       OXOO
XXOX       XXOO
XOOX  and  XOOO
XXXX       OXXX
``````

So in the first matrix the shape I want to parse is:

``````  oo
o
oo
``````

and the 2nd:

``````  oo
oo
ooo
``````

I know there must be an algorithm for this because I saw this kind of behavior on some puzzle games but I have no idea how to go about to detecting them or even where to start.

So my question is: How do I detect what shape is in the matrix and how do I differentiate between multiple colors? (it doesn't come only in `X` and `O`, it comes in a maximum of 4). Additionally, the shape must be a minimum of 4 blocks.

-
Even though it's posed differently this is EXACTLY the same problem as this: gamedev.stackexchange.com/q/21586/1494 – Jonathan Dickinson May 11 '12 at 8:22
What should happen with OO__ OO__ __OO __OO? Do you want to find two shapes? Or is the shape considered valid because it's made of two valid shapes? – sam hocevar May 11 '12 at 9:01
As an optics guy, I just have to: 2D Fourier transform. Muahah. – David Lively Jul 19 '12 at 5:11

What data type is the matrix? If its all stuffed into a single int for example and represented with bits then you could just check masks like so

``````ooxo
oxxo
xxxx
oooo
``````

would equal

``````0010011011110000
``````

which you could then store in an enum, a #define or what have you and use the simple

``````if(inValue & MaskNumber1 == MaskNumber1) { // we have a perfect match }
``````

Since they are also integers you could use a switch statement if you wanted as well (assuming the patterns are exclusive of each other).

If this is not a matrix of Off and On values then let me know and I will try and update my answer.

Hope this helps.

-
the matrix itself it's an array of integers but they range from 0 to 3 (4 values) your idea is great but an algorithm would be better for this situation because of all the permutations possible (there are literally thousandths of possibilities and if i decide to upgrade the game to a 5x5 or higher the nr will grow exponentially) – ion Apr 10 '12 at 23:48
wait a min ..i just realized...there are actually 5 values (counting the 0) – ion Apr 10 '12 at 23:49
@ion are the 'valid' shapes unlimited in variation and only limited by the size? and if there is no difference between a shape made up of a single color or multiple colors, at least as far as detection of the shape goes, I would still suggest simplifying it down to an off/on pattern for the detection. You can also always extend the size you want to go simply by adding in another integer to hold more bits (integers are just bit arrays of a set size is all). As long as the valid 'detectable' combinations are limited I would go with something like above for speed/maintainability. – James Apr 10 '12 at 23:54
well the thing is that i was planning to add multiple shapes in a single matrix and then run the algorithm for each color separately, and if i detect a valid shape i take it from there – ion Apr 10 '12 at 23:59
@Ion Wish we could chat but since we can not, my suggestion for the algorithm then is to loop through the matrix for each color building up a bit mask as above in the answer for that color and compare it against a list of known shapes (if the list is long a switch statement will help with speed and also let you map multiple masks to the same shape (a square in any corner for example is still a square maybe). With out knowing more exactly what you are doing I do not think I can give any more insight on this topic and will just remove my answer. Let me know. – James Apr 11 '12 at 0:18

You can use a slightly modified version of a depth first search algorithm to extract connected shapes of items with same color.

If you have a matrix of size 4x4 with items, you need to have additional matrix of the same size with boolean flags stating that given item with (x,y) coordinates was traversed or not.

Then, you may construct a recursive function to extract connected items, given with a description:

``````function traverse(item, currentShape)
mark item as traversed
for each N,E,W,S neighboring item
if neighboring item with the same color
if neighboring item not traversed
traverse(neighboringItem, currentShape)
``````

Using a particular order of scanning elements from items matrix (eg. from left to right and from top to bottom) call this function on every non-traversed item and in return, you'll be given an list of items connected to the starting one. There may be many lists of such kind, from whose you can choose ones that have length of 4 or more.

-

A single 32 bit integer can store all the data. 00,01,10,11. You could even set up some macros so you can use strings for visuals just with bit shifts orred together You can #define each shape and use a switch, case for all of the masks.

``````#include <stdio.h>
#define shapeit(s) ( ( s[0]-'0' )|( s[1]-'0'<<2 )|( s[2]-'0'<<4 )|\
( s[3]-'0'<<6 )|( s[4]-'0'<<8 )|( s[5]-'0'<<10 )|( s[6]-'0'<<12 )|\
( s[7]-'0'<<14 )|( s[8]-'0'<<16 )|( s[9]-'0'<<18 )|( s[10]-'0'<<20 )|\
( s[11]-'0'<<22 )|( s[12]-'0'<<24 )|( s[13]-'0'<<26 )|( s[14]-'0'<<28 )|\
( s[15]-'0'<<30 ) )

/* acceptable values in shape strings are 0123 */
#define LSHAPE shapeit( \
(   "1000" \
"1000" \
"1000" \
"1111" ))
``````

which gives this binary representation 1010101000000010000000100000001 of the integer 1426129153 (thus the macros - it would be painful to read otherwise)

since you now have each shape defined as an integer it is possible to use a switch, case to check an unlimited amount of shapes simultaneously (you can change to `long long` instead of `int` later to get larger shapes, but you will need to cast each one in the macro , so it may be easier to just say that an 8x8 is 4 4x4s - maybe only use long long for adding more colors or other "attributes") One big advantage is that since all of the predefined shapes are calculated by the preprocessor into `const int` prior to compiling, a lot of code can be optimized and each incoming shape would only need to be converted to integer and compared ... typically optimizing to a jump table for larger data sets on a switch case

-