0

タイトルが適切ではありません。読み進めてください (これ以上のタイトルは見つかりませんでした)。

注: Python 2.7 を使用していますが、アルゴリズムも役に立ちます。

私は、その場で障害物を生成している横スクロール ゲームを作成しています。私が抱えている問題は、障害物を生成する方法を理解することです。o_O
ある種のロジックがありますが、ロジック全体を理解するのに苦労しています。

実装の観点から見た私の問題は次のとおり
です。すべての長方形である をSurfaceいくつか入れました。 次のように考えてください。Element

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(1 の) 別の四角形をオーバーラップせずに四角形を追加できるかどうか、およびすべての場所をどのように判断できますか。また、他のすべてのオブジェクトから x 要素 (対角線上であっても) の距離を維持すると、長方形全体が (x+3, x+4) になります。ifx=1, a=3, b=4のように、可能な配置は 1 つだけです:
(2 は新しいオブジェクトを表します)

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: 両方のサイトで話題になっていると思うので、ここと Programmers で質問しました。

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) および ( x, j+1)。

コードで行インデックスとして使用できるように、パラメーターの名前を に変更したことに注意してくださいx。zx

于 2013-07-28T08:59:40.820 に答える
0

これは、2 次元の Python リスト (リストのリスト) であるグリッド内の境界線 c を持つ四角形 a、b のすべての可能な配置を考慮する力ずくの検索です。

find_placementsを呼び出す前に、ボーダーに幅とボーダーに高さを追加しますisvalid。この方法でisvalidは、境界について何も考慮する必要はありません。

a, b, c通常はそのようなものである座標と混同しないように、幅、高さ、境界線に変数を使用x, y, zしました。gxグリッド xとgyグリッド y の略です。

矛盾の 1 つは、このようにグリッドを表す 2 次元リストでは、セルへのアクセスが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 に答える