社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  Python

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

Legatro • 7 年前 • 1822 次点击  

我在研究俄罗斯方块。

工件用坐标定义,每个工件都有一个原点块 (0,0) 所以一块L可以定义为 [(0,0), (0,1), (0,2), (1,2)] 以及 [(0,-1), (0,0), (0,1), (1,1)] 取决于放置原点块的位置。

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

我目前正在使用numpy从a中的每个值中提取一个a值以达到相对坐标,然后与b进行比较。a的顺序始终是递增的,但不能保证与b的顺序匹配。b与其他俄罗斯方块片段存储在一个列表中,thr在整个程序中,它的原点块将保持不变。下面的方法似乎效率低下 不考虑旋转/反射 公元前

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

是否有有效的方法/功能来实现这一点?(尽可能考虑旋转和反射)

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/40007
文章 [ 1 ]  |  最新文章 7 年前
jdehesa
Reply   •   1 楼
jdehesa    7 年前

这是一种方法。其思想是首先在一些标准坐标系中构建一个工件的所有变量集(每种工件都可以这样做一次并重用它),然后将给定的工件放在相同的标准坐标系中并进行比较。

# 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 坐标序列。