2d - Identifying quad patterns in a two-dimensional array

In the tech demo I'm trying to make, tetrominoe-style blocks will be placed by the player, at which point the game checks to see if they've made a quad with any existing shapes on the board (a 2D array). If so, the quad should be processed in some way.

I have a 2D array like so:

[ [0, 0, 0, 1, 1, 1],
  [0, 1, 1, 1, 1, 1],
  [1, 0, 0, 1, 1, 1],
  [1, 0, 0, 1, 0, 1] ]

And I need to identify 'quad' patterns such as that in the top-right corner, e.g.

[ [1, 1, 1],
  [1, 1, 1],
  [1, 1, 1] ]

I'm not sure of the best way to do this. I've had a look at some two-dimensional array pattern matching algorithms, which all seem to flatten the 2D array into 1D, then use a 1D text searching algorithm (e.g. KMP) to identify any matches. My problems with that idea are that the quad can be any size, as long as it's rectangular and bigger than an arbitrary minimum (in my case, 2 x 2).

I also thought about using some variant of the 4 way flood fill algorithm or connected-component labelling, for each position of the newly-place tetrominoe. But I'm not quite sure how to best follow the path out and establish the bounds of a quad (for example, capturing this:

[ [1, 1, 1],
  [1, 1, 1],

  [1, 1, 1] ]

out of this:

[ [1, 1, 1, 1],
  [1, 1, 1, 0],
  [1, 1, 1, 0] ]

My latest though is perhaps a floodfill to get all interconnected parts after a tetrominoe lands, then 'round off' the jagged edges, maybe by checking the number of neighbours of each block, if it's 1, remove it, repeating the process until all remaining blocks have 2 or more neighbours. But this seems like it could be slow.

Has anyone any experience of this problem, or any pointers about how best to accomplish this task? I'm sure there's a common or at least applicable algorithm, I just don't know it!

Answer

I drew it.

• Coloured backgrounds are the layout of filled squares just after a block has been placed.


• Red circles are locations that could potentially be the top-left corner of a quad.


• Red lines are on squares around a potential corner that must be filled for the shape to be a quad.


• Red crosses are locations that were checked and found to be empty. (In the last two diagrams, I've connected them to the red circle from which the check was made.)

In the first diagram (green), things worked out fantastically. The very first top-left corner we checked has filled squares on its bottom-right outline that form a 2x2 block. If we try to be even more ambitious and form a 3x3 block, we find that some of those (the red crosses) are not filled. So all we got is a 2x2.

In the second diagram (blue), things worked out easily also. Except this time, even the second bottom-right outline matched on all squares: We have a 3x3 block. Trying for a 4x4 fails, as not all squares are filled.

In the third diagram (purple), we've got nothing. We ran out of filled squares to place the corner in before we found one that has a bottom-right outline.

In the fourth diagram (yellow), things worked after some trying. The first three squares we tried to place corners in had no bottom-right outline. The fourth, however, did. This gives us a 2x2. Trying to get a 3x3 fails as in the first diagram.

If your corner is grid[0][0], the nth bottom-right outline consists of squares where one or both coordinates are n.

This generalises to: If your corner is at grid[x][y], then the bottom-right outline is a union of these sets of squares:

• grid[x+n][yVariable], where y <= yVariable < y+n (the right side)



• grid[xVariable][y+n], where x <= xVariable < x+n (the bottom side)


• and finally grid[x+n][y+n] (the bottom-right corner)

It should be easy to iterate through these. If you have a quad, the top-right and bottom-right corners' coordinates tell you where it is.

That only works for squares though!

Those three bullet points above can also be checked for individually:

This of course means that from any state of checking, 3 (instead of 1) possible further states may evolve:

Each of these three states can each be further expanded into up to three states by a similar method.

Your code could save the two other states for later and process the first to exhaustion before continuing with the next. At the end, the quad with the largest area would be the output. (This is, in computer science terms, a depth-first traversal of a trinary tree.)