Algorithme De Rotation Des Pièces De Tetris

il y a une quantité limitée de formes, donc j'utiliserais une table fixe et aucun calcul. Qui permet de gagner du temps.

mais il y a des algorithmes de rotation.

a choisi un point central et pivote pi/2.

Si un bloc d'un morceau commence à (1,2) il se déplace dans le sens horaire pour (2,-1) et (-1,-2) et (-1, 2). Appliquez ceci pour chaque bloc et la pièce est tournée.

chaque x est le y précédent et chaque y - le x précédent. Qui donne la matrice suivante:

[  0   1 ]
[ -1   0 ]

pour une rotation dans le sens contraire des aiguilles d'une montre, utiliser:

[  0  -1 ]
[  1   0 ]

quand j'ai essayé de comprendre comment les rotations fonctionneraient pour mon jeu tetris, c'était la première question que j'ai trouvé sur le débordement de pile. Même si cette question Est ancienne, je pense que mon apport aidera d'autres personnes à essayer de comprendre cela algorithmiquement. Tout d'abord, je ne suis pas d'accord que le codage dur chaque pièce et la rotation sera plus facile. La réponse de Gamecat est correcte, mais je voulais m'y attarder. Voici les étapes que j'ai utilisées pour résoudre le problème de rotation en Java.

1. pour chaque forme, déterminer son origine. J'ai utilisé les points sur le diagramme de cette page pour assigner mes points d'origine. Gardez à l'esprit que, selon votre application, vous pouvez avoir à modifier l'origine chaque fois que la pièce est déplacée par l'utilisateur.

2. Rotation suppose que l'origine est située au point (0,0), donc vous devrez traduire chaque bloc avant qu'il puisse être tourné. Exemple, supposons que votre origine soit actuellement au point (4, 5). Cela signifie qu'avant que la forme puisse être tournée, chaque bloc doit être traduit par -4 dans la coordonnée x et -5 dans la coordonnée y pour être relatif à (0,0).

3. en Java, un plan de coordonnées typique commence par un point (0,0) dans le coin supérieur le plus à gauche et augmente ensuite vers la droite et vers le bas. Pour compenser cela dans mon implémentation, j'ai multiplié chaque point par -1 avant la rotation.

4. Voici les formules que j'ai utilisées pour calculer la nouvelle coordonnée x et y après une rotation dans le sens contraire des aiguilles d'une montre. Pour plus d'informations à ce sujet, je voudrais consulter la page Wikipedia sur matrice de Rotation . x' et y' sont les nouvelles coordonnées:

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

5. pour la dernière étape, je viens de passer par les étapes 2 et 3 dans l'ordre inverse. J'ai donc multiplié mes résultats par -1 à nouveau, puis j'ai ramené les blocs à leurs coordonnées originales.

voici le code qui a fonctionné pour moi (en Java) pour avoir une idée de comment le faire dans votre langue:

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

cette méthode est tout ce qui est nécessaire pour tourner votre forme vers la gauche, qui s'avère être beaucoup plus petite (selon votre langue) que de définir chaque rotation pour chaque forme.

personnellement, J'ai toujours représenté les rotations à la main - avec très peu de formes, il est facile de coder de cette façon. Basiquement j'ai eu (comme pseudo-code)

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

class ShapeRotation
{
    Point[4] points;
}

class Point
{
    int x, y;
}

du moins sur le plan conceptuel - un tableau multidimensionnel de points directement en forme ferait l'affaire aussi:)

c'est comme ça que je l'ai fait récemment dans un jeu de tetris basé sur jQuery/CSS.

déterminer le centre du bloc (à utiliser comme point de pivot), c'est-à-dire le centre de la forme du bloc. Appelez ça (px, py).

chaque brique qui forme le bloc tournera autour de ce point. Pour chaque brique, vous pouvez appliquer le calcul suivant...

où la largeur et la hauteur de chaque brique est q, l'emplacement actuel de la brique (du dessus coin gauche) est (x1, y1) et le nouvel emplacement de brique est (x2, y2):

x2 = (y1 + px - py)

y2 = (px + py - x1 - q)

pour tourner dans la direction opposée:

x2 = (px + py - y1 - q)

y2 = (x1 + py - px)

ce calcul est basé sur une transformation de matrice affine 2D. Si vous voulez savoir comment je suis arrivé là, dites-le-moi.

vous pouvez tourner une matrice seulement en appliquant des opérations mathématiques à elle. Si vous avez une matrice, dites:

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

pour le faire tourner, le multiplier par sa transposition et ensuite par cette matrice ([I]dentity [H]orizontaly [M]irrored):

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

alors vous aurez:

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]

Remarque: le Centre de rotation sera le centre de la matrice, dans ce cas (2,2).

Puisqu'il n'y a que 4 orientations possibles pour chaque forme, pourquoi ne pas utiliser un tableau d'États pour la forme et tourner CW ou CCW incrémente ou décrémente simplement l'indice de l'état de la forme (avec wraparound pour l'indice)? Je pense que ça pourrait être plus rapide que d'effectuer des calculs de rotation et autres.

j'ai tiré un algorithme de rotation à partir de la matrice des rotations ici . Pour résumer: Si vous avez une liste de coordonnées de toutes les cellules qui composent le bloc, par exemple [(0, 1), (1, 1), (2, 1), (3, 1)] ou [(1, 0), (0, 1), (1, 1), (2, 1)]:

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

vous pouvez calculer les nouvelles coordonnées en utilisant

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

pour rotation dans le sens des aiguilles d'une montre et

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

pour rotation dans le sens contraire des aiguilles d'une montre. me est l'étendue maximale du bloc, c'est-à-dire 4 pour les blocs I, 2 pour les blocs O et 3 pour tous les autres blocs.

si vous faites cela en Python, basé sur les cellules au lieu des paires de coordonnées, c'est très simple de faire tourner une liste imbriquée.

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

représentation

représente chaque pièce de la matrice minimale où 1 représente les espaces occupés par les tétramides et 0 représente l'espace vide. Exemple:

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

Formule De Rotation

clockwise90DegreesRotatedMatrix = reverseTheOrderOfColumns(Transpose(originalMatrix))

anticlockwise90DegreesRotatedMatrix = reverseTheOrderOfRows(Transpose(originalMatrix))

Illustration

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]

pour les pièces tetris de taille 3x3 inverser x et y de votre pièce ensuite permuter les colonnes extérieures c'est ce que j'ai compris un jour

si nous supposons que le carré central du tétromino a des coordonnées (x0, y0) qui restent inchangées alors la rotation des 3 autres carrés en Java ressemblera à ceci:

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

j'ai utilisé une position de forme et un ensemble de quatre coordonnées pour les quatre points dans toutes les formes. Puisqu'il est dans l'espace 2D, vous pouvez facilement appliquer un 2D matrice de rotation aux points.

les points sont divs de sorte que leur classe css est éteint de off à on. (c'est après avoir dégagé la classe css de l'endroit où ils étaient au dernier virage.)

si la taille du tableau est 3*3, que la façon la plus simple de le tourner par exemple dans le sens anti-horaire est:

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

*/ 

dans Ruby, au moins, vous pouvez réellement utiliser des matrices. Représentez vos formes de pièce comme des tableaux imbriqués de tableaux comme [[0,1],[0,2],[0,3]]

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

cependant, je suis d'accord que le codage dur des formes est faisable puisqu'il y a 7 formes et 4 états pour chacune = 28 lignes et il ne sera jamais plus que cela.

pour plus sur ce Voir mon billet de blog à http://pivotallabs.com/the-simplest-thing-that-could-possibly-work-in-tetris/ et une implémentation entièrement fonctionnelle (avec des bugs mineurs) à 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