Как проверить, соответствует ли набор координат фигуре тетриса в 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

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


python numpy coordinates tetris
person Legatro    schedule 19.11.2018    source источник
comment
вычесть пороговое значение (например, вектор исходного блока) из всех координат, чтобы ваш исходный блок оказался на [0,0], а затем сравнить с предопределенным списком фрагментов тетриса?   -  person vencaslac    schedule 19.11.2018
comment
вас волнуют ротации?   -  person Maarten Fabré    schedule 19.11.2018
comment
Помимо вращений, вы также хотите учитывать отражения? (традиционно отражения считаются разными фигурами, например, в классическом тетрисе они имеют разные цвета, но я не знаю, как вы). Важно, гарантируется ли порядок заданных координат? То есть всегда ли они начинаются в одном и том же исходном блоке и охватывают часть в одном и том же относительном порядке?   -  person jdehesa    schedule 19.11.2018
comment
@jdehesa Reflections также поможет с решением, которое я ищу. Исходный блок всегда будет одним и тем же для данной части, и порядок будет одинаковым. Я подробно остановился на этом в вопросе, чтобы сделать его более понятным. Спасибо!   -  person Legatro    schedule 19.11.2018

Ответы (1)


arrow_upward
0
arrow_downward

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

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

person jdehesa    schedule 19.11.2018