高效地在2D网格中找到最大的周围正方形

Question

在一个2D网格地图游戏中，我面临以下情况：

我需要找到围绕玩家位置（红点）的最大边界正方形，或者至少是最大尺寸的一个边界正方形，因为可能会有更多。注意：是正方形而非长方形。

在这种情况下，很容易看出最大的正方形是8x8。

如果我在地图上添加障碍，那么最大的可能性现在是5x5。

我正在寻找一种快速有效的方法来找到包含玩家位置的（或一个）最大正方形。

我目前正在做的是一种暴力算法：

- 一个1x1的正方形总是可行的（即玩家位置本身）。 - 然后，我尝试包含玩家的所有可能的2*2正方形，这是4个不同的可能的正方形，并针对每个正方形进行2*2的循环，检查所有网格单元是否都是清除的（不是墙或障碍）。 - 如果2*2正方形是可能的，则我尝试围绕玩家的所有可能的3*3正方形（共9个不同的正方形），并对每个正方形执行3*3循环，以检查是否存在冲突。 - 依此类推，直到对于大小N*N没有正方形是可能的为止。

它可以工作，非常直观，但感觉非常低效。显然，在这里我做了很多冗余检查，我想知道是否有更聪明/更快的方法来做到这一点。是否有人知道一种高效的算法来实现这一点？

（编辑）重要补充：除了玩家移动外，“障碍物或墙壁是动态添加或移动的”，因此缓存或预计算优化在这里有些难以实现。

- RocketNuts

---

有很多事情可以做，但是根据您的网格的最大尺寸，由于大量初始化开销，大多数优化可能会效率低下。是否有预定义的最大尺寸？ - Amit

@Amit 嗯，网格可以是横向和纵向的许多个单位，但我注意到在实践中，最大可能的正方形很少超过10，从未超过20。我会说，对于最大可能的正方形，我得到的最常见尺寸通常为3-6。 - RocketNuts

@Amit，既然你提到了“初始化”，我添加了一条关于地图有点动态的注释。我曾经考虑过预先计算各种边界框信息，但由于地图不是固定的，所以这并不适用。 - RocketNuts

你能否发布一些代码展示矩阵是如何存储的？ - גלעד ברקן

@גלעדברקן 这只是一个具有固定宽度和高度的 int 数组映射[]（我正在使用 C++，但希望保持这个主题的语言无关性）。有不同种类的障碍和方块，但基本上 0 = 空，非零 = 墙或者障碍物。 - RocketNuts

@RocketNuts 我的解决方案对处理动态地图应该非常有效，因为只有在地图发生变化时才需要进行部分计算。 - Amit

Answer 1

我认为你可以通过仅检查现有“最大正方形”的有效边界来改进算法。可能更容易通过图解来解释这个概念...但基本上，你应该做的是

 **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

通过这种方式，您只需要对最终有效方块的每个子正方形进行一次测试。因此，如果正方形边长为n，则为n^2的过程。我不认为您可以做得更好，因为您确实需要检查每个子正方形的有效性。

- Penguino

---

非常感谢您的思考和清晰的图表！实际上，我一直在考虑类似的“成长边缘”方法。但问题是：验证或阻止我的正方形边缘的顺序或优先级（从而决定我仍然可以扩展的方向）会产生差异。[1/2] - RocketNuts

例如，如果您看我的第三张图中的情况（有障碍物），如果我扩展所有边缘，我会先发现一个被阻止的左边缘，然后是上边缘（与你迄今为止的过程相同），之后右边和下边缘都被障碍物阻挡了，所以我最终会得到一个44的正方形。而正确答案是55（用蓝色表示，通过向左/向上扩展3个单位并向右/向上扩展1个单位获得）。[2/5] - RocketNuts

@RocketNuts 是的，我现在看到问题了。我没有时间详细查看，但可能当你最终在所有方向上都被阻塞时（这将在你的示例中的第三个图中出现额外的正方形），你可以添加一步，在其中查看“阻塞”的最大正方形是否可以沿着任意4个方向对角线滑动（不“失去”你的起始点）-如果可以，你将在每个方向上重复算法，以查看它是否可以进一步扩展。这将在你的第三个图中起作用（成本最小），但我不能确认它是否在所有情况下都有效。 - Penguino

@RocketNuts 我以一种比较模糊的方式更新了算法描述。 - Penguino

我想对这种方法补充一点：不要检查每个循环中的所有边缘，而是只检查每个循环中的两个边缘（上和左、上和右、下和右、下和左）。这样工作可以让你检查每个循环中仅增加1个单位的正方形，而如果你检查所有边缘，你可能会得到一个大小为n+2而不是n+1的正方形。从复杂度的角度来看，这似乎更好，但实现起来需要更多的努力（更多的有效性检查等）。使用每个单位增长1个单位的正方形也允许进行更细粒度的检查。如果有不清楚的地方，请告诉我。 - Gentian Kasa

Answer 2

我认为一段视频胜过千言万语的图片。算法演示。

在这个视频中，你可以看到这个算法如何找到周围的正方形，不幸的是，我没有展示整个过程，只展示了好的匹配情况，但我认为你会发现它很有趣，而且你可以通过观察好的匹配情况来注意到整个过程。

你可以使用Processing 3自己运行视频示例，我将整个代码放在此Gist中。

最相关的代码（用Python编写）如下：

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);

- ZooMMX

Answer 3

请使用这种变体：全为1的最大正方形子矩阵。

算法：

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

- גלעד ברקן

---

有趣的是，是的，方块只能在四个对角线方向上扩展。我在第一时间就遇到的问题是，每进行一次迭代，就会出现4种新的变化。如果我递归执行这个过程，数字将会变得非常庞大。但是有很多重复的情况：不同的对角线步骤顺序实际上会导致相同的方块，因此也许有一个聪明的方法来跳过重复的情况。 - RocketNuts

嗯，是的，增长可以在任何4个对角方向上发生，但最终结果是一个正方形，从玩家位置开始向上、向右、向下和向左方向扩展特定数量的单位。我只需要记住在4个直线方向上扩展的单位数，以确定我已经拥有哪些可能性。我会再仔细考虑一下这个问题！ - RocketNuts

Answer 4

这里有一个完全不同的方法：

你拥有一个大小为[Length，2]的二维矩阵，其中Length是地图的大小（我假设宽度/高度对称，但如果不是，请选择一个轴）。 我将称第一级（长度）列（您可以将整个算法旋转90度并称其为行）。 每列包含2个值-列中有效范围的最小位置和最大位置。

您可以使用以下算法填充此矩阵：

从点列开始，查找并存储点上方和下方连续范围的最小和最大位置。 如果点位于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;

你可以使用以下算法独立地进行双向处理：

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
   }
}

现在您已经填好了MinMaxValid。下一步是遍历行并找到最大的正方形：

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;
      }
   }
}

最后一部分的工作方式如下：

任何列只能参与高度不超过其本身高度的正方形。为了做到这一点，当前列范围和 col + squareSize - 1 处的范围的并集必须至少有 squareSize 的高度。

现在来到最好的部分！每当场景发生变化（一个正方形变得无效，点移动等等...），你只能使你的 MinMaxValid 矩阵中的某个范围无效，并根据需要重新评估。我没有包含这个逻辑，因为这个答案已经够长了，但这是容易的部分（基本上，你缩小列范围以适应新情况，然后再次扫描两个方向）。

我必须说我还没有尝试过这个方法，但即使它不起作用（请让我知道，这样我就可以删除这个评论 :-），它也肯定接近一个有效的解决方案。

- Amit

---

非常感谢你的详细回答，Amit。我还没有完全理解它的内容，我会进一步分析并告诉你！ - RocketNuts