Algoritmo di rotazione del pezzo di Tetris

Quali sono i migliori algoritmi (e spiegazioni) per rappresentare e ruotare i pezzi di un gioco di tetris? Trovo sempre confusi la rotazione del pezzo e gli schemi di rappresentazione.

La maggior parte dei giochi di tetris sembra utilizzare un ingenuo “remake della matrice di blocchi” ad ogni rotazione:

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

Tuttavia, alcuni usano numeri codificati pre-costruiti e bit shifting per rappresentare ciascun pezzo:

http://www.codeplex.com/wintris

Esiste un metodo per farlo usando la matematica (non è sicuro che funzioni su una scheda basata su celle)?

C’è una quantità limitata di forms, quindi utilizzerei una tabella fissa e nessun calcolo. Questo fa risparmiare tempo.

Ma ci sono algoritmi di rotazione.

Scegli un punto centrale e ruota pi / 2.

Se un blocco di un pezzo inizia da (1,2), si sposta in senso orario su (2, -1) e (-1, -2) e (-1, 2). Applicalo per ogni blocco e il pezzo viene ruotato.

Ogni x è la y precedente e ogni y – la x precedente. Che dà la seguente matrice:

[ 0 1 ] [ -1 0 ] 

Per la rotazione in senso antiorario, utilizzare:

 [ 0 -1 ] [ 1 0 ] 

Quando stavo cercando di capire come funzionavano le rotazioni per il mio gioco tetris, questa è stata la prima domanda che ho trovato sullo stack overflow. Anche se questa domanda è vecchia, penso che il mio contributo aiuterà gli altri a cercare di capirlo in modo algoritmico. In primo luogo, non sono d’accordo sul fatto che codificare a fondo ogni pezzo e la rotazione sarà più facile. La risposta di Gamecat è corretta, ma volevo approfondire la questione. Ecco i passaggi che ho usato per risolvere il problema di rotazione in Java.

  1. Per ogni forma, determinare dove sarà la sua origine. Ho usato i punti sul diagramma da questa pagina per assegnare i miei punti di origine. Tieni presente che, a seconda dell’implementazione, potresti dover modificare l’origine ogni volta che il pezzo viene spostato dall’utente.

  2. La rotazione presuppone che l’origine si trovi al punto (0,0), quindi dovrai tradurre ogni blocco prima che possa essere ruotato. Ad esempio, supponiamo che la tua origine sia attualmente al punto (4, 5). Ciò significa che prima che la forma possa essere ruotata, ogni blocco deve essere tradotto -4 nella coordinata x e -5 nella coordinata y per essere relativo a (0,0).

  3. In Java, un piano di coordinate tipico inizia con il punto (0,0) nell’angolo in alto a sinistra e poi aumenta verso destra e verso il basso. Per compensare questo nella mia implementazione, ho moltiplicato ogni punto di -1 prima della rotazione.

  4. Ecco le formule che ho usato per calcolare la nuova coordinata x e y dopo una rotazione in senso antiorario. Per ulteriori informazioni su questo, vorrei controllare la pagina di Wikipedia su Rotation Matrix . x ‘e y’ sono le nuove coordinate:

    x ‘= x * cos (PI / 2) – y * sin (PI / 2) ey = = x * sin (PI / 2) + y * cos (PI / 2).

  5. Per l’ultimo passaggio, ho appena seguito i passaggi 2 e 3 in ordine inverso. Quindi ho moltiplicato i miei risultati di -1 e poi ho tradotto i blocchi nelle loro coordinate originali.

Ecco il codice che ha funzionato per me (in Java) per avere un’idea di come farlo nella tua lingua:

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

Questo metodo è tutto ciò che è necessario per ruotare la tua forma a sinistra, che risulta essere molto più piccola (a seconda della tua lingua) rispetto alla definizione di ogni rotazione per ogni forma.

Personalmente ho sempre rappresentato le rotazioni a mano – con pochissime forms, è facile codificarle in questo modo. Fondamentalmente avevo (come pseudo-codice)

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

Almeno concettualmente, anche una serie multidimensionale di punti direttamente in forma farebbe il trucco 🙂

Ecco come l’ho fatto di recente in un gioco tetris basato su jQuery / CSS.

Calcola il centro del blocco (da utilizzare come punto di rotazione), ovvero il centro della forma del blocco. Chiamalo (px, py).

Ogni mattone che compone la forma del blocco ruoterà attorno a quel punto. Per ogni mattone, puoi applicare il seguente calcolo …

Quando la larghezza e l’altezza di ciascun mattone sono q, la posizione corrente del mattone (nell’angolo in alto a sinistra) è (x1, y1) e la posizione del nuovo mattone è (x2, y2):

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

Per ruotare nella direzione opposta:

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

Questo calcolo si basa su una trasformazione della matrice affine 2D. Se sei interessato a come sono arrivato a questo fammi sapere.

È ansible ruotare una matrice solo applicando operazioni matematiche ad essa. Se hai una matrice, dì:

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

Per ruotarlo, moltiplicarlo per la sua trasposizione e quindi per questa matrice ([I] dentity [H] orizontaly [M] irrored):

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

Quindi avrai:

 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: il centro di rotazione sarà il centro della matrice, in questo caso a (2,2).

Dal momento che ci sono solo 4 possibili orientamenti per ogni forma, perché non utilizzare una matrice di stati per la forma e ruotando CW o CCW è sufficiente incrementare o decrementare l’indice dello stato forma (con avvolgimento per l’indice)? Penserei che potrebbe essere più veloce di eseguire calcoli di rotazione e quant’altro.

Ho derivato un algoritmo di rotazione dalle rotazioni della matrice qui . Per riassumere: Se si dispone di un elenco di coordinate per tutte le celle che compongono il blocco, ad esempio [(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.... 

puoi calcolare le nuove coordinate usando

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

per rotazione oraria e

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

per rotazione antioraria. me è l’estensione massima del blocco, cioè 4 per I-blocks, 2 per O-blocks e 3 per tutti gli altri blocchi.

Se lo stai facendo in python, basato su celle invece che su coppie di coordinate, è molto semplice ruotare un elenco annidato.

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

Rappresentazione

Rappresenta ogni pezzo nella matrice minima dove 1 rappresenta gli spazi occupati dal tetriminoe e 0 rappresenta lo spazio vuoto. Esempio:

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

inserisci la descrizione dell'immagine qui

Formula di rotazione

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

Illustrazione

 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 ] 

inserisci la descrizione dell'immagine qui

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

inserisci la descrizione dell'immagine qui

per pezzi di tetris di dimensioni 3×3 flip xey del tuo pezzo quindi scambia le colonne esterne che è quello che ho capito un po ‘di tempo

Se assumiamo che il quadrato centrale del tetromino abbia coordinate (x0, y0) che rimangono invariate, la rotazione degli altri 3 quadrati in Java sarà simile a questa:

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

Ho usato una posizione di forma e un insieme di quattro coordinate per i quattro punti in tutte le forms. Dal momento che è nello spazio 2D, puoi applicare facilmente una matrice rotazionale 2D ai punti.

I punti sono div così la loro class css viene distriggersta da off a on. (questo è dopo aver cancellato la class css di dove erano l’ultimo turno.)

Se la dimensione dell’array è 3 * 3, il modo più semplice per ruotarlo, ad esempio in senso antiorario, è:

 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 

In Ruby, almeno, puoi effettivamente usare le matrici. Rappresenta le tue forms pezzo come matrici annidate di matrici come [[0,1], [0,2], [0,3]]

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

Tuttavia, sono d’accordo sul fatto che l’hard-coding delle forms è fattibile dato che ci sono 7 forms e 4 stati per ciascuna = 28 linee e non sarà mai più di questo.

Per ulteriori informazioni su questo vedi il mio blog post su http://pivotallabs.com/the-simplest-thing-that-could-possibly-work-in-tetris/ e un’implementazione completamente funzionante (con bug minori) su https: // github.com/andrewfader/Tetronimo

Pitone:

 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