Implementierung von Tetris: Kollisionserkennung

German (Deutsch) translation by Federicco Ancie (you can also view the original English article)

Ich bin sicher, dass es möglich ist, ein Tetris-Spiel mit einem Point-and-Click-Gamedev-Tool zu erstellen, aber ich konnte nie herausfinden, wie. Heute denke ich besser auf einer höheren Abstraktionsebene, wo das Tetromino, das Sie auf dem Bildschirm sehen, nur eine Darstellung dessen ist, was im zugrunde liegenden Spiel vor sich geht. In diesem Tutorial zeige ich Ihnen, was ich meine, indem ich Ihnen den Umgang mit der Kollisionserkennung in Tetris demonstriere.

Hinweis: Obwohl der Code in diesem Tutorial mit AS3 geschrieben wurde, sollten Sie in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte verwenden können.

Das Gitter

Ein Standard-Tetris-Spielfeld besteht aus 16 Zeilen und 10 Spalten. Wir können dies in einem mehrdimensionalen Array darstellen, das 16 Unterarrays mit 10 Elementen enthält:

Implementing Tetris: Collision Detection

Grafiken aus diesem großartigen Vectortuts+ Tutorial.

Stellen Sie sich vor, das Bild links ist ein Screenshot aus dem Spiel - so könnte das Spiel für den Spieler aussehen, nachdem ein Tetromino gelandet ist, aber bevor ein anderer erzeugt wurde.

Auf der rechten Seite befindet sich eine Array-Darstellung des aktuellen Status des Spiels. Nennen wir es landed[], da es sich auf alle Blöcke bezieht, die gelandet sind. Ein Element von 0 bedeutet, dass kein Block diesen Raum belegt. 1 bedeutet, dass ein Block in diesem Raum gelandet ist.

Lassen Sie uns nun einen O-Tetromino in der Mitte oben auf dem Feld erzeugen:

1	tetromino.shape = [[1,1],
2	[1,1]];
3	tetromino.topLeft = {row: 0, col:4};

Die shape-Eigenschaft ist eine weitere mehrdimensionale Array-Darstellung der Form dieses Tetrominos. topLeft gibt die Position des oberen linken Blocks des Tetromino an: in der oberen Reihe und in der fünften Spalte in.

Wir rendern alles. Zuerst zeichnen wir den Hintergrund - das ist einfach, es ist nur ein statisches Gitterbild.

Dann zeichnen wir jeden Block aus dem landed[] Array:

for (var row = 0; row < landed.length; row++) {
    for (var col = 0; col < landed[row].length; col++) {
        if (landed[row][col] != 0) {
            //draw block at position corresponding to row and col
            //remember, row gives y-position, col gives x-position
        }
     }
}

Meine Blockbilder sind 20x20px groß. Um die Blöcke zu zeichnen, könnte ich einfach ein neues Blockbild bei (col * 20, row * 20) einfügen. Die Details spielen keine Rolle.

Danach zeichnen wir jeden Block im aktuellen Tetromino:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            //draw block at position corresponding to 
            //row + topLeft.row, and 
            //col + topLeft.col
        }
     }
}

Wir können hier den gleichen Zeichnungscode verwenden, aber wir müssen die Blöcke um topLeft versetzen.

Hier ist das Ergebnis:

Beachten Sie, dass das neue O-Tetromino nicht im landed[] Array angezeigt wird - das liegt daran, dass es noch nicht gelandet ist.

Fallen

Angenommen, der Player berührt die Bedienelemente nicht. In regelmäßigen Abständen - sagen wir jede halbe Sekunde - muss der O-Tetromino eine Reihe nach unten fallen.

Es ist verlockend, einfach anzurufen:

1	tetromino.topLeft.row++;

...und dann alles erneut rendern, aber dies erkennt keine Überlappungen zwischen dem O-Tetromino und den bereits gelandeten Blöcken.

Stattdessen werden wir zuerst nach möglichen Kollisionen suchen und dann den Tetromino nur bewegen, wenn er "sicher" ist.

Dazu müssen wir eine mögliche neue Position für den Tetromino definieren:

1	tetromino.potentialTopLeft = {row: 1, col: 4};

Jetzt prüfen wir auf Kollisionen. Der einfachste Weg, dies zu tun, besteht darin, alle Leerzeichen im Raster zu durchlaufen, die der Tetromino an seiner potenziellen neuen Position einnehmen würde, und das landed[]-Array zu überprüfen, um festzustellen, ob sie bereits vergeben sind:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            if (landed[row + tetromino.potentialTopLeft.row] != 0 &&
                landed[col + tetromino.potentialTopLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Lassen Sie uns dies testen:

1	tetromino.shape = [[1,1],
2	[1,1]];
3	tetromino.potentialTopLeft: {row: 1, col: 4}
4	--------------------------------------------
5	row: 0, col: 0, tetromino.shape[0][0]: 1, landed[0+1][0+4]: 0
6	row: 0, col: 1, tetromino.shape[0][1]: 1, landed[0+1][1+4]: 0
7	row: 1, col: 0, tetromino.shape[1][0]: 1, landed[1+1][0+4]: 0
8	row: 1, col: 1, tetromino.shape[1][1]: 1, landed[1+1][1+4]: 0

Alle Nullen! Dies bedeutet, dass es keine Kollision gibt, sodass sich der Tetromino bewegen kann.

Legen wir fest:

1	tetromino.topLeft = tetromino.potentialTopLeft;

...und dann alles nochmal rendern:

Großartig!

Landing

Angenommen, der Spieler lässt den Tetromino bis zu diesem Punkt fallen:

Oben links befindet sich {row: 11, col: 4}. Wir können sehen, dass der Tetromino mit den gelandeten Blöcken kollidieren würde, wenn er weiter fallen würde - aber findet unser Code es heraus? Wir werden sehen:

1	tetromino.shape = [[1,1],
2	[1,1]];
3	tetromino.potentialTopLeft: {row: 12, col: 4}
4	--------------------------------------------
5	row: 0, col: 0, tetromino.shape[0][0]: 1, landed[0+12][0+4]: 0
6	row: 0, col: 1, tetromino.shape[0][1]: 1, landed[0+12][1+4]: 0
7	row: 1, col: 0, tetromino.shape[1][0]: 1, landed[1+12][0+4]: 1
8	row: 1, col: 1, tetromino.shape[1][1]: 1, landed[1+12][1+4]: 0

Es gibt eine 1, was bedeutet, dass es eine Kollision gibt - speziell würde der Tetromino mit dem Block kollidieren landed[13][4].

Das bedeutet, dass der Tetromino gelandet ist, was bedeutet, dass wir ihn dem landed[] Array hinzufügen müssen. Wir können dies mit einer sehr ähnlichen Schleife tun, mit der wir nach möglichen Kollisionen gesucht haben:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            landed[row + tetromino.topLeft.row][col + tetromino.topLeft.col] = tetromino.shape[row][col];
        }
     }
}

Hier ist das Ergebnis:

So weit, ist es gut. Aber Sie haben vielleicht bemerkt, dass wir uns nicht mit dem Fall befassen, in dem der Tetromino auf dem "Boden" landet - wir befassen uns nur mit Tetrominos, die auf anderen Tetrominos landen.

Hierfür gibt es eine ziemlich einfache Lösung: Wenn wir nach möglichen Kollisionen suchen, prüfen wir auch, ob die potenzielle neue Position jedes Blocks unter dem unteren Rand des Spielfelds liegt:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            if (row + tetromino.potentialTopLeft.row >= landed.length) {
                //this block would be below the playing field
            }
            else if (landed[row + tetromino.potentialTopLeft.row] != 0 &&
                landed[col + tetromino.potentialTopLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Wenn ein Block im Tetromino unter dem unteren Rand des Spielfelds landen würde, wenn er weiter fallen würde, machen wir den Tetromino natürlich "landen", so als würde ein Block einen Block überlappen, der bereits gelandet war.

Jetzt können wir mit einem neuen Tetromino in die nächste Runde starten.

Bewegen und drehen

Lassen Sie uns diesmal einen J-Tetromino spawnen:

1	tetromino.shape = [[0,1],
2	[0,1],
3	[1,1]];
4	tetromino.topLeft = {row: 0, col:4};

Rendern Sie es:

Denken Sie daran, dass der Tetromino jede halbe Sekunde um eine Reihe fallen wird. Nehmen wir an, der Spieler drückt viermal die linke Taste, bevor eine halbe Sekunde vergeht. Wir wollen das Tetromino jedes Mal um eine Spalte nach links verschieben.

Wie können wir sicherstellen, dass der Tetromino nicht mit einem der gelandeten Blöcke kollidiert? Wir können tatsächlich den gleichen Code wie zuvor verwenden!

Zunächst ändern wir die potenzielle neue Position:

1	tetromino.potentialTopLeft = {row: tetromino.topLeft, col: tetromino.topLeft - 1};

Jetzt prüfen wir, ob sich einer der Blöcke im Tetromino mit den gelandeten Blöcken überschneidet, und verwenden dabei dieselbe grundlegende Prüfung wie zuvor (ohne zu prüfen, ob ein Block unter das Spielfeld gefallen ist):

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            if (landed[row + tetromino.potentialTopLeft.row] != 0 &&
                landed[col + tetromino.potentialTopLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Führen Sie die gleichen Überprüfungen durch, die wir normalerweise durchführen, und Sie werden sehen, dass dies einwandfrei funktioniert. Der große Unterschied besteht darin, dass wir uns daran erinnern müssen, die Blöcke des Tetromino nicht zum landed[]-Array hinzuzufügen, wenn eine mögliche Kollision vorliegt. Stattdessen sollten wir den Wert von tetromino.topLeft einfach nicht ändern.

Jedes Mal, wenn der Spieler den Tetromino bewegt, sollten wir alles neu rendern. Hier ist das endgültige Ergebnis:

Was passiert, wenn der Spieler noch einmal nach links schlägt? Wenn wir das nennen:

1	tetromino.potentialTopLeft = {row: tetromino.topLeft, col: tetromino.topLeft - 1};

...wir werden am Ende versuchen, tetromino.potentialTopLeft.col auf -1 zu setzen - und das wird später zu allen möglichen Problemen führen.

Lassen Sie uns unsere bestehende Kollisionsprüfung ändern, um dies zu beheben:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            if (col + tetromino.potentialTopLeft.col < 0) {
                //this block would be to the left of the playing field
            }
            if (landed[row + tetromino.potentialTopLeft.row] != 0 &&
                landed[col + tetromino.potentialTopLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Einfach - es ist die gleiche Idee wie wenn wir prüfen, ob einer der Blöcke unter das Spielfeld fällt.

Beschäftigen wir uns auch mit der rechten Seite:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            if (col + tetromino.potentialTopLeft.col < 0) {
                //this block would be to the left of the playing field
            }
            if (col + tetromino.potentialTopLeft.col >= landed[0].length) {
                //this block would be to the right of the playing field
            }
            if (landed[row + tetromino.potentialTopLeft.row] != 0 &&
                landed[col + tetromino.potentialTopLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Wenn sich der Tetromino außerhalb des Spielfelds bewegen würde, ändern wir tetromino.topLeft einfach nicht - Sie müssen nichts weiter tun.

Okay, eine halbe Sekunde muss inzwischen vergangen sein, also lassen wir diesen Tetromino eine Reihe fallen:

1	tetromino.shape = [[0,1],
2	[0,1],
3	[1,1]];
4	tetromino.topLeft = {row: 1, col:0};

Angenommen, der Spieler drückt den Knopf, um den Tetromino im Uhrzeigersinn drehen zu lassen. Dies ist eigentlich ziemlich einfach zu handhaben - wir ändern nur tetromino.shape, ohne tetromino.topLeft zu ändern:

1	tetromino.shape = [[1,0,0],
2	[1,1,1]];
3	tetromino.topLeft = {row: 1, col:0};

Wir könnten etwas Mathematik verwenden, um den Inhalt des Array von Blöcken zu drehen... aber es ist viel einfacher, nur die vier möglichen Umdrehungen jedes Tetrominos irgendwo zu speichern, wie folgt:

1	jTetromino.rotations = [
2	[[0,1],
3	[0,1],
4	[1,1]],
5	[[1,0,0],
6	[1,1,1]],
7	[[1,1],
8	[1,0],
9	[1,0]],
10	[[1,1,1],
11	[0,0,1]]
12	];

(Ich lasse Sie herausfinden, wo Sie das am besten in Ihrem Code speichern können!)

Sobald wir alles wieder rendern, sieht es jedenfalls so aus:

Wir können es wieder drehen (und nehmen wir an, wir machen beide Umdrehungen innerhalb einer halben Sekunde):

1	tetromino.shape = [[1,1],
2	[1,0],
3	[1,0]];
4	tetromino.topLeft = {row: 1, col:0};

Nochmals rendern:

Wunderbar. Lassen wir es noch ein paar Zeilen fallen, bis wir zu diesem Zustand kommen:

1	tetromino.shape = [[1,1],
2	[1,0],
3	[1,0]];
4	tetromino.topLeft = {row: 10, col:0};

Plötzlich drückt der Spieler ohne ersichtlichen Grund erneut auf die Schaltfläche Im Uhrzeigersinn drehen. Wenn wir uns das Bild ansehen, können wir sehen, dass dies nichts zulassen sollte, aber wir haben noch keine Kontrollen durchgeführt, um dies zu verhindern.

Sie können wahrscheinlich erraten, wie wir das lösen werden. Wir werden eine tetromino.potentialShape einführen, sie auf die Form des gedrehten Tetromino einstellen und nach möglichen Überlappungen mit bereits gelandeten Blöcken suchen.

tetromino.shape = [[1,1],
                   [1,0],
                   [1,0]];
tetromino.topLeft = {row: 10, col:0};
tetromino.potentialShape = [[1,1,1],
                            [0,0,1]];

for (var row = 0; row < tetromino.potentialShape.length; row++) {
    for (var col = 0; col < tetromino.potentialShape[row].length; col++) {
        if (tetromino.potentialShape[row][col] != 0) {
            if (col + tetromino.topLeft.col < 0) {
                //this block would be to the left of the playing field
            }
            if (col + tetromino.topLeft.col >= landed[0].length) {
                //this block would be to the right of the playing field
            }
            if (row + tetromino.topLeft.row >= landed.length) {
                //this block would be below the playing field
            }
            if (landed[row + tetromino.topLeft.row] != 0 &&
                landed[col + tetromino.topLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Wenn es eine Überlappung gibt (oder wenn die gedrehte Form teilweise außerhalb der Grenzen liegt), lassen wir den Block einfach nicht drehen. Somit kann es eine halbe Sekunde später einrasten und dem landed[] Array hinzugefügt werden:

Ausgezeichnet.

Alles gerade halten

Um klar zu sein, haben wir jetzt drei separate Prüfungen.

Die erste Prüfung gilt für den Fall, dass ein Tetromino fällt, und wird jede halbe Sekunde aufgerufen:

//set tetromino.potentialTopLeft to be one row below tetromino.topLeft, then:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            if (row + tetromino.potentialTopLeft.row >= landed.length) {
                //this block would be below the playing field
            }
            else if (landed[row + tetromino.potentialTopLeft.row] != 0 &&
                landed[col + tetromino.potentialTopLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Wenn alle Prüfungen bestanden sind, setzen wir tetromino.topLeft auf tetromino.potentialTopLeft.

Wenn eine der Prüfungen fehlschlägt, lassen wir das Tetromino wie folgt landen:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            landed[row + tetromino.topLeft.row][col + tetromino.topLeft.col] = tetromino.shape[row][col];
        }
     }
}

Die zweite Prüfung gilt für den Fall, dass der Spieler versucht, den Tetromino nach links oder rechts zu bewegen, und wird aufgerufen, wenn der Spieler die Bewegungstaste drückt:

//set tetromino.potentialTopLeft to be one column to the right or left
//of tetromino.topLeft, as appropriate, then:

for (var row = 0; row < tetromino.shape.length; row++) {
    for (var col = 0; col < tetromino.shape[row].length; col++) {
        if (tetromino.shape[row][col] != 0) {
            if (col + tetromino.potentialTopLeft.col < 0) {
                //this block would be to the left of the playing field
            }
            if (col + tetromino.potentialTopLeft.col >= landed[0].length) {
                //this block would be to the right of the playing field
            }
            if (landed[row + tetromino.potentialTopLeft.row] != 0 &&
                landed[col + tetromino.potentialTopLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Wenn (und nur wenn) alle diese Prüfungen erfolgreich sind, setzen wir tetromino.topLeft auf tetromino.potentialTopLeft.

Die dritte Prüfung gilt für den Fall, dass der Spieler versucht, den Tetromino im oder gegen den Uhrzeigersinn zu drehen, und wird aufgerufen, wenn der Spieler die Taste drückt, um dies zu tun:

//set tetromino.potentialShape to be the rotated version of tetromino.shape 
//(clockwise or anti-clockwise as appropriate), then:

for (var row = 0; row < tetromino.potentialShape.length; row++) {
    for (var col = 0; col < tetromino.potentialShape[row].length; col++) {
        if (tetromino.potentialShape[row][col] != 0) {
            if (col + tetromino.topLeft.col < 0) {
                //this block would be to the left of the playing field
            }
            if (col + tetromino.topLeft.col >= landed[0].length) {
                //this block would be to the right of the playing field
            }
            if (row + tetromino.topLeft.row >= landed.length) {
                //this block would be below the playing field
            }
            if (landed[row + tetromino.topLeft.row] != 0 &&
                landed[col + tetromino.topLeft.col] != 0) {
                //the space is taken
            }
        }
     }
}

Wenn (und nur wenn) alle diese Prüfungen erfolgreich sind, setzen wir tetromino.shape auf tetromino.potentialShape.

Vergleichen Sie diese drei Prüfungen - es ist leicht, sie zu verwechseln, da der Code sehr ähnlich ist.

Andere Probleme

Formabmessungen

Bisher habe ich verschiedene Größen von Arrays verwendet, um die verschiedenen Formen von Tetrominos (und die verschiedenen Rotationen dieser Formen) darzustellen: Das O-Tetromino verwendete ein 2x2-Array und das J-Tetromino ein 3x2- oder ein 2x3-Array.

Aus Gründen der Konsistenz empfehle ich, für alle Tetrominos (und deren Rotationen) die gleiche Arraygröße zu verwenden. Angenommen, Sie halten sich an die sieben Standard-Tetrominoes, dann können Sie dies mit einem 4x4-Array tun.

Es gibt verschiedene Möglichkeiten, die Rotationen innerhalb dieses 4x4-Quadrats anzuordnen. Werfen Sie einen Blick auf das Tetris-Wiki, um weitere Informationen zu den verschiedenen Spielen zu erhalten.

Wandtritt

Angenommen, Sie stellen ein vertikales I-Tetromino wie folgt dar:

1	[[0,1,0,0],
2	[0,1,0,0],
3	[0,1,0,0],
4	[0,1,0,0]];

...und Sie stellen seine Rotation folgendermaßen dar:

1	[[0,0,0,0],
2	[0,0,0,0],
3	[1,1,1,1],
4	[0,0,0,0]];

Angenommen, ein vertikaler I-Tetromino wird wie folgt gegen eine Wand gedrückt:

Was passiert, wenn der Spieler die Drehtaste drückt?

Nun, mit unserem aktuellen Kollisionserkennungscode passiert nichts - der Block ganz links des horizontalen I-Tetromino würde außerhalb der Grenzen liegen.

Dies ist wohl in Ordnung - so hat es in der NES-Version von Tetris funktioniert -, aber es gibt eine Alternative: Drehen Sie den Tetromino und verschieben Sie ihn, sobald Sie ein Leerzeichen nach rechts haben, wie folgt:

Ich lasse Sie die Details herausfinden, aber im Wesentlichen müssen Sie überprüfen, ob durch Drehen des Tetromino es außerhalb der Grenzen verschoben wird, und wenn ja, verschieben Sie es nach Bedarf um ein oder zwei Felder nach links oder rechts. Sie müssen jedoch daran denken, nach dem Anwenden der Drehung und der Bewegung auf mögliche Kollisionen mit anderen Blöcken zu prüfen!

Verschiedene farbige Blöcke

Ich habe in diesem Tutorial Blöcke mit derselben Farbe verwendet, um die Dinge einfach zu halten, aber es ist einfach, die Farben zu ändern.

Wählen Sie für jede Farbe eine Zahl aus, um sie darzustellen. Verwenden Sie diese Zahlen in Ihrer shape[] und landed[] Arrays. Ändern Sie dann Ihren Rendering-Code in Farbblöcke basierend auf deren Nummern.

Das Ergebnis könnte ungefähr so aussehen:

Abschluss

Das Trennen der visuellen Darstellung eines Objekts im Spiel von seinen Daten ist ein wirklich wichtiges Konzept, um es zu verstehen. es kommt in anderen Spielen immer wieder vor, insbesondere wenn es um die Kollisionserkennung geht.

In meinem nächsten Beitrag werden wir uns ansehen, wie die andere Kernfunktion von Tetris implementiert wird: Entfernen von Zeilen, wenn diese gefüllt sind. Danke fürs Lesen!