python - 如何检查一组坐标是否与Python中的俄罗斯方块相匹配
问题描述
我正在处理俄罗斯方块。
这些块是用坐标定义的,其中每个块都有一个原点块(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
是否有有效的方法/功能来实现这一点?(如果可能,还要考虑旋转和反射)
解决方案
这是处理它的一种方法。这个想法是首先在某些规范坐标中构建一个片段的所有变体集(您可以对每个片段类型执行一次并重复使用它),然后将给定片段放在相同的标准坐标中并进行比较。
# 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
您可以使用 a代替 atuple
作为坐标序列。
推荐阅读
- google-apps-script - 从范围输入中获取最后一个非空单元格
- delphi - 带有 FireDAC 的 Delphi 10.4 的 RxLib?
- node.js - 使用打字稿进行依赖注入并使用类进行表达
- java - 字段“record_id”没有默认值 - Spring JPA 错误
- android - 为什么上下文菜单不会在片段中打开?
- python - Matplotlib/Seaborn:我在哪里进行元素比较?ValueError:具有多个元素的数组的真值不明确
- perl - 在 Perl 中使用 foreach 代替 map 和 grep
- firebase - 在 Future 完成之前返回 Stream
- sql-server - 远程 Sql Server 连接疑难解答
- google-chrome - 如何在 Firefox Web 开发工具中调整“响应模式”缩放?