Tile-based games having been there for so long, there are a whole bunch of different techniques developers have used to implement collision detection in their games. While learning the subject myself, I came across this brilliant article written by a programmer named Rodrigo Monteiro (http://higherorderfun.com/blog/). He has described a few of the techniques used for tile-based collision detection and cataloged a lot of information on them in the article, which you can find here: http://higherorderfun.com/blog/2012/05/20/the-guide-to-implementing-2d-platformers/.

The algorithm we will be using is based on the pseudo code that Rodrigo describes in the article. The reason we are discussing collision detection before any of the other gameplay is because this algorithm is flexible in nature and can be plugged in to any other tile-based game with little or no modifications necessary. It can be used even in games that are not made with Tiled. I can vouch for this, having used this very algorithm in three of my own games.

The algorithm is divided into two parts: vertical and horizontal collision detection. This has been done so that you can understand it easily, and I strongly advise you to combine both the vertical and horizontal algorithms into one as they are quite similar. For the purpose of collision detection, each character will be represented by an axis aligned bounding box (AABB). AABBs are nothing but rectangles that do not rotate.

The algorithm will check for conditions of intersection between such AABBs and tiles that qualify for collisions. Before we dive into the code, let's take a look at the process for vertical collision detection:

This pseudo code is given full form in the CheckVerticalCollisions function of GameWorld.cpp. We will discuss the implementation in steps like the preceding pseudo code:

bool GameWorld::CheckVerticalCollisions(GameObject* game_object)
{
  int visible_rows = (int)tiled_map_->getMapSize().height;
  int visible_cols = (int)tiled_map_->getMapSize().width;

  CCRect aabb = game_object->GetAABB();
  CCPoint speed = game_object->GetSpeed();

  // since we're checking vertically, save the row occupied by the aabb
  int aabb_row = GET_ROW_FOR_Y(aabb.origin.y, visible_rows);
  if(speed.y > 0)
  {
    // if we're going up, save the row occupied by the top edge of the aabb
    aabb_row = GET_ROW_FOR_Y(aabb.origin.y + 
      aabb.size.height, visible_rows);
  }

We begin the function by storing the size of the map and also the AABB for the GameObject class passed in as parameter. This algorithm simply needs an AABB. However, we have passed it a reference to the GameObject class so it can call the collision response function. In the first step, we check the speed_ variable to determine whether we are moving upwards or downwards and calculate the row occupied by the forward edge of the AABB, storing it into variable aabb_row.

The GET_ROW_FOR_Y function is a helper macro that returns the row at a given point. You can find this macro and a few more in GameGlobals.h.

Let's take a look at the following code:

  // also save the columns occupied by the left & right edges of the aabb
  int aabb_start_col = GET_COL_FOR_X(aabb.origin.x);
  int aabb_end_col = GET_COL_FOR_X(aabb.origin.x + aabb.size.width);

  // bounds checking
  if(aabb_row < 0 || aabb_row >= visible_rows ||
      aabb_start_col < 0 || aabb_start_col >= visible_cols ||
      aabb_end_col < 0 || aabb_end_col >= visible_cols)
    return false;

  // initialise flags & counters
  bool found_collidable = false;
  int current_col = aabb_start_col;
  int current_row = aabb_row;

In the second step, we call another macro by the name GET_COL_FOR_X and pass in the left and right end points of the AABB to get the left and right columns. These are stored into the variables aabb_start_col and aabb_end_col respectively.

We then ensure that we're not checking outside the tile map, because querying the tile map for tiles that are beyond its bounds will result in an assert. We also initialize a few flags and counters.

Let's take a look at the following code:

while(current_row >= 0 && current_row < visible_rows)
{
  // check for every column that the aabb occupies
  for(current_col = aabb_start_col; current_col <= aabb_end_col; ++current_col)
  {
    // check if a brick exists at the given row & column
    if(bricks_layer_->tileGIDAt(ccp(current_col, current_row)))
    {
      found_collidable = true;
      break;
    }
  }

  // from current tile, keep moving in same direction till a brick is found
  if(found_collidable == false)
  {
    current_row = (speed.y < 0) ? (current_row + 1):(current_row - 1);
  }

As you read in the pseudo code, we must scan from the left column to the right column for each row in the direction of movement. Thus, we start a while loop that will iterate through each row within the bounds of the map, starting from current_row. Inside this loop, we add a for loop that checks from each tile from the left column to the right column for this particular row. We can now use the values contained within current_col and current_row to check if a brick exists at that particular tile by calling the tileGIDAt function on the bricks_layer_ object. If a tile has been found, then we break out of this for loop.

Outside the for loop, the variable found_collidable is checked to determine whether we need to keep scanning for collision tiles or should we move ahead to the collision response. Thus, if found_collidable is false, we decrement or increment current_row, depending on whether this particular GameObject class wants to move up or down respectively. Read that again! We decrement the row if we want to move up and increment to move down. That is because Tiled treats the top-left corner as the origin while placing its tiles.

That winds up the third step, and at this point, the found_collidable variable tells us whether a collision tile has been found. If a collision tile has indeed been found, then the variables current_col and current_row can be used to identify it. Let's now move to the next step, which will wrap up the vertical collision checking function:

if(found_collidable)
{
  // going down
  if(speed.y < 0)
  {
    // if the bottom edge of aabb is lower than the top edge of 
     the collidable row
    if(aabb.origin.y <= GET_Y_FOR_ROW(current_row, visible_rows))
    {
      // its a collision, do something
      game_object->CollisionResponse(current_col, current_row, 
        E_COLLISION_BOTTOM);
    }
    else
    {
      // not a collision
      found_collidable = false;
    }
  }
  // going up
  else
  {
    // if the top edge of aabb is higher than the bottom edge of 
     the collidable row
    if((aabb.origin.y + aabb.size.height) >= GET_Y_FOR_ROW(
      current_row + 1, visible_rows))
    {
      // its a collision, do something
      game_object->CollisionResponse(current_col, current_row, 
        E_COLLISION_TOP);
    }
    else
    {
      // not a collision
      found_collidable = false;
    }
  }
}

return found_collidable;

This block of code executes only if a collision tile has been found. In that case, based on whether we're going up or down, the y component of the respective AABB edge is compared with the y component of the respective upper or lower row. If the values indicate an overlap or intersection, we have found a collision and we call the respective collision response function, passing in the column and row of the collision tile while also specifying whether the collision occurred above or below AABB.

Inside GameWorld.cpp, you will find a similar function by the name CheckHorizontalCollisions. Just like its name, even the definition of this function is similar to the CheckVerticalCollisions function. As such, I will only highlight the differences in the next paragraph. So make sure you read through the function from the source bundle for this chapter before moving ahead.

Since we're checking horizontally instead of vertically, we find the column instead of the row occupied by the forward-facing edge of AABB. Similarly, we find the start and end rows indicated by the top and bottom edges of AABB, respectively.

Throughout the function, we simply swap the rows with columns and it performs horizontal collision detection. The final difference between vertical and horizontal collision detection functions is the type of collision that we pass into the CollisionResponse function.

With these two functions, we have written a simple and reusable tile-based collision detection algorithm. If you want to see the algorithm in action, you should run the game in debug mode. You can do that by uncommenting the following line in GameGlobals.h:

#define ICEMAN_DEBUG_MODE

A few important lines of code elude us for the moment, that is, the collision response logic that we will get to when we define the hero's class, which we are just about to. But before that, we need to define a base class for the hero, enemy, and platform to inherit from.