sábado, 27 de octubre de 2012

Implementing Tetris: Collision Detection

This entry is part 1 of 2 in the series Implementing Tetris

I’m sure it’s possible to create a Tetris game with a point-and-click gamedev tool, but I could never figure out how. Today, I’m more comfortable thinking at a higher level of abstraction, where the tetromino you see onscreen is only a representation of what’s going on in the underlying game. In this tutorial I’ll show you what I mean, by demonstrating how to handle collision detection in Tetris.

Note: Although the code in this tutorial is written using AS3, you should be able to use the same techniques and concepts in almost any game development environment.


The Grid

A standard Tetris playing field has 16 rows and 10 columns. We can represent this in a multidimensional array, containing 16 sub-arrays of 10 elements:

Imagine the image on the left is a screenshot from the game – it’s how the game might look to the player, after a tetromino has landed but before another has been spawned.

On the right is an array representation of the game’s current state. Let’s call it landed[], as it refers to all of the blocks that have landed. An element of 0 means that no block occupies that space; 1 means that a block has landed in that space.

Now let’s spawn an O-tetromino in the centre at the top of the field:

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

The shape property is another multidimensional array representation of the shape of this tetromino. topLeft gives the position of the top-left block of the tetromino: at the top row, and the fifth column in.

We render everything. First, we draw the background – this is easy, it’s just a static grid image.

Next, we draw every block from the 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          }       }  }  

My block images are 20x20px, so to draw the blocks I could just insert a new block image at (col * 20, row * 20). The details don’t really matter.

Next, we draw every block in the current 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          }       }  }  

We can use the same drawing code here, but we need to offset the blocks by topLeft.

Here’s the result:

Implementing Tetris: Collision Detection

Note that the new O-tetromino doesn’t appear in the landed[] array – that’s because, well, it hasn’t landed yet.


Falling

Suppose the player doesn’t touch the controls. At regular intervals – let’s say every half-second – the O-tetromino needs to fall down one row.

It’s tempting to just call:

  tetromino.topLeft.row++;  

…and then render everything again, but this won’t detect any overlaps between the O-tetromino and the blocks that have already landed.

Instead, we’ll check for potential collisions first, and then only move the tetromino if it’s “safe”.

For this, we’ll need to define a potential new position for the tetromino:

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

Now we check for collisions. The simplest way to do this is to loop through all the spaces in the grid that the tetromino would take up in its potential new position, and check the landed[] array to see if they’re already taken:

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

Let’s test this out:

  tetromino.shape = [[1,1],                     [1,1]];  tetromino.potentialTopLeft: {row: 1, col: 4}  --------------------------------------------  row: 0, col: 0, tetromino.shape[0][0]: 1, landed[0+1][0+4]: 0  row: 0, col: 1, tetromino.shape[0][1]: 1, landed[0+1][1+4]: 0  row: 1, col: 0, tetromino.shape[1][0]: 1, landed[1+1][0+4]: 0  row: 1, col: 1, tetromino.shape[1][1]: 1, landed[1+1][1+4]: 0  

All zeroes! This means there’s no collision, so the tetromino can move.

We set:

  tetromino.topLeft = tetromino.potentialTopLeft;  

…and then render everything again:

Implementing Tetris: Collision Detection

Great!


Landing

Now, suppose the player lets the tetromino fall to this point:

Implementing Tetris: Collision Detection

The top-left is at {row: 11, col: 4}. We can see that the tetromino would collide with the landed blocks if it fell any more – but does our code figure it out? Let’s see:

  tetromino.shape = [[1,1],                     [1,1]];  tetromino.potentialTopLeft: {row: 12, col: 4}  --------------------------------------------  row: 0, col: 0, tetromino.shape[0][0]: 1, landed[0+12][0+4]: 0  row: 0, col: 1, tetromino.shape[0][1]: 1, landed[0+12][1+4]: 0  row: 1, col: 0, tetromino.shape[1][0]: 1, landed[1+12][0+4]: 1  row: 1, col: 1, tetromino.shape[1][1]: 1, landed[1+12][1+4]: 0  

There’s a 1, which means there’s a collision – specifically, the tetromino would collide with the block at landed[13][4].

This means that the tetromino has landed, which means we need to add it to the landed[] array. We can do this with a very similar loop to the one we used to check for potential collisions:

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

Here’s the result:

Implementing Tetris: Collision Detection

So far so good. But you may have noticed that we don’t deal with the case where the tetromino lands on the “ground” – we only deal with tetrominoes landing on top of other tetrominoes.

There’s a pretty simple fix for this: when we check for potential collisions, we also check whether the potential new position of each block would be below the bottom of the playing field:

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

Of course, if any block in the tetromino would end up below the bottom of the playing field if it fell any further, we make the tetromino “land”, just as if any block would overlap a block that had already landed.

Now we can start the next round, with a new tetromino.


Moving and Rotating

This time, let’s spawn a J-tetromino:

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

Render it:

Implementing Tetris: Collision Detection

Remember, every half-second, the tetromino is going to fall by one row. Let’s suppose the player hits the Left key four times before half a second passes; we want to move the tetromino left by one column each time.

How can we make sure that the tetromino won’t collide with any of the landed blocks? We can actually use the same code from before!

First, we alter the potential new position:

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

Now, we check whether any of the blocks in the tetromino overlap with the landed blocks, using the same basic check as before (without bothering to check whether any block has gone below the playing field):

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

Run it through the same checks we usually perform and you’ll see that this works fine. The big difference is, we must remember not to add the tetromino’s blocks to the landed[] array if there is a potential collision – instead, we should simply not change the value of tetromino.topLeft.

Each time the player moves the tetromino, we should re-render everything. Here’s the eventual result:

Implementing Tetris: Collision Detection

What happens if the player hits left once more? When we call this:

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

…we’ll end up trying to set tetromino.potentialTopLeft.col to -1 – and that will lead to all sorts of problems later.

Let’s modify our existing collision check to deal with this:

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

Simple – it’s the same idea as when we check whether any of the blocks would fall below the playing field.

Let’s deal with the right-hand side, as well:

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

Again, if the tetromino would move outside of the playing field, we just don’t alter tetromino.topLeft – no need to do anything else.

Okay, half a second must have passed by now, so let’s let that tetromino fall one row:

  tetromino.shape = [[0,1],                     [0,1],                     [1,1]];  tetromino.topLeft = {row: 1, col:0};  
Implementing Tetris: Collision Detection

Now, suppose the player hits the button to make the tetromino rotate clockwise. This is actually pretty easy to deal with – we just alter tetromino.shape, without altering tetromino.topLeft:

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

We could use some maths to rotate the contents of the array of blocks… but it’s much simpler just to store the four possible rotations of each tetromino somewhere, like this:

  jTetromino.rotations = [      [[0,1],       [0,1],       [1,1]],      [[1,0,0],       [1,1,1]],      [[1,1],       [1,0],       [1,0]],      [[1,1,1],       [0,0,1]]  ];  

(I’ll let you figure out where best to store that in your code!)

Anyway, once we render everything again, it’ll look like this:

Implementing Tetris: Collision Detection

We can rotate it again (and let’s assume we do both these rotations within half a second):

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

Render again:

Implementing Tetris: Collision Detection

Wonderful. Let’s let it drop a few more rows, until we get to this state:

  tetromino.shape = [[1,1],                     [1,0],                     [1,0]];  tetromino.topLeft = {row: 10, col:0};  
Implementing Tetris: Collision Detection

Suddenly, the player hits the Rotate Clockwise button again, for no apparent reason. We can see from looking at the picture that this shouldn’t allow anything to happen, but we don’t have any checks in place yet to prevent it.

You can probably guess how we’re going to solve this. We’ll introduce a tetromino.potentialShape, set it to the shape of the rotated tetromino, and look for any potential overlaps with blocks that have already landed.

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

If there is an overlap (or if the rotated shape would be partly out of bounds), we simply don’t allow the block to rotate. Thus, it can fall into place half a second later, and get added to the landed[] array:

Implementing Tetris: Collision Detection

Excellent.


Keeping It All Straight

To be clear, we now have three separate checks.

The first check is for when a tetromino falls, and is called every half-second:

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

If all of the checks pass, then we set tetromino.topLeft to tetromino.potentialTopLeft.

If any of the checks fail, then we make the tetromino land, like so:

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

The second check is for when the player tries to move the tetromino left or right, and is called when the player hits the movement key:

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

If (and only if) all of these checks pass, we set tetromino.topLeft to tetromino.potentialTopLeft.

The third check is for when the player tries to rotate the tetromino clockwise or anti-clockwise, and is called when the player hits the key to do so:

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

If (and only if) all of these checks pass, we set tetromino.shape to tetromino.potentialShape.

Compare these three checks – it’s easy to get them mixed up, because the code is very similar.


Other Issues

Shape Dimensions

So far, I’ve used different sizes of arrays for representing the different shapes of tetrominoes (and the different rotations of those shapes): the O-tetromino used a 2×2 array, and the J-tetromino used a 3×2 or a 2×3 array.

For consistency, I recommend using the same size of array for all the tetrominoes (and rotations thereof). Assuming you’re sticking with the seven standard tetrominoes, you can do this with a 4×4 array.

There are several different ways you can arrange the rotations within this 4×4 square; take a look at the Tetris Wiki for more information on what different games use.

Wall Kicking

Suppose you represent a vertical I-tetromino like this:

  [[0,1,0,0],   [0,1,0,0],   [0,1,0,0],   [0,1,0,0]];  

…and you represent its rotation like this:

  [[0,0,0,0],   [0,0,0,0],   [1,1,1,1],   [0,0,0,0]];  

Now suppose a vertical I-tetromino is pressed up against a wall like this:

Implementing Tetris: Collision Detection

What happens if the player hits the Rotate key?

Well, using our current collision detection code, nothing happens – the leftmost block of the horizontal I-tetromino would be outside of the boundaries.

This is arguably fine – that’s how it worked in the NES version of Tetris – but there is an alternative: rotate the tetromino, and move it once space to the right, like so:

Implementing Tetris: Collision Detection

I’ll let you figure out the details, but essentially you need to check whether rotating the tetromino would move it out of bounds and, if so, move it left or right one or two spaces as necessary. However, you must remember to check for potential collisions with other blocks after applying both the rotation and the movement!

Different Coloured Blocks

I’ve used blocks of all the same colour throughout this tutorial to keep things simple, but it’s easy to change the colours.

For each colour, pick a number to represent it; use those numbers in your shape[] and landed[] arrays; then alter your rendering code to colour blocks based on their numbers.

The result might look something like this:

Implementing Tetris: Collision Detection

Conclusion

Separating the visual representation of an in-game object from its data is a really important concept to understand; it comes up again and again in other games, particularly when dealing with collision detection.

In my next post, we’ll look at how to implement the other core feature of Tetris: removing lines when they are filled. Thanks for reading!



No hay comentarios:

Publicar un comentario