Algorithme de rotation des pièces de Tetris

Question

Quels sont les meilleurs algorithmes (et explications) pour représenter et faire tourner les pièces d'un jeu de tétris ? Je trouve toujours les schémas de rotation et de représentation des pièces déroutants.

La plupart des jeux de tetris semblent utiliser un naïf "refaire le tableau des blocs" à chaque rotation :

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

Cependant, certains utilisent des numéros codés préétablis et un décalage de bits pour représenter chaque pièce :

http://www.codeplex.com/wintris

Existe-t-il une méthode pour faire cela en utilisant les mathématiques (je ne suis pas sûr que cela fonctionnerait sur une carte à base de cellules) ?

Answer 1

Il y a une quantité limitée de formes, donc j'utiliserais un tableau fixe et aucun calcul. Cela permet de gagner du temps.

Mais il existe des algorithmes de rotation.

Choisis un point central et fais une rotation de pi/2.

Si un bloc d'une pièce commence à (1,2), il se déplace dans le sens des aiguilles d'une montre vers (2,-1), (-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. Ce qui donne la matrice suivante :

[  0   1 ]
[ -1   0 ]

Pour une rotation dans le sens inverse des aiguilles d'une montre, utilisez :

[  0  -1 ]
[  1   0 ]

Answer 2

Lorsque j'ai essayé de comprendre comment les rotations fonctionneraient pour mon jeu de tetris, c'est la première question que j'ai trouvée sur stack overflow. Même si cette question est ancienne, je pense que ma contribution aidera d'autres personnes qui tentent de résoudre ce problème de manière algorithmique. Tout d'abord, je ne suis pas d'accord pour dire que coder en dur chaque pièce et chaque rotation sera plus facile. La réponse de Gamecat est correcte, mais je voulais la développer. Voici les étapes que j'ai utilisées pour résoudre le problème de rotation en Java.

1. Pour chaque forme, déterminez où sera son origine. J'ai utilisé les points du diagramme de cette page pour attribuer mes points d'origine. Gardez à l'esprit que, selon votre implémentation, vous devrez peut-être modifier l'origine chaque fois que la pièce sera déplacée par l'utilisateur.

2. La rotation suppose que l'origine est située au point (0,0), vous devrez donc translater chaque bloc avant de pouvoir le faire pivoter. Par exemple, supposons que votre origine est actuellement au point (4, 5). Cela signifie qu'avant de pouvoir faire pivoter la forme, chaque bloc doit être translaté de -4 dans la coordonnée x et de -5 dans la coordonnée y pour être relatif à (0,0).

3. En Java, un plan de coordonnées typique commence par le point (0,0) dans le coin supérieur gauche et augmente ensuite vers la droite et 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 déterminer les nouvelles coordonnées x et y après une rotation dans le sens inverse des aiguilles d'une montre. Pour plus d'informations à ce sujet, je vous invite à consulter la page Wikipédia suivante 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, j'ai juste parcouru 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 d'origine.

Voici le code qui a fonctionné pour moi (en Java) pour avoir une idée de la façon de 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 faire pivoter votre forme vers la gauche, ce qui s'avère beaucoup plus petit (selon votre langue) que de définir chaque rotation pour chaque forme.

Answer 3

C'est ainsi que je l'ai fait récemment dans un jeu de tétris basé sur jQuery/CSS.

Déterminez le centre du bloc (à utiliser comme point de pivot), c'est-à-dire le centre de la forme du bloc. Appelez cela (px, py).

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

La largeur et la hauteur de chaque brique étant q, l'emplacement actuel de la brique (du coin supérieur gauche) est (x1, y1) et le nouvel emplacement de la brique est (x2, y2) :

x2 = (y1 + px - py)

y2 = (px + py - x1 - q)

Pour tourner dans le sens inverse :

x2 = (px + py - y1 - q)

y2 = (x1 + py - px)

Ce calcul est basé sur une transformation matricielle affine 2D. Si vous souhaitez savoir comment j'en suis arrivé là, faites-le moi savoir.

Answer 4

Personnellement, j'ai toujours représenté les rotations à la main - avec très peu de formes, c'est facile à coder de cette façon. En gros, j'avais (en 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 dans la forme ferait aussi l'affaire :)

Answer 5

Puisqu'il n'y a que 4 orientations possibles pour chaque forme, pourquoi ne pas utiliser un tableau d'états pour la forme et que la rotation dans le sens horaire ou anti-horaire incrémente ou décrémente simplement l'index de l'état de la forme (avec une enveloppe pour l'index) ? Je pense que cela pourrait être plus rapide que d'effectuer des calculs de rotation et autres.