Efficiently finding the largest surrounding square in 2D grid

Question

In a game with a 2D grid map I'm facing the following situation:

I need to find the largest bounding square that surrounds the player position (the red dot). Or at least a bounding square of maximum size, as there could be more. Note: square, not rectangle.

In this case, it's fairly easy to see the largest square is 8x8:

If I add an obstacle in the map, the largest possibility is now 5x5:

I am looking for a fast and efficient way of finding the (or a) maximum square that contains the player position.

What I'm currently doing is kind of brute force:

• A 1x1 square is always possible (the player position itself).
• Then I try all possible 2*2 squares containing the player, that's 4 possible different squares, and for each I do a 2*2 loop, checking if all grid cells are clear (not walls or obstacles).
• If a 2*2 square is possible, then I try all possible 3*3 squares surrounding the player (that's 9 different squares) and for each I do a 3*3 loop, to check if there's no collission.
• Et cetera, until for size N*N no square is possible.

It works, it's very straightforward, but it feels very inefficient. Obviously I'm doing a lot of redundant checks here, and I'm wondering if there is a smarter / faster way to do this. Does anyone know of an algorithm to do this efficiently?

(edit) Important addition: besides the player moving around, obstacles or walls are dynamically added or moved, so caching or precalc optimizations are somewhat hard to implement here.

Answer 1

I think you can probably improve your algorithm by, at each stage, just checking on the valid boundaries of your existing 'largest square'. It is probably easier to explain this diagrammatically...but basically. All you should do is

 **Growth Algorithm**
 repeat
   search the bounding sub-squares on the valid sides of the largest valid square found so far
   increase size of square on 'valid' sides and mark newly blocked sides as invalid
 until all sides invalid

 then check if largest valid square can be translated 1 unit diagonally in any of 4 directions
 if so repeat the growth algorithm on each new square until none get bigger

By this means you should only need to test each sub-square of the final valid square once only. So a n^2 process if square is n on its side. IO don';t think you can do better as you do need to check each sub-square for validity.

Answer 2

Use a variation on this: Maximum size square sub-matrix with all 1s.

Algorithm:

Scan up, down, left and right only from the dot to generate the bounds for the 
solution matrix S, not more than 20 in each direction (that's my contribution... :)

Copy the first row and first column (within the bounds of S) from M[][] to S[][], switching 
zeros for ones and ones for zeros.

For the remaining entries (i=1 to length S, j=1 to length S) do:

If M[i][j] is 0 then
   S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
   If S[i][j] is within distance of dot
      Best = max(S[i][j], Best)
Else
   S[i][j] = 0

Answer 3

I think a video worth a thousand images. Algorithm demonstration.

In the video you can see how this algorithm find surrounding squares, unfurtunately I didn't paint the whole process It paints only good matches but I think you'll find interesting and you can notice the whole process only watching the good matches.

You can run the example of the video by yourself with processing 3, I put the whole code in this gist.

The most relevant code (written in python) is this

def checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):
    return areaX1 < 0 or areaY1 < 0 or areaX2 >= gridSize or areaY2 >= gridSize

def isAreaCompatible(type, oldAreaX1, oldAreaY1, oldAreaX2, oldAreaY2, areaX1, areaY1, areaX2, areaY2):
    global grid
    for y in range(areaY1, areaY2+1):
        for x in range(areaX1, areaX2+1):
            print "checking point (%s,%s) old area is (%s,%s) (%s,%s) new area is (%s,%s) (%s,%s)" % (x,y,oldAreaX1, oldAreaY1, oldAreaX2, oldAreaY2, areaX1,areaY1,areaX2,areaY2)    
            if x >= oldAreaX1 and x <= oldAreaX2 and y >= oldAreaY1 and y <= oldAreaY2: 
                print "This area belongs to previous area, won't check"
            else:         
                if grid[y][x].type != type: print "false"; print "This area have a different color/type so it's not compatible"; return False;
    return True;

def explore(type, x1, y1, x2, y2):
    #Right and bottom
    print "----- Right and bottom ------"
    areaX1 = x1;
    areaY1 = y1;
    areaX2 = x2+1;
    areaY2 = y2+1;
    if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):
        if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):      
            addAnim(areaX1, areaY1, areaX2, areaY2);
            addMatch(areaX1, areaY1, areaX2, areaY2);
            explore(type, areaX1, areaY1, areaX2, areaY2);

    #Bottom and left    
    print "----- Bottom and left ------"
    areaX1 = x1-1;
    areaY1 = y1;
    areaX2 = x2;
    areaY2 = y2+1;
    if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2): 
        if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):
            addAnim(areaX1, areaY1, areaX2, areaY2);
            addMatch(areaX1, areaY1, areaX2, areaY2);
            explore(type, areaX1, areaY1, areaX2, areaY2);

    #Left and top
    print "----- Left and top ------"
    areaX1 = x1-1;
    areaY1 = y1-1;
    areaX2 = x2;
    areaY2 = y2;
    if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):     
        if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):
            addAnim(areaX1, areaY1, areaX2, areaY2);
            addMatch(areaX1, areaY1, areaX2, areaY2);
            explore(type, areaX1, areaY1, areaX2, areaY2);

    #Top and right
    print "----- Top and right ------"
    areaX1 = x1;
    areaY1 = y1-1;
    areaX2 = x2+1;
    areaY2 = y2;
    if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):     
        if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):
            addAnim(areaX1, areaY1, areaX2, areaY2);
            addMatch(areaX1, areaY1, areaX2, areaY2);
            explore(type, areaX1, areaY1, areaX2, areaY2);

Answer 4

Here's a completely different approach:

You hold a a 2d matrix of size [Length, 2] Length being the size of your map (I'm assuming symmetric width / height, but if not just pick an axis). I'll call the 1st rank (Length) column (you could rotate the entire algorithm 90 degrees and call this row). Each column holds 2 values - Min Position & Max Position of valid range in the column.

You fill this matrix with the following algorithm:

Start with the dot column, find & store the min & max position of the contiguous range above & below the dot. If dot is at x,y:

int colMin, colMax;
for(colMin = y; colMin > 0;) {
   if(Matrix[x, colMin - 1].IsValid)
       colMin--;
   else break;
}
for(colMax = y; colMax < maxHeight;) {
   if(Matrix[x, colMax + 1].IsValid)
       colMax++;
   else break;
}
MinMaxValid[x, 0] = colMin;
MinMaxValid[x, 1] = colMax;

You proceed in both directions independently with the following algorithm:

int minCol = 0, maxCol = maxWidth; // These hold the min/max range of valid columns
for(int col = x - 1; col >= 0; col--) {
   for(colMin = y; colMin > MinMaxValid[col + 1, 0];) { // Cell is only valid if it overlaps to the next range
      if(Matrix[col, colMin - 1].IsValid)
          colMin--;
      else break;
   }
   for(colMax = y; colMax < MinMaxValid[col + 1, 1];) { // Cell is only valid if it overlaps to the next range
      if(Matrix[col, colMax + 1].IsValid)
          colMax++;
      else break;
   }
   if((colMax - colMin) >= (x - col)) { // if the found range is smaller than the distance for x, it can't be a part of the square
      MinMaxValid[col, 0] = colMin;
      MinMaxValid[col, 1] = colMax;
   }
   else {
      minCol = col + 1; 
      break; // We're done on this side
   }
}

for(int col = x + 1; col < maxWidth; col++) {
   for(colMin = y; colMin > MinMaxValid[col - 1, 0];) { // Cell is only valid if it overlaps to the previous range
      if(Matrix[col, colMin - 1].IsValid)
          colMin--;
      else break;
   }
   for(colMax = y; colMax < MinMaxValid[col - 1, 1];) { // Cell is only valid if it overlaps to the previous range
      if(Matrix[col, colMax + 1].IsValid)
          colMax++;
      else break;
   }
   if((colMax - colMin) >= (col - x)) { // if the found range is smaller than the distance for x, it can't be a part of the square
      MinMaxValid[col, 0] = colMin;
      MinMaxValid[col, 1] = colMax;
   }
   else {
      maxCol = col - 1;
      break; // We're done on this side
   }
}

You now have your MinMaxValid filled. The next part is to run over the rows and find the largest square:

int maxSquareSize = 0, maxSquareCol = minCol;
for(int col = minCol; (MinMaxValid[col, 1] - MinMaxValid[col, 0]) >= (maxCol - col); col++) {
   for(int squareSize = MinMaxValid[col, 1] - MinMaxValid[col, 0] + 1; squareSize > maxSquareSize; squareSize--) {
      if((Min(MinMaxValid[col, 1], MinMaxValid[col + squareSize - 1, 1]) - Max(MinMaxValid[col, 0], MinMaxValid[col + squareSize - 1, 0])) >= (squareSize) {
         maxSquareSize = squareSize;
         maxSquareCol = col;
         break;
      }
   }
}

The last part works like this:

Any column can participate in a square only as large as it's height. In order to do so, the union of the current column range, and the range at col + squareSize - 1 must be at least squareSize tall.

Now comes the best part! Whenever the scene changes (A square becomes invalid, the dot moves, etc...) you can only invalidate a certain range of your MinMaxValid matrix and re-evaluate as necessary. I didn't include this logic as this answer is long enough, but that's the easy part (Basically, you reduce the column range to fit the new scenario, and rescan both directions again).

I must say I haven't tried this one out, but even if it doesn't work (And please let me know so I could remove this comment :-), it's got to be close to a valid solution.