如何检查一组坐标是否与Python中的俄罗斯方块匹配

Question

我在研究俄罗斯方块。你知道吗

工件用坐标定义，每个工件都有一个原点块(0,0) 因此，根据放置原点块的位置，可以将L块定义为[(0,0), (0,1), (0,2), (1,2)]和[(0,-1), (0,0), (0,1), (1,1)]。你知道吗

我想检查一组坐标a，例如[(50,50), (50,51), (50,52), (51,52)]是否与给定俄罗斯方块片段B的形状匹配。

我现在正在使用numpy从A中的每个值中去掉一个A值，以获得相对坐标，然后与B进行比较。A的顺序始终是递增的，但不保证与B的顺序匹配。B与其他俄罗斯方块片段存储在一个列表中，并且在整个程序中，它的原始块将保持不变。下面的方法似乎效率低下，不考虑B的旋转/反射

def isAinB(A,B):  # A and B are numpy arrays
    for i in range(len(A)):
        matchCoords = A - A[i]
        setM = set([tuple(x) for x in matchCoords])
        setB = set([tuple(x) for x in B])
        if setM == setB:  # Sets are used here because the ordering of M and B are not guarenteed to match
            return True
    return False

有没有一个有效的方法/功能来实现这一点？（尽可能考虑旋转和反射）

Answer 1

这是一种方法。其思想是首先在一些规范坐标中构建一个工件的所有变体集（每个工件类型可以这样做一次并重用它），然后将给定的工件放在相同的规范坐标中并进行比较。你知道吗

# Rotates a piece by 90 degrees
def rotate_coords(coords):
    return [(y, -x) for x, y in coords]

# Returns a canonical coordinates representation of a piece as a frozen set
def canonical_coords(coords):
    x_min = min(x for x, _ in coords)
    y_min = min(y for _, y in coords)
    return frozenset((y - y_min, x - x_min) for x, y in coords)

# Makes all possible variations of a piece (optionally including reflections)
# as a set of canonical representations
def make_piece_variations(piece, reflections=True):
    variations = {canonical_coords(piece)}
    for i in range(3):
        piece = rotate_coords(piece)
        variations.add(canonical_coords(piece))
    if reflections:
        piece_reflected = [(y, x) for x, y in piece]
        variations.update(make_piece_variations(piece_reflected, False))
    return variations

# Checks if a given piece is in a set of variations
def matches_piece(piece, variations):
    return canonical_coords(piece) in variations

以下是一些测试：

# L-shaped piece
l_piece = [(0, 0), (0, 1), (0, 2), (1, 2)]
l_piece_variations = make_piece_variations(l_piece, reflections=True)

# Same orientation
print(matches_piece([(50, 50), (50, 51), (50, 52), (51, 52)], l_piece_variations))
# True

# Rotated
print(matches_piece([(50, 50), (51, 50), (52, 50), (52, 49)], l_piece_variations))
# True

# Reflected and rotated
print(matches_piece([(50, 50), (49, 50), (48, 50), (48, 49)], l_piece_variations))
# True

# Rotated and different order of coordinates
print(matches_piece([(50, 48), (50, 50), (49, 48), (50, 49)], l_piece_variations))
# True

# Different piece
print(matches_piece([(50, 50), (50, 51), (50, 52), (50, 53)], l_piece_variations))
# False

这并不是一个特别聪明的算法，但它可以在最小的约束下工作。你知道吗

编辑：因为在您的例子中，您说第一个块和相对顺序总是相同的，所以您可以按如下所示重新定义规范坐标，使其更加优化（尽管性能差异可能可以忽略不计，其使用也会受到更多限制）：

def canonical_coords(coords):
    return tuple((y - coords[0][0], x - coords[0][1]) for x, y in coords[1:])

第一个坐标始终是（0，0），因此您可以跳过它并将其用作其余坐标的参考点，并且可以使用frozenset代替tuple作为坐标序列。你知道吗