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