在二维阵列中寻找合适的切割片

Question

好吧，标题不太合适，请继续阅读（我无法获得更好的）。

注意：使用Python 2.7，但算法也会有所帮助。

我正在制作侧卷轴游戏，其中我在飞行中产生障碍物。我遇到的麻烦是弄清楚如何产生障碍。 o_O
我有一种某种逻辑，但后来在计算整个逻辑时遇到了麻烦。

因此，这里是从实现的角度来看我的问题：
我有一个Surface，其中我已经把一些Element s，这是所有的矩形。
认为它像：

0 0 0 0 0 0 0 
0 0 0 0 1 1 0 
0 0 0 0 1 1 0 
0 0 0 0 1 1 0 
0 0 0 0 0 0 0 
0 1 1 0 0 1 1 
0 0 0 0 0 1 1 

如在上述结构中，我怎样才能确定是否可以在不重叠的（1S）的另一个矩形被添加一个axb矩形，并且其中所有。此外，与所有其他对象保持x个元素（甚至对角线）的距离，这意味着整个矩形是（x + 3，x + 4）。就像如果x=1, a=3, b=4东西，只有一个可能的安排：
（2S代表了新的对象）

2 2 2 0 0 0 0 
2 2 2 0 1 1 0 
2 2 2 0 1 1 0 
2 2 2 0 1 1 0 
0 0 0 0 0 0 0 
0 1 1 0 0 1 1 
0 0 0 0 0 1 1 

基本上，我需要找到所有的点，从侧面a和b的矩形可以有它，说，左上角。这是如何实现的？

注意：打开更好的想法，为飞行中产生障碍！

PS：我已经问过这里和程序员，因为我认为它落在这两个网站上的主题。

Answer 1

下面应该工作得相当好：

def find_valid_locations(grid, z, a, b): 
    check = [(0, 0, 0, 0)] 
    w = z + b 
    h = z + a 
    while check: 
     x, y, ox, oy = check.pop() 
     if x + w >= len(grid) or y + h >= len(grid[0]): 
      continue 
     for i, row in enumerate(grid[x+ox:x+w+1], x+ox): 
      for j, val in enumerate(row[y+oy:y+h+1], y+oy): 
       if val: 
        break 
      else: 
       continue 
      check.append((x, j+1, 0, 0)) 
      if y == 0: 
       check.extend((ii, j+1, 0, 0) for ii in range(x+1, i+1)) 
       check.append((i+1, y, 0, 0)) 
      break 
     else: 
      yield (x, y) 
      check.append((x, y+1, 0, h-1)) 
      if y == 0: 
       check.append((x+1, y, w-1, 0)) 
      continue 

这里的蛮力法将检查每个潜在的矩形位置中的所有位置，并且只返回rectange没有遇到非零位置的位置。实际上，这就是我们在这里做，有以下优化：

• 如果我们已经找到了一个有效的位置（X，Y），我们可以检查位置（X + 1，y）和（X，Y + 1 ），只需通过向下或向右移动来检查添加到矩形的新位置。
• 如果我们在检查位置（x，y）时在位置（i，j）遇到障碍，我们可以跳过检查包含（i，j）的任何其他位置，方法是在（i + 1，y ）和（x，j + 1）。

注意，我改名参数x到z，这样我可以使用x在代码中的行索引。

Answer 2

您可以将面存储在一个矩阵M，然后遍历矩阵找个地方为新的矩形R的左上角：

for all rows of matrix M 
    for all columns of matrix M 
     variable empty = 0 
     for all numbers from 1 to a 
      for all numbers from 1 to b 
       empty = empty + M(row + a, col + b)      
     if empty == 0 
      insert R(row,col) //insert R with top-left corner at M(row,col) 
      break;  

Answer 3

这是一个蛮力搜索，它考虑了在一个二维Python列表（列表列表）中的一个网格中，具有边界c的矩形a，b的所有可能位置。

find_placements在调用isvalid之前将宽度添加到边框和高度。这种方式isvalid不需要考虑边界的任何事情。

我用宽度，高度，边框的变量a, b, c，这样它们就不会被通常为x, y, z的坐标所困惑。 gx和gy是网格x和网格y的缩写。

一个差异在于，以这种方式用2维列表表示一个网格，访问一个单元是用grid[y][x]而不是grid[x][y]完成的。其他一切都很简单。

def find_placements(grid, a, b, c): 
    """ 
    Return [(x, y), ...] for all valid placements in the grid 
    of rectangle a x b with border c. 
    """ 
    result = [] 
    for gx in xrange(len(grid[0]) - (a + c)): 
     for gy in xrange(len(grid) - (b + c)): 
      if isvalid(grid, (a + c), (b + c), gx, gy): 
       result.append((gx, gy)) 
    return result 


def isvalid(grid, a, b, x, y): 
    """ 
    Return True if rect a, b fits at pos x, y 
    without overlapping. 
    """ 
    for gx in xrange(x + a): 
     for gy in xrange(y + b): 
      if grid[gy][gx]: 
       return False 
    return True 

---

>>> grid =[ 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 0, 1, 1, 0], 
    [0, 0, 0, 0, 1, 1, 0], 
    [0, 0, 0, 0, 1, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 1, 0, 0, 1, 1], 
    [0, 0, 0, 0, 0, 1, 1] 
] 
>>> find_placements(grid, 3, 4, 1) 
[(0, 0)] 
>>>