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

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

Большинство игр с тетрисом, по-видимому, используют наивное «переделывание массива блоков» при каждом повороте:

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

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

http://www.codeplex.com/wintris

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

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

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

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

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

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

[ 0 1 ] [ -1 0 ] 

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

 [ 0 -1 ] [ 1 0 ] 

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

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

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

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

  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()); } 

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

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

 class Shape { Color color; ShapeRotation[] rotations; } class ShapeRotation { Point[4] points; } class Point { int x, y; } 

По крайней мере, концептуально – multidimensional array точек непосредственно в форме мог бы сделать трюк тоже 🙂

Вот как я это делал недавно в игре на основе тетриса на основе 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) 

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

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

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

Чтобы повернуть его, умножьте его на его транспонирование, а затем на эту матрицу ([I] dentity [H] or horizontaly [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).

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

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

Если вы делаете это в 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]]) 

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

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

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

введите описание изображения здесь

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

 clockwise90DegreesRotatedMatrix = reverseTheOrderOfColumns(Transpose(originalMatrix)) anticlockwise90DegreesRotatedMatrix = reverseTheOrderOfRows(Transpose(originalMatrix)) 

иллюстрация

 originalMatrix = xyz a[0, 0, 1 ] b[ 1 , 1 , 1 ] 

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

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

введите описание изображения здесь

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

введите описание изображения здесь

для трехцветных тетрисов размером 3×3 и x вашей части, затем поменяйте внешние столбцы, вот что я выяснил некоторое время

Если предположить, что центральный квадрат тетромино имеет координаты (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; } } 

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

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

Если размер массива 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 

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

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

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

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

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 
Давайте будем гением компьютера.