Как проверить, соответствует ли набор координат части тетриса в Python - PullRequest
Новая
       11

Как проверить, соответствует ли набор координат части тетриса в Python

0 голосов
/ 19 ноября 2018

Я работаю с кусочками тетриса.

Части определены с координатами, где у каждой фигуры есть исходный блок (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

Существует ли эффективный метод / функция для реализации этого?(С учетом поворотов и отражений, если возможно)

1 Ответ

0 голосов
/ 19 ноября 2018

Это один из способов приблизиться к этому. Идея состоит в том, чтобы сначала построить весь набор вариаций фрагмента в некоторых канонических координатах (вы можете сделать это один раз для каждого вида фрагмента и использовать его повторно), затем поместить данный фрагмент в те же канонические координаты и сравнить. 

# 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 для последовательности координат.

...