Javascript Gauntlet - Collision Detection

Sat, May 18, 2013

Last time we looked at our game entities and their update() methods and talked a little about monster AI - which really boiled down to:

move towards the player!

What we glossed over was how the entities occupy() the map, and trymove() within it.

This article will reveal more details about those methods, what the maps internal data structure looks like, and how collision detection works within the game.

Brute Force

We can check if 2 entities overlap with a simple helper method:

overlap: function(x1, y1, w1, h1, x2, y2, w2, h2) {
  return !(((x1 + w1 - 1) < x2) ||
           ((x2 + w2 - 1) < x1) ||
           ((y1 + h1 - 1) < y2) ||
           ((y2 + h2 - 1) < y1))
}

Given this method, the simplest possible approach to collision detection would be to maintain a single array of entities, each with a position (x,y) and a size (w,h), then in each game frame compare every entity against every other entity to see if they overlap()

However, this is an O(n^2) algorithm, and while it might work in a game with just a few entities, in Gauntlet we can have hundreds of entities in a single level. 500 entities would require 250 thousand collision checks every frame - not good.

Spatial Partitioning

The solution is to use a Spatial Partitioning technique and split collision detection into 2 separate phases:

There are many different partitioning techniques available to us:

For Gauntlet, we have already defined our map in terms of a tile-based grid, and all of our entities are the same size (roughly 1 tile) so it makes sense for us to use a simple grid to partition our space.

If we had different sized entities we might be better off with a QuadTree, but for our purposes a simple grid works out well.

Occupying the Map

Since our entities are all equal (or smaller) in size than our cell, we can be sure that a single entity can only ever occupy 1, 2, or at most, 4 cells

In a more general example, the first image on the left (below) shows entities that all conveniently line up on grid cell coordinates, but entities are not restricted to grid aligned coordinates, they can roam freely. The second image on the right (below) shows an example when the entities are placed arbitrarily and do not align cleanly with grid cell coordinates.

To support this, in addition to our single array of entities, we add the following data structures

A SIDE NOTE - on performance

Before we continue, lets take a small time out to talk about javascript arrays, objects, and performance.

If we plan to use arrays to track entity.cells and cell.occupied then we have to expect those arrays to be changing frequently within our game loop.

Specifically, we should recognise that the only way to remove an arbitrary element from a javascript array is to splice() the array and create a new one. Thus we might be creating many (small) arrays. This should make us pause and consider performance implications, specifically garbage collection issues.

We could recognize that we actually don’t care about ordering in our 2 cases and that what we really want is a set, not an array, but javascript doesn’t have native sets!

We might consider using an object as a set, since its effectively the same thing, but we are then left with using a for in loop to iterate over the keys, and delete for removing keys. These both have performance implications, the for in loop is simply slower than a normal for loop over an array, while using delete on an object changes its internal structure and frequently causes it to be de-optimized by the browser’s hot spot compiler - again causing performance issues.

What this boils down to is that there is no hard and fast rules for the right data structures to use, you must always measure your results and choose based on actual performance, not theoretical performance.

I experimented with both approaches

And it turned out, for Gauntlet where the arrays are very small (typically 1 to 4 elements) the Array case was much faster then using an Object as a Set. Although it did result in a little more memory allocation, and therefore more garbage collection, the amount was small and did not result in any noticeable game stutter.

In order to encapsulate the problem and experiment with alternative solutions, we hide the implementation of the core methods behind the following helper methods:

function set_contains(arr, entity) { return arr.indexOf(entity) >= 0;    }
function set_add(arr, entity)      { arr.push(entity);                   }
function set_remove(arr, entity)   { arr.splice(arr.indexOf(entity), 1); }
function set_clear(arr)            { arr.length = 0;                     }
function set_copy(arr, source) {
  set_clear(arr);
  for(var n = 0, max = source.length ; n < max ; n++)
    arr.push(source[n]);
}

If we eventually find that garbage collecting the arrays causes issues, we can implement a ‘pool’ of arrays, or replace these methods with a more optimized Set class. Long term, for a more formal game library, we would almost certainly want to invest some effort in a high performance, garbage-friendly, Set class.

A SIDE NOTE - on coordinates

When we talk about (x,y) coordinates we are referencing game pixels. Occasionally, when we want to talk about grid cell coordinates we will use the (tx,ty) notation to denote tile-x and tile-y coordinates.

NOTE: apologies for the inconsistent terminology, at the start of the project I was using the word TILE, by the end I was using the word CELL, and I never went back to tidy up. You should consider them interchangeable terms.

The game also defines the size of a tile in game pixels:

TILE = 32

So, for a map that is 10x10 cells, the pixel size of the map will be 320x320. We also set this as the size for our logical <canvas> element and let the browser take care of scaling it to whatever physical size the canvas element happens to be (based on @media queries)

In order to quickly convert between game pixel coordinates and game tile coordinates we use a couple of simple helper methods:

  function p2t(n) { return Math.floor(n/TILE); }; // pixel-to-tile conversion
  function t2p(n) { return (n * TILE);         }; // tile-to-pixel conversion

Now, given a pixel (x,y) position, we can access any map.cell():

  cell: function(x, y) {
    return this.cells[p2t(x) + (p2t(y) * this.tw)];
  },

Occupying the Map (continued)

Ok, so lets get back to the entities and the map. We want to start with a helper method that will return, for any given rectangle, the cells that overlap that rectangle.

overlappingCells: function(x, y, w, h) {

  var cells = [];

  var nx = ((x%TILE) + w) > TILE ? 1 : 0,   // overlap right ?
      ny = ((y%TILE) + h) > TILE ? 1 : 0;   // overlap below ?

  set_add(cells,   this.cell(x,        y));
  if (nx > 0)
    set_add(cells, this.cell(x + TILE, y));
  if (ny > 0)
    set_add(cells, this.cell(x,        y + TILE));
  if ((nx > 0) && (ny > 0))
    set_add(cells, this.cell(x + TILE, y + TILE));

  return cells;

},

NOTE: this method assumes entities are equal or less than the size of 1 TILE. To support larger entities we could refactor this method to be more general purpose, but it works for our needs.

We can now place entities on the map using the map.occupy() method, which will:

occupy: function(x, y, entity) {

  // always move, assume caller took care to avoid collisions
  entity.x = x;
  entity.y = y;

  var before = entity.cells,
      after  = this.overlappingCells(x, y, entity.w, entity.h),
      c, cell;

  // remove object from previous cells that are no longer occupied
  for(c = 0 ; c < before.length ; c++) {
    cell = before[c];
    if (!set_contains(after, cell))
      set_remove(cell.occupied, entity);
  }

  // and add object to new cells that were not previously occupied
  for(c = 0 ; c < after.length ; c++) {
    cell = after[c];
    if (!set_contains(before, cell))
      set_add(cell.occupied, entity);
  }

  // and remember for next time
  set_copy(before, after);

  return entity;
},

Note that this method has no collision detection logic. It assumes that the calling code will check for collisions before trying to occupy() the map…

Movement and Collision Detection

Now that entities can occupy the map, we want to allow them to move into empty space but stop if they collide with another entity. With our spatial partitioning grid in place, we now only need to check for collisions against entities in the same cell(s) that we occupy.

To implement this algorithm we start with the occupied() method which, for a given rectangle, returns the first entity that overlaps (if any):

occupied: function(x, y, w, h, ignore) {

  var cells   = this.overlappingCells(x, y, w, h),
      checked = [],          // avoid checking against the same entity multiple times (if that entity spans multiple cells)
      c, cell, e, entity;

  // for each cell that overlaps the target area
  for(c = 0 ; c < cells.length ; c++) {
    cell = cells[c];

    // return true if the cell is a wall
    if (cell.wall)
      return true;

    // otherwise, check against each entity that currently occupies that cell
    for(e = 0 ; e < cell.occupied.length ; e++) {
      entity = cell.occupied[e];
      if ((entity != ignore) && !set_contains(checked, entity)) {
        set_add(checked, entity);
        if (overlap(x, y, w, h, entity.x, entity.y, entity.w, entity.h))
          return entity;
      }
    }

  }

  return false;
},

Given the occupied() method above, we can now implement a trymove() method for a given entity, with a specified direction and speed, to move that entity in that direction unless its already occupied():

trymove: function(entity, dir, speed) {
  var collision, pos = {};
  pos.x = entity.x + (isLeft(dir) ? -speed : isRight(dir) ? speed : 0);
  pos.y = entity.y + (isUp(dir)   ? -speed : isDown(dir)  ? speed : 0);
  collision = this.occupied(pos.x, pos.y, entity.w, entity.h, entity);
  if (!collision) {
    this.occupy(pos.x, pos.y, entity);
  }
  return collision;
},

… and that’s it! We’re done with collision detection. An entity can now occupy() the map and trymove() within it.

Next Time…

Yikes. Too much detail ? Lets recap:

We could simplify this a little, instead of having an entity occupy multiple cells, it could just occupy the one cell at its (x,y) position. Since we would no longer be tracking exactly which cells the entity occupies, we would have to change the algorithm to check against 9 cells per entity (the one it occupies + all 8 neighbouring cells). This would be slower than just checking against the more exact 1-4 cells, but would still be much better than a brute force O(n^2) algorithm, and would lead to simpler code…. Maybe next time!

The code in this article (as in the others) is a simplified version of the real code for clarity. The main differences are performance optimizations to avoid allocating new arrays/objects when possible, and I’ve also glossed over the fact that the entities are actually NOT all exactly 1 TILE wide/high. They actually have slightly different collision boxes (cbox), e.g. Weapons have much smaller collision boxes.

But I think the main points are covered.

In the next article, we can get out of the depths of the code and step back up to the high level game object and all of the state machine & event handlers that make up the actual game logic…