Алгоритм вращения фигуры тетриса - PullRequest
Новая
       67

Алгоритм вращения фигуры тетриса

45 голосов
/ 24 октября 2008

Каковы лучшие алгоритмы (и объяснения) для представления и вращения частей игры тетрис? Я всегда нахожу схемы вращения и представления фигуры запутанными.

Кажется, что в большинстве игр с тетрисом на каждом обороте используется наивная «переделка массива блоков»:

http://www.codeplex.com/Project/ProjectDirectory.aspx?ProjectSearchText=tetris

Однако некоторые используют предварительно созданные кодированные числа и сдвиг битов для представления каждого фрагмента:

http://www.codeplex.com/wintris

Есть ли способ сделать это с использованием математики (не уверен, что он будет работать на доске на основе ячеек)?

Ответы [ 15 ]

31 голосов
/ 24 октября 2008

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

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

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

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

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

[  0   1 ]
[ -1   0 ]

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

[  0  -1 ]
[  1   0 ]
24 голосов
/ 15 ноября 2011

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

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

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

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

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

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

  5. На последнем шаге я только что прошел шаги 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());
}

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

12 голосов
/ 24 октября 2008

Вот как я это сделал недавно в тетрис-игре на основе 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. Если вы заинтересованы в том, как я дошел до этого, дайте мне знать.

11 голосов
/ 24 октября 2008

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

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

class ShapeRotation
{
    Point[4] points;
}

class Point
{
    int x, y;
}

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

7 голосов
/ 02 мая 2010

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

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 голосов
/ 24 октября 2008

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

3 голосов
/ 08 декабря 2015

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

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

originalMatrix = 
[0,   0,   <b>1</b>]
[<b>1</b>,   <b>1</b>,   <b>1</b>]

enter image description here

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

clockwise90DegreesRotatedMatrix = reverseTheOrderOfColumns(Transpose(originalMatrix))

anticlockwise90DegreesRotatedMatrix = reverseTheOrderOfRows(Transpose(originalMatrix))

Иллюстрация 

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


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


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

enter image description here

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

enter image description here

3 голосов
/ 04 января 2010

Я получил алгоритм вращения из поворотов матрицы здесь . Подводя итог: если у вас есть список координат для всех ячеек, которые составляют блок, например, [(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 для всех других блоков.

2 голосов
/ 31 декабря 2014

Если предположить, что центральный квадрат тетромино имеет координаты (x0, y0), которые остаются неизменными, то вращение остальных трех квадратов в 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;
    }
}
2 голосов
/ 16 ноября 2009

Если вы делаете это в 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]])
Страница:
...