Tetris Slice Rotation Algorithm

Question

What are the best algorithms (and explanations) for representing and turning pieces of a tetris game? I always find that the rotation and presentation of details is confusing.

Most Tetris games seem to use the naive "remodel block array" at every turn:

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

However, some use pre-built encoded numbers and bit offsets to represent each part:

http://www.codeplex.com/wintris

Is there a way to do this using math (not sure if this will work on a cell basis)?

Answer 1

There is a limited number of forms, so I would use a fixed table and not calculate. It saves time.

But there are rotation algorithms.

Select the center point and turn pi / 2.

If a piece block starts with (1,2), it moves clockwise to (2, -1) and (-1, -2) and (-1, 2). Apply this for each block and the piece is rotated.

Each x is the previous y and each y is the previous x. Which gives the following matrix:

[ 0 1 ] [ -1 0 ] 

To rotate counterclockwise use:

 [ 0 -1 ] [ 1 0 ] 

Answer 2

When I tried to figure out how the rotations would work for my Tetris game, this was the first question I discovered when the stack overflowed. Despite the fact that this question is outdated, I think that my contribution will help others trying to understand this algorithmically. Firstly, I do not agree that hard coding of each part and rotation will be easier. Gamecat's answer is correct, but I wanted to talk about it. Here are the steps that I used to solve the rotation problem in Java.

• For each form, determine where its origin will occur. I used the points in the diagram from this page to assign my starting points. Keep in mind that depending on your implementation, you may need to change the source each time a piece is moved by the user.

• Rotation assumes that the origin is at (0,0), so you will need to translate each block before it can be rotated. For example, suppose your origin is currently at (4, 5). This means that before the form can be rotated, each block must be translated in the x-coordinate -4, and -5 in the y-coordinate relative to (0,0).

• In Java, a typical coordinate plane starts at the point (0,0) in the upper left corner and then increases to the right and down. To compensate for this in my implementation, I multiplied each point by -1 before the rotation.

• Here are the formulas that I used to determine the new x and y coordinates after counterclockwise rotation. For more information about this, I would look at the Rotation Matrix Wikipedia page. x 'and y' - new coordinates:

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

• In the last step, I just went through steps 2 and 3 in the reverse order. So I again multiplied my results by -1, and then transferred the blocks back to the original coordinates.

Here is the code that worked for me (in Java) to get an idea of ​​how to do this in your language:

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

This method is all that is needed to rotate the figure to the left, which turns out to be much smaller (depending on your language) than determining each rotation for each figure.

Answer 3

Here's how I did it recently in a jQuery / CSS tetris game.

Design the center of the block (which will be used as a reference point), i.e. the center of the block shape. Name it (px, py).

Each brick that makes up the shape of the block will rotate around this point. For each brick, you can apply the following calculation ...

If each brick width and height is q, the current location of the brick (upper left corner) is (x1, y1), and the new location of the brick (x2, y2):

 x2 = (y1 + px - py) y2 = (px + py - x1 - q) 

To rotate the opposite direction:

 x2 = (px + py - y1 - q) y2 = (x1 + py - px) 

This calculation is based on the transformation of the affine matrix 2D. If you are interested in how I got to this, let me know.

Answer 4

Personally, I always imagined a turn by hand - with a very small number of figures, it is easy to code this path. Mostly I had (like pseudo code)

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

At least conceptually - a multidimensional array of points directly in the form could also do the trick :)

Answer 5

You can rotate a matrix only by applying mathematical operations to it. If you have a matrix, say:

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

To rotate it, multiply it by its transposition, and then by this matrix ([I] dentity [H] orizontaly [M] irrored):

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

Then you will get:

 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] 

Note: the center of rotation will be the center of the matrix, in this case at (2.2).

Answer 6

Since for each figure there are only 4 possible orientations, why not use an array of states for the form, and rotating CW or CCW simply increases or decreases the index of the state of the figure (with a wrapper for the index)? I would have thought that this could be faster than performing rotation calculations and more.

Answer 7

I got the rotation algorithm from matrix rotation here . To summarize: if you have a list of coordinates for all the cells that make up the block, for example. [(0, 1), (1, 1), (2, 1), (3, 1)] or [(1, 0), (0, 1), (1, 1), (2, 1) ]:

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

you can calculate new coordinates using

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

for clockwise rotation and

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

to rotate counterclockwise. me is the maximum degree of a block, i.e. 4 for I-blocks, 2 for O-blocks and 3 for all other blocks.

Answer 8

Performance

We represent each part in a minimal matrix, where 1 represents the spaces occupied by tetriminoe, and 0 represents empty space. Example:

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

Rotation formula

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

Illustration

 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 ] 

Answer 9

If you do this in python, instead of cell-based coordinate pairs, it's very easy to rotate the nested list.

 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]]) 

Answer 10

If we assume that the central square of tetromino has coordinates (x0, y0), which remains unchanged, then the rotation of the other 3 squares in Java will look like this:

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

Answer 11

for 3 × 3 pieces of tetris, flip x and y of your fragment, then change the outer columns, which I found out for a while

Answer 12

I used the position of the shape and a set of four coordinates for the four points in all the shapes. Since this is in 2D space, you can easily apply a 2D rotational matrix to points.

Dots are divs, so their css class is disabled. (this is after clearing the css class where they were last time.)

Answer 13

If the size of the array is 3 * 3, then the easiest way to rotate it, for example, counterclockwise, is:

 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}}; */ 

Answer 14

At least in Ruby you can use matrices. Imagine figure shapes as nested arrays of arrays such as [[0,1], [0,2], [0,3]]

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

Nevertheless, I agree that hard coding of forms is feasible, since for each of the 28 lines there are 7 figures and 4 states, and there will never be more than that.

For more details, see my blog post at https://content.pivotal.io/blog/the-simplest-thing-that-could-possbly-work-in-tetris and a fully working implementation (with minor errors) on https . : //github.com/andrewfader/Tetronimo

Answer 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