Smashinglabs

3D Tetris with Three.js tutorial – part 4

Fourth part may be the most difficult so far. We will talk about collision detection.

Board object

We will start with a new class to store our 3D space information. We need few “const”, “enum” values. They are really neither const nor enum, as there are no such things in JS, but there is a new function in JS 1.8.5 – freeze. You can create an object and protect it from any further modification. It is widely supported in all browsers that may run WebGL and will give us enum-like objects.

window.Tetris = window.Tetris  || {};
Tetris.Board = {};

Tetris.Board.COLLISION = {NONE:0, WALL:1, GROUND:2};
Object.freeze(Tetris.Board.COLLISION);

Tetris.Board.FIELD = {EMPTY:0, ACTIVE:1, PETRIFIED:2};
Object.freeze(Tetris.Board.FIELD);


We will use field enum to store state of our board in fields array. On game start we need to initialize it as empty.

Tetris.Board.fields = [];

Tetris.Board.init = function(_x,_y,_z) {
for(var x = 0; x < _x; x++) {
Tetris.Board.fields[x] = [];
for(var y = 0; y < _y; y++) {
Tetris.Board.fields[x][y] = [];
for(var z = 0; z < _z; z++) {
Tetris.Board.fields[x][y][z] = Tetris.Board.FIELD.EMPTY;
}
}
}
};


Tetris.Board.init() should be called before any block appears in game. I call it from Tetris.init, because we can easily provide board dimensions as parameters:

// add anywhere in Tetris.init
Tetris.Board.init(boundingBoxConfig.splitX, boundingBoxConfig.splitY, boundingBoxConfig.splitZ);


We should also modify Tetris.Block.petrify function, so that it stores information in our new array.

Tetris.Block.petrify = function () {
var shape = Tetris.Block.shape;
for (var i = 0; i < shape.length; i++) {
Tetris.addStaticBlock(Tetris.Block.position.x + shape[i].x, Tetris.Block.position.y + shape[i].y, Tetris.Block.position.z + shape[i].z);
Tetris.Board.fields[Tetris.Block.position.x + shape[i].x][Tetris.Block.position.y + shape[i].y][Tetris.Block.position.z + shape[i].z] = Tetris.Board.FIELD.PETRIFIED;
}
};


Collision detection

There are two main types of collisions in Tetris. First one is wall collision, when active block hits a wall or another block while being moved or rotated on x/y axes (e.g. on one level). Second one is ground collision which happens when block is moved on z-axis and hits floor or another block and it’s life cycle is finished.

We will start with board walls collision, which is quite easy. To make code nicer (and faster) I used shorthands again.

Tetris.Board.testCollision = function (ground_check) {
var x, y, z, i;

// shorthands
var fields = Tetris.Board.fields;
var posx = Tetris.Block.position.x, posy = Tetris.Block.position.y,
posz = Tetris.Block.position.z, shape = Tetris.Block.shape;

for (i = 0; i < shape.length; i++) {
// 4 walls detection for every part of the shape
if ((shape[i].x + posx) < 0 ||
(shape[i].y + posy) < 0 ||
(shape[i].x + posx) >= fields.length ||
(shape[i].y + posy) >= fields[0].length) {
return Tetris.Board.COLLISION.WALL;
}
// to be continued


Now how to deal with block-block collision? We already store petrified blocks in our array, so we can check if block is intersecting with any of existing cubes. You may wonder why testCollision has ground_check as an argument. It’s a result of a simple observation, that block-block collision is detected in almost the same way for ground and wall collision. The only distinction is movement on z-axis which should cause ground hit.

        if (fields[shape[i].x + posx][shape[i].y + posy][shape[i].z + posz - 1] === Tetris.Board.FIELD.PETRIFIED) {
return ground_check ? Tetris.Board.COLLISION.GROUND : Tetris.Board.COLLISION.WALL;
}
// to be continued


We will also test if position on z-axis in not equal to zero. That means that there are no cubes below our moving block, but it reached the ground level and should be petrified anyway.

        if((shape[i].z + posz) <= 0) {
return Tetris.Board.COLLISION.GROUND;
}
}
};


Collision reaction

It wasn’t so bad, was it? Now lets do something with information we have. We will start in the easiest place, detection of the lost game. We can do it by testing if there is a collision immediately after creating a new block. If it hits the ground, there is no point in playing further.

Add to Tetris.Block.generate after block position is calculated:

    if (Tetris.Board.testCollision(true) === Tetris.Board.COLLISION.GROUND) {
Tetris.gameOver = true;
Tetris.pointsDOM.innerHTML = "GAME OVER";
Cufon.replace('#points');
}


Movement is also simple. After we change a position we call collision detection, passing the information about z-axis movement as an argument.

If there is a wall collision the move was impossible and we should undo it. We could add few lines to subtract position but I’m lazy and I prefer to call the move function again, but with inverted arguments. It will be never used with z-axis movement so we can pass a zero as z.

If the shape hits the ground, we already have a function hitBottom() that should be called. It will remove active shape from the game, modify board state and create a new shape.

    // add instead of ground level detection from part 3
var collision = Tetris.Board.testCollision((z != 0));
if (collision === Tetris.Board.COLLISION.WALL) {
Tetris.Block.move(-x, -y, 0); // laziness FTW
}
if (collision === Tetris.Board.COLLISION.GROUND) {
Tetris.Block.hitBottom();
}


And now comes the crazy part. If you run game at this point, you will notice that rotating shape is not permanent. When it hits the ground, it returns to the initial rotation. That’s because we apply rotation to the Three.js mesh (as Tetris.Block.mesh.rotation) but we don’t use it to get coordinates of our cube-based shape representation. To deal with it we need to go through a quick math lesson.

3D math

DISCLAIMER: If you are afraid of math or have little time, you can actually skip this part. It’s important to know what happens inside your engine, but later we will use a Three.js functions for that.

Consider a 3-element vector (which represents position in 3D space). To transform such vector in euclidean space we have to add another vector. It can be represented as:

$\begin{matrix}x\\y\\z\\\end{matrix}\ + \begin{matrix}\delta x\\\delta y\\\delta z\\\end{matrix} = \begin{matrix}x’\\ y’\\ z’\\\end{matrix}$

It’s fairly simple. The problem appears when we would like to rotate a vector. Rotation around a single axis affects two of the three coordinates (check if you don’t believe) and equations aren’t that simple. Luckily, there is one method used in almost all computer generated graphics, including Three.js, WebGL, OpenGL and GPU itself. If you remember from high school, multiplying a vector by matrix will result in another vector. There is a number of transformations based on that. The easiest one is neutral transformation (using identity matrix) that does nothing but shows general idea and is used as a base for other transformations.

$\begin{matrix}x\\y\\z\\w\\\end{matrix}\ * \begin{matrix} 1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\end{matrix}\ = \begin{matrix}x\\y\\z\\w\\\end{matrix}$

Why do we use 4×4 matrices and 4-element vectors instead of 3×3 and 3-elements? It’s used to enable translation by a vector:

$\begin{matrix}x\\y\\z\\w\\\end{matrix}\ * \begin{matrix} 1 & 0 & 0 & \delta x\\0 & 1 & 0 & \delta y\\0 & 0 & 1 & \delta z\\0 & 0 & 0 & 1\end{matrix}\ = \begin{matrix}x’\\y’\\z’\\w’\\\end{matrix}$

It’s a nice math trick that makes all equations easier. It also helps with numerical errors and enables us to use even more advanced concepts like quaternions.

Scaling is also simple:

$\begin{matrix}x\\y\\z\\w\\\end{matrix}\ * \begin{matrix} sx & 0 & 0 & 0\\ 0 & sy & 0 & 0\\ 0 & 0 & sz & 0\\ 0 & 0 & 0 & 1 \end{matrix}= \begin{matrix}x * sx\\y * sy\\z * sz\\w’\\\end{matrix}$

There are three matrices for rotations, one for every axis.

For x-axis

$\begin{matrix} 1 & 0 & 0 & 0\\ 0 & cos \alpha & -sin \alpha & 0\\ 0 & sin \alpha & cos \alpha & 0\\ 0 & 0 & 0 & 1 \end{matrix}$

For y-axis

$\begin{matrix} cos \alpha & 0 & sin \alpha & 0\\ 0 & 1 & 0 & 0\\ -sin \alpha & 0 & cos \alpha & 0\\ 0 & 0 & 0 & 1 \end{matrix}$

For z-axis

$\begin{matrix} cos \alpha & -sin \alpha & 0 & 0\\ sin \alpha & cos \alpha & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{matrix}$

Another great thing about matrix transformations is that we can easily combine two transformations by multiplying its matrices. If you want to rotate around all three axes, you can multiply three matrices and get something called transformation matrix. It will easily transform a vector that represents a position.

If you are interested in writing your own math library, you can read this tutorial on blog-o-ben. Very good introduction to math and pure WebGL. You may also need to read some good book about physics or graphics. I recommend Ian Millington’s Game Physics Engine Development.

Luckily most of the times you don’t have to work on that. Three.js already has a built in math library and we are going to use it.

Back to rotation

To rotate a shape in Three.js we need to create a rotation matrix and multiply it with shape’s every vector. We will use cloneVector again to make sure that created shape is independent from the one stored as a pattern.

    // append to Tetris.Block.rotate()
var rotationMatrix = new THREE.Matrix4();
rotationMatrix.setRotationFromEuler(Tetris.Block.mesh.rotation);

for (var i = 0; i < Tetris.Block.shape.length; i++) {
Tetris.Block.shape[i] = rotationMatrix.multiplyVector3(
Tetris.Utils.cloneVector(Tetris.Block.shapes[this.blockType][i])
);
Tetris.Utils.roundVector(Tetris.Block.shape[i]);
}
// to be continued


There is one problem with rotation matrix and our representation of the board. Fields are represented as an array which is indexed by integers, while a result of matrix-vector multiplication may be a float. JavaScript is not very good with floating point numbers and it’s almost sure that it will produce positions like 1.000001 or 2.999998. This is why we need a rounding function.

Tetris.Utils.roundVector = function(v) {
v.x = Math.round(v.x);
v.y = Math.round(v.y);
v.z = Math.round(v.z);
};


When we have our shape rotated, it’s very simple to check if collision occurs. I used the same trick with undoing rotation by calling function again, but with inverted parameters. Please note, that collision will never occur when undoing a move. If you want, you can add additional parameter so it won’t be checked again when not needed.

    // append to Tetris.Block.rotate()
if (Tetris.Board.testCollision(false) === Tetris.Board.COLLISION.WALL) {
Tetris.Block.rotate(-x, -y, -z); // laziness FTW
}


Summary

Our Tetris is almost completed. Playing it is already some fun. In following parts of tutorial we will focus on adding more juice to the game – there will be scoring system, some HTML5 audio and eye candies.

After this tutorial you should:

• Know what enum is and how to emulate it in JavaScript.
• Know how to detect different types of collision in Tetris.
• Be familiar with shorthands for
• if conditional: test ? if_true : if_false
• long scope resolution: var tmpVal = some.long.obj.val
• boolean as a parameter: myFunc((foo === 42))
• Understand 3D math – transforming vectors (positions) with matrices.

If you have trouble with any of these, check tutorial again or ask a question in the comments below.

2 Responses so far.

1. jeff says:

Excellent work, just one small thing to point out:

Consider a 3-element vector (which represents position in 3D space).

It isn’t actually a position in space!!

2. Stargazer says:

and btw …the link to the fifth part doesn’t seem to work from here

This came as a surprise for me but gMap is ...

gMap 3.3.3 released

It was a looong time since I last visited gMap. ...

Two new slide decks appeared in lectures tab. This time with ...

Talks and lectures w

Every now and then I spend a weekend watching various ...

3D Tetris with Three

In the fifth part of tutorial we add some final ...

This came as a surprise for me but gMap is ...

gMap 3.3.0 released

Christmas came early! New version of gMap is ready!

Lecture for GTUG: Ja

Today I gave a lecture for GTUG Krakow about optimizations in ...

Unit testing for jQu

In part 1 I described basics of unit testing in ...

Unit testing for jQu

In part 1 I described some basic concepts behind unit ...