0

好吧，标题不太合适，请继续阅读（我找不到更好的）。

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

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

所以从实现的角度来看，这是我的问题：
我有一个Surface，我在其中放了一些Elements，它们都是矩形。
想一想：

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

与上述结构一样，我如何确定是否axb可以添加一个矩形而不重叠另一个矩形（1s），以及在哪里。此外，在与所有其他对象保持 x 元素（甚至对角线）的距离的情况下，这意味着整个矩形是 (x+3, x+4)。像 if 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：我在这里和程序员上都问过这个问题，因为我认为这两个网站都属于主题。

4

3 回答 3

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

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

  • 如果我们找到了一个有效的位置 (x, y)，我们可以很容易地检查位置 (x+1, y) 和 (x, y+1)，只需检查添加到矩形的新位置，方法是将其向下移动或正确的。
  • 如果我们在检查位置 (x, y) 时在位置 (i, j) 遇到障碍物，我们可以通过在 (i+1, y) 和 (i+1, y) 和 ( x, j+1)。

请注意，我将参数重命名为x，z以便可以x在代码中用作行索引。

于 2013-07-28T08:59:40.820 回答
0

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

find_placements在调用isvalid. 这种方式isvalid不需要考虑边界的任何事情。

我为宽度、高度、边框使用了变量a, b, c，这样它们就不会被通常类似的坐标混淆x, y, z。gx并且gy是网格 x 和网格 y 的缩写。

一个差异是，使用以这种方式表示网格的二维列表，访问单元格是用grid[y][x]not完成的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)]
>>>
于 2013-07-28T10:02:07.750 回答
0

您可以将曲面存储在矩阵 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;
于 2013-07-28T08:38:08.773 回答