algorithm - Algoritmo de rotación de la pieza Tetris
rotation (15)
¿Cuáles son los mejores algoritmos (y explicaciones) para representar y rotar las piezas de un juego de tetris? Siempre encuentro confusos los esquemas de rotación y representación de piezas.
La mayoría de los juegos de tetris parecen usar un ingenuo "rehacer la matriz de bloques" en cada rotación:
http://www.codeplex.com/Project/ProjectDirectory.aspx?ProjectSearchText=tetris
Sin embargo, algunos usan números codificados previamente construidos y cambios de bit para representar cada pieza:
http://www.codeplex.com/wintris
¿Hay algún método para hacerlo utilizando las matemáticas (no estoy seguro de que funcione en una placa basada en células)?
Así es como lo hice recientemente en un juego de tetris basado en jQuery / CSS.
Trabaja el centro del bloque (para usar como punto de pivote), es decir, el centro de la forma del bloque. Llamar a eso (px, py).
Cada ladrillo que conforma la forma del bloque girará alrededor de ese punto. Para cada ladrillo, puede aplicar el siguiente cálculo ...
Donde el ancho y la altura de cada ladrillo es q, la ubicación actual del ladrillo (de la esquina superior izquierda) es (x1, y1) y la ubicación del ladrillo nuevo es (x2, y2):
x2 = (y1 + px - py)
y2 = (px + py - x1 - q)
Para rotar en la dirección opuesta:
x2 = (px + py - y1 - q)
y2 = (x1 + py - px)
Este cálculo se basa en una transformación de matriz afín 2D. Si estás interesado en cómo llegué a esto, házmelo saber.
Cuando estaba tratando de descubrir cómo funcionarían las rotaciones para mi juego de tetris, esta fue la primera pregunta que encontré en el desbordamiento de la pila. Aunque esta pregunta es antigua, creo que mi opinión ayudará a otros a tratar de resolver esto de forma algorítmica. En primer lugar, no estoy de acuerdo en que programar cada pieza y girar sea más fácil. La respuesta de Gamecat es correcta, pero quería profundizar en ella. Estos son los pasos que utilicé para resolver el problema de rotación en Java.
Para cada forma, determine dónde será su origen. Usé los puntos en el diagrama de esta página para asignar mis puntos de origen. Tenga en cuenta que, dependiendo de su implementación, es posible que tenga que modificar el origen cada vez que el usuario mueva la pieza.
La rotación asume que el origen está ubicado en el punto (0,0), por lo que deberá traducir cada bloque antes de que se pueda rotar. Por ejemplo, supongamos que su origen se encuentra actualmente en el punto (4, 5). Esto significa que antes de que se pueda rotar la forma, cada bloque debe traducirse -4 en la coordenada xy -5 en la coordenada y para ser relativa a (0,0).
En Java, un plano de coordenadas típico comienza con el punto (0,0) en la esquina superior izquierda y luego aumenta hacia la derecha y hacia abajo. Para compensar esto en mi implementación, multipliqué cada punto por -1 antes de la rotación.
Aquí están las fórmulas que usé para descubrir la nueva coordenada xey después de una rotación en sentido antihorario. Para obtener más información sobre esto, verificaría la página de Wikipedia en Rotation Matrix . x ''e y'' son las nuevas coordenadas:
x ''= x * cos (PI / 2) - y * sin (PI / 2) e y'' = x * sin (PI / 2) + y * cos (PI / 2).
Para el último paso, acabo de seguir los pasos 2 y 3 en orden inverso. Así que multipliqué mis resultados por -1 nuevamente y luego traduje los bloques a sus coordenadas originales.
Aquí está el código que funcionó para mí (en Java) para tener una idea de cómo hacerlo en su idioma:
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());
}
Este método es todo lo que se necesita para rotar su forma hacia la izquierda, que resulta ser mucho más pequeña (dependiendo de su idioma) que definir cada rotación para cada forma.
Dado que solo hay 4 orientaciones posibles para cada forma, ¿por qué no usar una matriz de estados para la forma y girar CW o CCW simplemente incrementa o disminuye el índice del estado de la forma (con el envolvente para el índice)? Creo que eso podría ser más rápido que realizar cálculos de rotación y otras cosas.
En Ruby, al menos, puedes usar matrices. Representa tus formas de pieza como matrices anidadas de matrices como [[0,1,11], [0,2], [0,3]]
require ''matrix''
shape = shape.map{|arr|(Matrix[arr] * Matrix[[0,-1],[1,0]]).to_a.flatten}
Sin embargo, estoy de acuerdo en que la codificación de las formas es factible ya que hay 7 formas y 4 estados para cada = 28 líneas y nunca será más que eso.
Para obtener más información al respecto, consulte la publicación de mi blog en http://pivotallabs.com/the-simplest-thing-that-could-possibly-work-in-tetris/ y una implementación completamente operativa (con errores menores) en https: // github.com/andrewfader/Tetronimo
Hay una cantidad limitada de formas, así que usaría una tabla fija y ningún cálculo. Eso ahorra tiempo.
Pero hay algoritmos de rotación.
Elija un punto central y gire pi / 2.
Si un bloque de una pieza comienza en (1,2) se mueve en sentido horario a (2, -1) y (-1, -2) y (-1, 2). Aplique esto para cada bloque y la pieza se gira.
Cada x es la y anterior y cada y - la x anterior. Lo cual da la siguiente matriz:
[ 0 1 ]
[ -1 0 ]
Para rotación hacia la izquierda, use:
[ 0 -1 ]
[ 1 0 ]
He usado una posición de forma y un conjunto de cuatro coordenadas para los cuatro puntos en todas las formas. Como está en el espacio 2D, puede aplicar fácilmente una matriz rotacional 2D a los puntos.
Los puntos son divs por lo que su clase css se activa y desactiva. (Esto es después de borrar la clase css de dónde estaban el último turno).
Obtuve un algoritmo de rotación a partir de las rotaciones de la matriz aquí . Para resumir: si tiene una lista de coordenadas para todas las celdas que componen el bloque, por ejemplo [(0, 1), (1, 1), (2, 1), (3, 1)] o [( 1, 0), (0, 1), (1, 1), (2, 1)]:
0123 012
0.... 0.#.
1#### or 1###
2.... 2...
3....
puedes calcular las nuevas coordenadas usando
x_new = y_old
y_new = 1 - (x_old - (me - 2))
para la rotación en sentido horario y
x_new = 1 - (y_old - (me - 2))
y_new = x_old
para la rotación en sentido antihorario. me es la extensión máxima del bloque, es decir, 4 para I-blocks, 2 para O-blocks y 3 para todos los demás bloques.
Personalmente, siempre he representado las rotaciones a mano: con muy pocas formas, es fácil codificar de esa manera. Básicamente tuve (como pseudo-código)
class Shape
{
Color color;
ShapeRotation[] rotations;
}
class ShapeRotation
{
Point[4] points;
}
class Point
{
int x, y;
}
Al menos conceptualmente, una matriz multidimensional de puntos directamente en forma haría el truco también :)
Pitón:
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
Puede rotar una matriz solo mediante la aplicación de operaciones matemáticas. Si tienes una matriz, di:
Mat A = [1,1,1]
[0,0,1]
[0,0,0]
Para rotarlo, multiplíquelo por su transposición y luego por esta matriz ([I] dentity [H] orizontaly [M] irrored):
IHM(A) = [0,0,1]
[0,1,0]
[1,0,0]
Entonces tendrás:
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]
Nota: El centro de rotación será el centro de la matriz, en este caso en (2,2).
Si el tamaño de la matriz es 3 * 3, entonces la forma más simple de rotarlo, por ejemplo, en sentido antihorario es:
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}};
*/
Si está haciendo esto en python, basado en celdas en lugar de pares de coordenadas, es muy simple rotar una lista anidada.
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]])
Si suponemos que el cuadrado central del tetromino tiene coordenadas (x0, y0) que permanecen sin cambios, entonces la rotación de los otros 3 cuadrados en Java se verá así:
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;
}
}
para piezas de tetris de 3x3 voltea xey de tu pieza y luego cambia las columnas externas, eso es lo que descubrí en algún momento
Representación
Representa cada pieza en la matriz mínima donde 1 representa los espacios ocupados por el tetriminoe y 0 representa el espacio vacío. Ejemplo:
originalMatrix =
[0, 0, 1]
[1, 1, 1]
Fórmula de rotación
clockwise90DegreesRotatedMatrix = reverseTheOrderOfColumns(Transpose(originalMatrix))
anticlockwise90DegreesRotatedMatrix = reverseTheOrderOfRows(Transpose(originalMatrix))
Ilustración
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]
