Алгоритм вращения фрагмента Tetris

Ответ 1

Существует ограниченное количество форм, поэтому я бы использовал фиксированную таблицу и не вычислял. Это экономит время.

Но есть алгоритмы вращения.

Выберите центральную точку и поверните pi/2.

Если блок куска начинается с (1,2), он движется по часовой стрелке до (2, -1) и (-1, -2) и (-1, 2). Примените это для каждого блока, и кусок повернут.

Каждый x является предыдущим y и каждым y - предыдущим x. Что дает следующую матрицу:

[  0   1 ]
[ -1   0 ]

Для вращения против часовой стрелки используйте:

[  0  -1 ]
[  1   0 ]

Ответ 2

Когда я пытался понять, как будут работать ротации для моей игры в тетрис, это был первый вопрос, который я обнаружил при переполнении стека. Несмотря на то, что этот вопрос устарел, я думаю, что мой вклад поможет другим, пытающимся понять это алгоритмически. Во-первых, я не согласен с тем, что жесткая кодировка каждой части и вращение будет проще. Ответ Gamecat верен, но я хотел рассказать об этом. Вот шаги, которые я использовал для решения проблемы вращения в Java.

• Для каждой формы определите, где будет происходить ее происхождение. Я использовал точки на диаграмме от эту страницу, чтобы назначить мои исходные точки. Имейте в виду, что в зависимости от вашей реализации вам может потребоваться изменить источник каждый раз, когда кусок перемещается пользователем.

• Вращение предполагает, что начало координат находится в точке (0,0), поэтому вам нужно будет перевести каждый блок, прежде чем его можно будет вращать. Например, предположим, что ваше происхождение в настоящее время находится в точке (4, 5). Это означает, что до того, как форма может быть повернута, каждый блок должен быть переведен в x-координате -4, а -5 в y-координате относительно (0,0).

• В Java типичная координатная плоскость начинается с точки (0,0) в верхнем левом углу, а затем увеличивается вправо и вниз. Чтобы компенсировать это в моей реализации, я умножал каждую точку на -1 перед вращением.

• Вот формулы, которые я использовал для определения новой координаты x и y после вращения против часовой стрелки. Для получения дополнительной информации об этом, я бы посмотрел страницу Википедии Rotation Matrix. x 'и y' - новые координаты:

  x '= x * cos (PI/2) - y * sin (PI/2) и y' = x * sin (PI/2) + y * cos (PI/2) .

• На последнем шаге я просто прошел шаги 2 и 3 в обратном порядке. Поэтому я снова умножил свои результаты на -1, а затем перевел блоки обратно в исходные координаты.

Вот код, который работал у меня (на Java), чтобы получить представление о том, как это сделать на вашем языке:

public synchronized void rotateLeft(){

    Point[] rotatedCoordinates = new Point[MAX_COORDINATES];

    for(int i = 0; i < MAX_COORDINATES; i++){

        // Translates current coordinate to be relative to (0,0)
        Point translationCoordinate = new Point(coordinates[i].x - origin.x, coordinates[i].y - origin.y);

        // Java coordinates start at 0 and increase as a point moves down, so
        // multiply by -1 to reverse
        translationCoordinate.y *= -1;

        // Clone coordinates, so I can use translation coordinates
        // in upcoming calculation
        rotatedCoordinates[i] = (Point)translationCoordinate.clone();

        // May need to round results after rotation
        rotatedCoordinates[i].x = (int)Math.round(translationCoordinate.x * Math.cos(Math.PI/2) - translationCoordinate.y * Math.sin(Math.PI/2)); 
        rotatedCoordinates[i].y = (int)Math.round(translationCoordinate.x * Math.sin(Math.PI/2) + translationCoordinate.y * Math.cos(Math.PI/2));

        // Multiply y-coordinate by -1 again
        rotatedCoordinates[i].y *= -1;

        // Translate to get new coordinates relative to
        // original origin
        rotatedCoordinates[i].x += origin.x;
        rotatedCoordinates[i].y += origin.y;

        // Erase the old coordinates by making them black
        matrix.fillCell(coordinates[i].x, coordinates[i].y, Color.black);

    }
    // Set new coordinates to be drawn on screen
    setCoordinates(rotatedCoordinates.clone());
}

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

Ответ 3

Вот как я это делал недавно в игре с тетрисом на jQuery/CSS.

Разработайте центр блока (который будет использоваться как опорная точка), т.е. центр формы блока. Назовите это (px, py).

Каждый кирпич, составляющий форму блока, будет вращаться вокруг этой точки. Для каждого кирпича вы можете применить следующий расчет...

Если каждая ширина и высота кирпича равна q, текущее местоположение кирпича (верхнего левого угла) равно (x1, y1), а новое местоположение кирпича (x2, y2):

x2 = (y1 + px - py)

y2 = (px + py - x1 - q)

Чтобы вращать противоположное направление:

x2 = (px + py - y1 - q)

y2 = (x1 + py - px)

Этот расчет основан на преобразовании аффинной матрицы 2D. Если вас интересует, как я дошел до этого, дайте мне знать.

Ответ 4

Лично я всегда представлял поворот вручную - с очень небольшим количеством фигур, легко кодировать этот путь. В основном у меня был (как псевдокод)

class Shape
{
    Color color;
    ShapeRotation[] rotations;
}

class ShapeRotation
{
    Point[4] points;
}

class Point
{
    int x, y;
}

По крайней мере, концептуально - многомерный массив точек непосредственно в форме тоже мог бы сделать трюк:)

Ответ 5

Вы можете вращать матрицу, только применяя к ней математические операции. Если у вас есть матрица, скажите:

Mat A = [1,1,1]
        [0,0,1]
        [0,0,0]

Чтобы повернуть его, умножьте его на его транспонирование, а затем на эту матрицу ([I] dentity [H] orizontaly [M] irrored):

IHM(A) = [0,0,1]
         [0,1,0]
         [1,0,0]

Затем вы получите:

Mat Rotation = Trn(A)*IHM(A) = [1,0,0]*[0,0,1] = [0,0,1]
                               [1,0,0] [0,1,0] = [0,0,1]
                               [1,1,0] [1,0,0] = [0,1,1]

Примечание: центр вращения будет центром матрицы, в этом случае при (2,2).

Ответ 6

Так как для каждой фигуры существует только 4 возможных ориентации, почему бы не использовать массив состояний для формы, а вращение CW или CCW просто увеличивает или уменьшает индекс состояния фигуры (с оберткой для индекса)? Я бы подумал, что это может быть быстрее, чем выполнение вычислений вращения и многое другое.

Ответ 7

Я получил алгоритм вращения от поворота матрицы здесь. Подводя итог: если у вас есть список координат для всех ячеек, составляющих блок, например. [(0, 1), (1, 1), (2, 1), (3, 1)] или [(1, 0), (0, 1), (1, 1), (2, 1) ]:

 0123       012
0....      0.#.
1####  or  1###
2....      2...
3....

вы можете вычислить новые координаты, используя

x_new = y_old
y_new = 1 - (x_old - (me - 2))

для вращения по часовой стрелке и

x_new = 1 - (y_old - (me - 2))
y_new = x_old

для вращения против часовой стрелки. me - максимальная степень блока, т.е. 4 для I-блоков, 2 для O-блоков и 3 для всех остальных блоков.

Ответ 8

Представление

Представляем каждую часть в минимальной матрице, где 1 представляют собой пространства, занимаемые tetriminoe, а 0 - пустое пространство. Пример:

originalMatrix = 
[0,   0,   1]
[1,   1,   1]

Формула вращения

clockwise90DegreesRotatedMatrix = reverseTheOrderOfColumns(Transpose(originalMatrix))

anticlockwise90DegreesRotatedMatrix = reverseTheOrderOfRows(Transpose(originalMatrix))

Иллюстрация

originalMatrix = 
  x    y    z
a[0,   0,   1]
b[1,   1,   1]

transposed = transpose(originalMatrix)
  a   b
x[0,  1]
y[0,  1]
z[1,  1]

counterClockwise90DegreesRotated = reverseTheOrderOfRows(transposed)
  a   b
z[1,  1]
y[0,  1]
x[0,  1]

clockwise90DegreesRotated = reverseTheOrderOfColumns(transposed)
  b   a
x[1,  0]
y[1,  0]
z[1,  1]

Ответ 9

Если вы делаете это в python, вместо пар координат, основанных на ячейках, очень просто повернуть вложенный список.

rotate = lambda tetrad: zip(*tetrad[::-1])

# S Tetrad
tetrad = rotate([[0,0,0,0], [0,0,0,0], [0,1,1,0], [1,1,0,0]])

Ответ 10

Если предположить, что центральный квадрат тетромино имеет координаты (x0, y0), который остается неизменным, то поворот других 3 квадратов в Java будет выглядеть так:

private void rotateClockwise()
{
    if(rotatable > 0)   //We don't rotate tetromino O. It doesn't have central square.
    {
        int i = y1 - y0;
        y1 = (y0 + x1) - x0;
        x1 = x0 - i;
        i = y2 - y0;
        y2 = (y0 + x2) - x0;
        x2 = x0 - i;
        i = y3 - y0;
        y3 = (y0 + x3) - x0;
        x3 = x0 - i;  
    }
}

private void rotateCounterClockwise()
{
    if(rotatable > 0)
    {
        int i = y1 - y0;
        y1 = (y0 - x1) + x0;
        x1 = x0 + i;
        i = y2 - y0;
        y2 = (y0 - x2) + x0;
        x2 = x0 + i;
        i = y3 - y0;
        y3 = (y0 - x3) + x0;
        x3 = x0 + i;
    }
}

Ответ 11

для кусков тетриса размером 3 × 3 перевернуть x и y вашего фрагмента затем поменяйте внешние столбцы что я выяснил какое-то время

Ответ 12

Я использовал положение фигуры и набор из четырех координат для четырех точек во всех фигурах. Так как это в 2D пространстве, вы можете легко применить 2D вращательную матрицу к точкам.

Точки - это divs, поэтому их класс css отключен. (это после очистки класса css, где они были в последний раз.)

Ответ 13

Если размер массива 3 * 3, то самый простой способ повернуть его, например, против часовой стрелки, это:

oldShapeMap[3][3] = {{1,1,0},
                     {0,1,0},
                     {0,1,1}};

bool newShapeMap[3][3] = {0};
int gridSize = 3;

for(int i=0;i<gridSize;i++)
    for(int j=0;j<gridSize;j++)
        newShapeMap[i][j] = oldShapeMap[j][(gridSize-1) - i];
/*newShapeMap now contain:    
                               {{0,0,1},
                                {1,1,1},
                                {1,0,0}};

*/ 

Ответ 14

По крайней мере, в Ruby вы можете использовать матрицы. Представьте фигуры фигуры в виде вложенных массивов массивов, таких как [[0,1], [0,2], [0,3]]

require 'matrix'
shape = shape.map{|arr|(Matrix[arr] * Matrix[[0,-1],[1,0]]).to_a.flatten}

Тем не менее, я согласен, что жесткое кодирование форм осуществимо, так как для каждой из 28 линий существует 7 фигур и 4 состояния, и никогда не будет больше, чем это.

Подробнее об этом см. Мой пост в блоге на https://content.pivotal.io/blog/the-simplest-thing-that-could-possbly-work-in-tetris и полностью работающую реализацию (с небольшими ошибками) на https. ://github.com/andrewfader/Tetronimo

Ответ 15

Python:

pieces = [
    [(0,0),(0,1),(0,2),(0,3)],
    [(0,0),(0,1),(1,0),(1,1)],
    [(1,0),(0,1),(1,1),(1,2)],
    [(0,0),(0,1),(1,0),(2,0)],
    [(0,0),(0,1),(1,1),(2,1)],
    [(0,1),(1,0),(1,1),(2,0)]
]

def get_piece_dimensions(piece):
    max_r = max_c = 0
    for point in piece:
        max_r = max(max_r, point[0])
        max_c = max(max_c, point[1])
    return max_r, max_c

def rotate_piece(piece):
    max_r, max_c = get_piece_dimensions(piece)
    new_piece = []
    for r in range(max_r+1):
        for c in range(max_c+1):
            if (r,c) in piece:
                new_piece.append((c, max_r-r))
    return new_piece