title: Efficiently finding the largest surrounding square in 2D grid
body: <p>In a game with a 2D grid map I'm facing the following situation:</p>
  
  <p><img src="https://i.stack.imgur.com/whMZP.png" alt="enter image description here"></p>
  
  <p>I need to find the <strong>largest bounding square</strong> that surrounds the player position (the red dot). Or at least <em>a</em> bounding square of maximum size, as there could be more. Note: <em>square</em>, not rectangle.</p>
  
  <p>In this case, it's fairly easy to see the largest square is 8x8:</p>
  
  <p><img src="https://i.stack.imgur.com/gRYc8.png" alt="enter image description here"></p>
  
  <p>If I add an obstacle in the map, the largest possibility is now 5x5:</p>
  
  <p><img src="https://i.stack.imgur.com/RRYD5.png" alt="enter image description here"></p>
  
  <p>I am looking for a <strong>fast and efficient</strong> way of finding the (or a) maximum square that contains the player position.</p>
  
  <p>What I'm currently doing is kind of brute force:</p>
  
  <ul>
  <li>A 1x1 square is always possible (the player position itself).</li>
  <li>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).</li>
  <li>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.</li>
  <li>Et cetera, until for size N*N no square is possible.</li>
  </ul>
  
  <p>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?</p>
  
  <p>(edit) Important addition: besides the player moving around, <strong>obstacles or walls are dynamically added or moved</strong>, so caching or precalc optimizations are somewhat hard to implement here.</p>