Rotating Tower Collision Detection

Sun, Nov 10, 2013

In this final article in the rotating tower series, I’m going to talk about collision detection.

In the previous article I talked about how to render a traditional 2-dimensional platform game as a rotating tower, and showed how, with just a few changes, you could switch between a rotating tower and a traditional flat platformer.

In fact, the actual game logic is (mostly) unaware that it’s taking place on a rotating tower. Therefore this discussion is really about standard 2-dimensional platform game collision detection.

We already have a good base to start that discussion from our earlier Tiny platformer game and we will be following the same pattern, although made more complex by:

the player is larger than a single cell
the player is an irregular shape
the player can perform more actions (climb, step, hurt)

The general algorithm remains:

update player position based on current velocity
update player velocity based on gravity, friction and player input
figure out which cells in the map now overlap with the player
… if they are platforms then they block our movement
… if they are ladders then we are allowed to climb on them
… if they contain coins then collect them
… if they contain monsters then the player gets hurt

But before we can go into detail on the collision detection algorithm, we need to take a quick look at what data the map and player objects contain.

The Map

To keep the code simple, we are loading our map data from a simple JSON file that contains an ASCII representation of the map with cells indicated by:

X: a platform
H: a ladder
o: a coin
0 - 3: different monster types

"map": [
  "XXXXXXXXXXXXXXXXXHXX",
  "                 H  ",
  "                 H  ",
  "                 H  ",
  "     o           H  ",
  "    o o          H  ",
  "   o   oooooooo  H  ",
  "   o   XXXXXXXH  X  ",
  "   o          H     ",

  ...

  "oooooooo        0X  ",
  "HXXXXXXX        X   ",
  "H       XX    XX    ",
  "H                   ",
  "H           0       ",
  "H  3       XX       ",
  "XXHXXXX   XXXX2     ",
  "  H      X    XXX   ",
  "  H     X           ",
  "  H    X          X ",
  "  H                 ",
  "  H        ooooooooo"
]

If we were to make a “real game” out of this demo we would probably want to use a real level editor, such as Tiled, as we did in the tiny platformer, but for our purposes, a hand-crafted .json file will suffice.

When we discussed our foundations we mentioned our tower variable. It parses the .json map and builds up a simple two dimensional array of cells:

createMap: function(source) {
  var row, col, cell, map = [];
  for(row = 0 ; row < this.rows ; row++) {
    map[row] = [];
    for(col = 0 ; col < this.cols ; col++) {
      cell = source[row][col];
      map[row][col] = {
        platform: (cell == 'X'),
        ladder:   (cell == 'H'),
        coin:     (cell == 'o'),
      };
    }
  }
  return map;
}

In addition to the static attributes:

platform - true if this cell is a platform
ladder - true if this cell is a ladder
coin - true if this cell contains a coin

A cell might also contain:

monster - reference to the monster that occupies this cell (if any)

which would initially be added to the map during construction…

createMonsters: function(source) {
  var row, col, type, monster, all = [];
  for(row = 0 ; row < tower.rows ; row++) {
    for(col = 0 ; col < tower.cols ; col++) {
      type = parseInt(source[row][col], 10);
      if (!isNaN(type)) {
        monster = new Monster(row, col, MONSTERS[type]);
        all.push(monster);
        tower.map[row][col].monster = monster;
      }
    }
  }
  return all;
}

…but also modified during the game’s update() loop as they move from cell to cell.

NOTE: cell.monster should, technically, be an array instead of a single monster, but if we design our levels well and prevent monsters from overlapping we can simplify our code by ensuring we only ever have a single monster in a single cell at any given time. A more robust engine would probably have to change this to an array.

Player Attributes

The player is initialized with all the attributes we are going to need during the update() loop:

initialize: function() {
  this.x         = col2x(0.5);                   // current x position
  this.y         = row2y(0);                     // current y position
  this.w         = PLAYER_WIDTH;                 // width
  this.h         = PLAYER_HEIGHT;                // height
  this.dx        = 0;                            // current horizontal speed
  this.dy        = 0;                            // current vertical speed
  this.maxdx     = METER * MAXDX;                // maximum horizontal speed
  this.maxdy     = METER * MAXDY;                // maximum vertical speed
  this.climbdy   = METER * CLIMBDY;              // fixed climbing speed
  this.gravity   = METER * GRAVITY;              // gravitational force
  this.impulse   = METER * IMPULSE;              // jump impulse force
  this.accel     = this.maxdx / ACCEL;           // acceleration to apply when player runs
  this.friction  = this.maxdx / FRICTION;        // friction to apply when player runs
  this.collision = this.createCollisionPoints(); // collision points...
},

Player Collision Points

So the player has their x,y,w,h,dx,dy,etc… attributes and will, shortly, move around.

Once they start moving around they are going to collide with things. Unlike in my earlier tiny platformer, the player here is larger than a single cell, and an irregular shape, so we need to do more than simply checking the players bounding box against 1,2, or 4 cells.

Instead, we need to define some collision points and check each one against the cell that it currently occupies.

There are 6 general purpose collision points that are used for most collision detection:

top-left & top-right
middle-left & middle-right
bottom-left & bottom-right

In addition there are 4 special collision points that help with climbing ladders:

under-left & under-right
ladder-top
ladder-bottom

Each collision point starts off with its coordinates relative to the player origin (centered between his feet)…

createCollisionPoints: function() {
  return {
    topLeft:     { x: -this.w/4, y: this.h-2 },
    topRight:    { x:  this.w/4, y: this.h-2 },
    middleLeft:  { x: -this.w/2, y: this.h/2 },
    middleRight: { x:  this.w/2, y: this.h/2 },
    bottomLeft:  { x: -this.w/4, y:  0       },
    bottomRight: { x:  this.w/4, y:  0       },
    underLeft:   { x: -this.w/4, y: -1       },
    underRight:  { x:  this.w/4, y: -1       },
    ladderUp:    { x:         0, y: this.h/2 },
    ladderDown:  { x:         0, y: -1       }
  }
},

During the update() loop, whenever the player moves, each collision point is updated with more detailed information about where in the map that point resides, and whether or not it has collided with a platform, ladder, monster, or coin:

updateCollisionPoint: function(point) {
  point.row      = y2row(this.y + point.y);
  point.col      = x2col(this.x + point.x);
  point.cell     = tower.getCell(point.row, point.col);
  point.blocked  = point.cell.platform;
  point.ladder   = point.cell.ladder;
  point.monster  = false;
  point.coin     = false;
  if (point.cell.monster) { // just because a monster is in the cell, doesn't mean we've collided, need an additional bounding box check...
    var monster = point.cell.monster;
    if (Game.Math.between(this.x + point.x, monster.x + monster.nx, monster.x + monster.nx + monster.w) &&
        Game.Math.between(this.y + point.y, monster.y + monster.ny, monster.y + monster.ny + monster.h)) {
      point.monster  = point.cell.monster;
    }
  }
  if (point.cell.coin) { // just because a coin is in the cell, doesn't mean we've collided, need an additional bounding box check...
    if (Game.Math.between(this.x + point.x, col2x(point.col+0.5) - COIN.W/2, col2x(point.col+0.5) + COIN.W/2) &&  // center point of column +/- COIN.W/2
        Game.Math.between(this.y + point.y, row2y(point.row), row2y(point.row+1))) {
      point.coin = true;
    }
  }
},

NOTE: that just because a point is in a cell with a monster, or a coin, that doesn’t necessarily mean the point collides with the monster or coin, hence the need for an additional bounding box check.

Player Update

Ok, so now that the player has attributes and collision points, the player’s update loop is going to look like this:

accumulate any forces acting on the player

if climbing, ignore vertical forces and use a fixed velocity
if jumping, add a vertical impulse force

integrate to update the player position and velocity
check for collisions

Step 1: we accumulate any forces acting on the player

update: function(dt) {

  this.ddx = 0;
  this.ddy = this.falling ? -this.gravity : 0;

  if (this.climbing) {
    this.ddy = 0;
    if (this.input.up)
      this.dy =  this.climbdy;
    else if (this.input.down)
      this.dy = -this.climbdy;
    else
      this.dy = 0;
  }

  if (this.input.left)
    this.ddx = this.ddx - this.accel;
  else if (wasleft)
    this.ddx = this.ddx + this.friction;

  if (this.input.right)
    this.ddx = this.ddx + this.accel;
  else if (wasright)
    this.ddx = this.ddx - this.friction;

  if (this.input.jump && (!this.falling || this.fallingJump))
    this.performJump();

  this.updatePosition(dt);

  ...

Step 2: Given a current position (x,y), and a current velocity (dx,dy) and now an accumulated force (ddx,ddy), we can update the player state by normal integrating equations of motion.

We must be careful to normalize the new x position if the player has wrapped around the map, and we must bound the new velocities to prevent the player from gaining too much speed.

updatePosition: function(dt) {
  this.x  = normalizex(this.x  + (dt * this.dx));
  this.y  =            this.y  + (dt * this.dy);
  this.dx = Game.Math.bound(this.dx + (dt * this.ddx), -this.maxdx, this.maxdx);
  this.dy = Game.Math.bound(this.dy + (dt * this.ddy), -this.maxdy, this.maxdy);
},

Step 3: Once the player position and velocity has been updated, we can finally check for collisions:

  ...

  while (this.checkCollision()) {
    // iterate until no more collisions
  }

Collision Detection

Collision detection in a platform game can quickly become a complicated business with lots of rules/cases to watch for. You have to really carefully think through the collision detection process and in particular the order which you make your checks to avoid bugs creeping in that might end up with the player stuck on the corner of a platform, or falling through another platform.

For this game, we gather up our current state, update our collision points to reflect the players latest position, and then run through a number of collision checks…

checkCollision: function() {

  var falling      = this.falling,
      fallingUp    = this.falling && (this.dy >  0),
      fallingDown  = this.falling && (this.dy <= 0),
      climbing     = this.climbing,
      climbingUp   = this.climbing && this.input.up,
      climbingDown = this.climbing && this.input.down,
      runningLeft  = this.dx < 0,
      runningRight = this.dx > 0,
      tl           = this.collision.topLeft,
      tr           = this.collision.topRight,
      ml           = this.collision.middleLeft,
      mr           = this.collision.middleRight,
      bl           = this.collision.bottomLeft,
      br           = this.collision.bottomRight,
      ul           = this.collision.underLeft,
      ur           = this.collision.underRight,
      ld           = this.collision.ladderDown,
      lu           = this.collision.ladderUp;
  
  this.updateCollisionPoint(tl);
  this.updateCollisionPoint(tr);
  this.updateCollisionPoint(ml);
  this.updateCollisionPoint(mr);
  this.updateCollisionPoint(bl);
  this.updateCollisionPoint(br);
  this.updateCollisionPoint(ul);
  this.updateCollisionPoint(ur);
  this.updateCollisionPoint(ld);
  this.updateCollisionPoint(lu);

Did we collide with a coin…

if      (tl.coin) return this.collectCoin(tl);
else if (tr.coin) return this.collectCoin(tr);
else if (ml.coin) return this.collectCoin(ml);
else if (mr.coin) return this.collectCoin(mr);
else if (bl.coin) return this.collectCoin(bl);
else if (br.coin) return this.collectCoin(br);

Did we land on the top of a platform or a ladder…

if (fallingDown && bl.blocked && !ml.blocked && !tl.blocked && nearRowSurface(this.y + bl.y, bl.row))
  return this.collideDown(bl);

if (fallingDown && br.blocked && !mr.blocked && !tr.blocked && nearRowSurface(this.y + br.y, br.row))
  return this.collideDown(br);

if (fallingDown && ld.ladder && !lu.ladder)
  return this.collideDown(ld);

Did we hit our heads on a platform above us…

if (fallingUp && tl.blocked && !ml.blocked && !bl.blocked)
  return this.collideUp(tl);

if (fallingUp && tr.blocked && !mr.blocked && !br.blocked)
  return this.collideUp(tr);

Did we reach the bottom of a ladder…

if (climbingDown && ld.blocked)
  return this.stopClimbing(ld);

While running right, did we run into a platform, or a step up

if (runningRight && tr.blocked && !tl.blocked)
  return this.collide(tr);

if (runningRight && mr.blocked && !ml.blocked)
  return this.collide(mr);

if (runningRight && br.blocked && !bl.blocked) {
  if (falling)
    return this.collide(br);
  else
    return this.startSteppingUp(DIR.RIGHT);
}

While running left, did we run into a platform, or a step up

if (runningLeft && tl.blocked && !tr.blocked)
  return this.collide(tl, true);

if (runningLeft && ml.blocked && !mr.blocked)
  return this.collide(ml, true);

if (runningLeft && bl.blocked && !br.blocked) {
  if (falling)
    return this.collide(bl, true);
  else
    return this.startSteppingUp(DIR.LEFT);
}

Did we just start climbing, falling, or fall off a ladder…

var onLadder = (lu.ladder || ld.ladder) && nearColCenter(this.x, lu.col, LADDER_EDGE);

if (!climbing && onLadder && ((lu.ladder && this.input.up) || (ld.ladder && this.input.down)))
  return this.startClimbing();
else if (!climbing && !falling && !ul.blocked && !ur.blocked && !onLadder)
  return this.startFalling(true);

if (climbing && !onLadder)
  return this.stopClimbing();

Did we just hit a monster…

if (!this.hurting && (tl.monster || tr.monster || ml.monster || mr.monster || bl.monster || br.monster || lu.monster || ld.monster))
  return this.hitMonster();

OMG! no more collisions, we are free to continue moving. Huzzah!

  return false; // done, we didn't collide with anything

Collision Resolution

In the previous section, if we detected a collision then we called an appropriate method to resolve it

collectCoin - collided with a coin
collide - collided with a platform while running
collideUp - collided with a platform while jumping
collideDown - collided with a platform while falling
startFalling - detected nothing below us
startClimbing - collided with a ladder while user input up or down
stopClimbing - reached bottom of ladder, or fell off the side
startSteppingUp - collided with step while running
hitMonster - collided with a monster

collectCoin: function(point) {
  point.cell.coin = false;      // remove coin from cell
  this.score = this.score + 50; // increase score
},

collide: function(point, left) {
  this.x  = normalizex(col2x(point.col + (left ? 1 : 0)) - point.x);
  this.dx = 0;
  return true;
},

collideUp: function(point) {
  this.y  = row2y(point.row) - point.y;
  this.dy = 0;
  return true;
},

collideDown: function(point) {
  this.y       = row2y(point.row + 1);
  this.dy      = 0;
  this.falling = false;
  return true;
},

startFalling: function(allowFallingJump) {
  this.falling     = true;
  this.fallingJump = allowFallingJump ? FALLING_JUMP : 0;
},

startClimbing: function() {
  this.climbing = true;
  this.dx = 0;
},

stopClimbing: function(point) {
  this.climbing = false;
  this.dy = 0;
  this.y  = point ? row2y(point.row + 1) : this.y;
  return true;
},

startSteppingUp: function(dir) {
  this.stepping  = dir;
  this.stepCount = STEP.FRAMES;
  return false; // NOT considered a collision
},

hitMonster: function() {
  this.hurting = true;
  return true;
},

performJump: function() {
  if (this.climbing)
    this.stopClimbing();
  this.dy  = 0;
  this.ddy = this.impulse; // an instant big force impulse
  this.startFalling(false);
  this.input.jump = false;
},

There are a lot of tiny, subtle details wrapped up in the player update() method and these associated collision detection methods. I’ve kept the descriptions pretty short, so, as always, look to the source code for any missing details.

That’s All Folks!

Well, that’s about it for this rotating tower platform game/demo. I hope that the articles made some sense, and might help you out with your future platform games!

Let me know in the comments below (or email) if you have any questions.

In the mean time, you can…

play the game
play the game (in flat mode)
view the source code
read the original article
read more about the game foundations
read more about the game rendering

Read more about collision detection in 2D platform games…

Enjoy!