7 min read

In almost every single game you’re going to have different objects colliding. If you’ve worked with any game engines, this is generally taken care of for you. But what about if you want to write your own?

For starters, we’re just going to check for collisions between rectangles. In many cases, you’ll want rectangles even for oddly shaped objects. Rectangles are very easy to construct, very easy to check for collisions, and take up very little memory. We can define a rectangle as such:

var rectangle = {
  x: xPosition,
  y: yPosition,
  w: width,
  h: height
}

Checking for collisions between two rectangles can be broken into 2 sections: Compare the right-side against the left and the bottom-side against the top. A simple rectangle collision function might look this this:

function isColliding(A, B) {
  var horizontalCollision = (A.x + A.w >= B.x && B.x + B.w >= A.x);
  var verticalCollision = (A.y + A.h >= B.y && B.y + B.h >= A.y);
  return horizontalCollision || verticalCollision;
}

Now that all of our game objects have collision rectangles, how do we decide which ones are colliding?

Check All The Things!

Why not just check everything against everything? The algorithm is really simple:

for (var i = 0; i < rectangles.length; i++) {
  var A = rectangles[i];
  for (var j = 0; j < rectangles.length; j++) {
    // Don't check a rectangle against itself
    if (j === i) {
      continue;
    }

    var B = rectangles[j];
    if (isColliding(A, B)) {
      A.isColliding = true;
      B.isColliding = true;
    }
  }
}

Here’s a working sample of this approach. The problem here is that this approach becomes drastically slower as the number of rectangles increases. If you’re familiar with Big-O then this is O(n2) which is a big no-no. Try moving around the slider in the example to see how this affects the number of collision checks.

Just by looking at the screen you can easily tell that there are rectangles which have no chance of touching each other, such as those on opposite sides of the screen. So to make this more efficient, we can only check against objects close to each other. How do we decide which ones could touch?

Enter: Spatial Partitioning

Spatial partioning is the process of breaking up the space into smaller chunks and only using objects residing in similar chunks for comparisons. This gives us a much better chance of only checking objects that could collide. The simplest way of doing this is to break the screen into a grid.

Uniform Grid

When you use a uniform grid, you divide the screen into equal sized blocks. Each of the chunks, or buckets as they’re commonly called, will contain a list of objects which reside in them. Deciding which bucket to place them in is very simple:

function addRectangle(rect) {
  // cellSize is the width/height of a bucket
  var startX = Math.floor(rect.x / cellSize);
  var endX = Math.floor((rect.x + rect.w) / cellSize);
  var startY = Math.floor(rect.y / cellSize);
  var endY = Math.floor((rect.y + rect.h) / cellSize);

  for (var y = startY; y <= endY; y++) {
    for (var x = startX; x<= endX; x++) {
      // Make sure this rectangle isn't already in this bucket
      if (grid[y][x].indexOf(rect) === -1) {
        grid[y][x].push(rect);
      }
    }
  }
}

A working example can be found here. Simple grids are actually extremely efficient. Mapping an object to a bucket is very straightforward which means adding and removing objects from the grid is very fast. There is one downside to using a grid though. It requires you to know the size of the world from the beginning and if that world is too big, you’ll consume too much memory just creating the buckets. What we need for those situations is a more dynamic structure.

Quad Tree

Imagine your whole screen as one bucket. Well the problem with the first approach was that we would have to check against too many objects so what if that bucket automatically broke into smaller buckets whenever we put too many objects into it? That’s exactly how a quad tree works. A quad tree limits how many objects can exist in each bucket and when that limit is broken, it subdivides into four distinct quadrants. Each of these quadrants are also quad trees so the process can continue recursively. We can define a quad tree like this:

function QuadTree(x, y, w, h, depth) {
  this.x = x;
  this.y = y;
  this.w = w;
  this.h = h;
  this.depth = depth;
  this.objects = [];
  this.children = [];
}

As you can see, a quad tree is also a rectangle. You can think of a quad tree like those little Russian stacking dolls. But rather than finding just one doll inside of each, you’ll find four different dolls inside of each one. Since these dolls are rectangular, we just check to see if an object intersects it. If it does, we put the object inside of it.

QuadTree.prototype.insert = function(obj) {
  // Only add object if we're at max depth
  // or haven't exceeded the max objects count
  var atMaxDepth = (this.depth > MAX_DEPTH);
  var noChildren = (this.children.length === 0);
  var canAddMore = (this.objects.length < MAX_OBJECTS);
  if (atMaxDepth || (noChildren && canAddMore)) {
    this.objects.push(obj);
  } else if (this.children.length > 0) {
    // If there are children, add to them
    for (var i = 0; i < 4; i++) {
      var child = this.children[i];
      if (isColliding(child, obj)) {
        child.insert(obj);
      }
    }
  } else {
    // Split into quadrants
    var halfWidth = this.w / 2;
    var halfHeight = this.h / 2;
    var top = this.y;
    var bottom = this.y + halfHeight;
    var left = this.x;
    var right = this.x + halfWidth;
    var newDepth = this.depth + 1;

    this.children.push(new QuadTree(right, top,    halfWidth, halfHeight, newDepth));
    this.children.push(new QuadTree(left,  top,    halfWidth, halfHeight, newDepth));
    this.children.push(new QuadTree(left,  bottom, halfWidth, halfHeight, newDepth));
    this.children.push(new QuadTree(right, bottom, halfWidth, halfHeight, newDepth));

    // Add the new object to simplify the next section
    this.objects.push(obj);

    // Move each of the objects into the children
    for (var i = 0; i < 4; i++) {
      var child = this.children[i];
      for (var j = 0; j < this.objects.length; j++) {
        var otherObj = this.objects[j];
        if (isColliding(child, otherObj)) {
          child.insert(otherObj);
        }
      }
    }

    // Clear out the objects from this node
    this.objects = [];
  }
};

At this point any given object will only reside in nodes in which it’s relatively close to other objects. To check for collisions, we only need to check against this subset of objects like how we did with the grid based collision.

QuadTree.prototype.getCollisions = function(obj) {
  var collisions = [];
  // If there are children, get the collisions from there
  if (this.children.length > 0) {
    for (var i = 0; i < 4; i++) {
      var child = this.children[i];
      if (isColliding(child, obj)) {
        // Concatenate together the results
        collisions = collisions.concat(child.getCollisions(obj));
      }
    }
  } else {
    // Otherwise, check against each object for a collision
    for (var i = 0; i < this.objects.length; i++) {
      var other = this.objects[i];

      // Don't compare an object with itself
      if (other === obj) {
        continue;
      }

      if (isColliding(other, obj)) {
        collisions.push(other);
      }
    }
  }
  return collisions;
};

A working example of this is available here. Traversing this tree takes time so why would we use this instead of a collision grid? Because a quad tree can grow and change as you need it. This means you don’t need to know how big your entire world is at the beginning of the game and load it all into memory. Just make sure to tweak your cell size and max objects.

Conclusion

Now that you’ve got your feet wet, you can go out and write your own collision detection systems or at least have a better understanding of how it all works under the hood. There are many more ways of checking collisions, such as using oct-trees and ray casting, and every approach has it’s benefits and drawbacks so you’ll have to figure out what works best for you and your game. Now go make something amazing!

About the Author

Mike Cluck is a software developer interested in game development. He can be found on Github at MCluck90.

LEAVE A REPLY

Please enter your comment!
Please enter your name here