Collision Detection in 2D

16 August 2018 3:03 pm



Before we begin

This is a bit disorganised, I don't really want to write a massive tutorial on something I learnt a few weeks ago. Instead these are notes to help me remember what I did. The links to other websites are probably of most use to other people.

Collisions, along with showing images and reading user input are one of the fundamental parts of making any 2D game. If you can't tell what's colliding, your game won't know how to react to the action on the screen.

It's deceptively difficult to do right

Sure, if you realise each sprite is nothing more than a 2D rectangle then the process of checking for overlapping rectangles is very easy. No actual maths is required, and the code fits on a few lines. Just test every rectangle against every other rectangle. If any two overlap, do something about it. This nice, dumb way is OK when there aren't too many items on the screen:

The player can only shoot one bullet at a time, and that bullet only has to check for an overlap with 60 other items (55 enemies, 4 bases and the top of the screen). It's not that much of a big deal.

More complex games need to use alternate strategies, which this post is going to cheerfully ignore for now. Try the brute-force method with thousands of bullets, and things start to slow down (which can sometimes be turned into a game mechanic)

It needs tuning to the game you're making

"Collision detection" isn't a single pattern that can be stamped into every game in the same way. A vertically scrolling shooter will handle it differently to a static screen shooter, which will handle it totally differently to a platform game where wall jumping exists.

For the purpose of this post collisions are restricted to a single screen, with no more than about 30 sprites on screen at once. That seems to be the limit of what my sprite routine can cope with at the moment. We are also only going to deal with axis-aligned collisions.

Pixel-perfect?

Look at any 2D game, notice how the sprites don't actually look like boxes? They contain areas that are treated as being transparent. Ever played a bad 2D game where things died even though it didn't look like anything had touched them? That's because the collision code was only checking whether the sprite's entire rectangle was colliding, rather than what the player can see.

Disclaimer...

Yes, you can define a collision rectangle inside the sprite and test against that. I know that's what most games did, but sometimes the reason for doing something is to find out whether you can do it.

The overall algorithm

Collision detection is all about filtering out sprites to reduce the amount being checked. The more precise the collision detection, the more expensive it is to calculate.

  1. Use some sort of spatial organisation to filter out sprites that aren't even near each other. Split your screen into a grid or something, only test sprites within the same grid, use a fancy sorted tree, whatever works for your game. When I need to do this, I'll write about what I did.
  2. Use axis-aligned bounding boxes to check whether two sprites are touching.
  3. If they are, figure out which parts are touching to see whether it's part of their collision masks.
  4. If their collision masks are touching, you have a collision.
  5. Do something about the collision.

Collision Mask?

You need some way to define which parts of the sprite are "solid" and which parts are not. Since our aim is to do this with pixel-perfect accuracy, the way to define the collision mask is to use a 1 bit bitmap that is the same shape and size as your sprite. Colour any parts "solid" black, and leave the rest white (or do the opposite, it doesn't matter). My bitblit routine needs a mask to avoid drawing "transparent" parts of the sprites, so I can reuse that.

How to do it

1. Axis Aligned Bounding Boxes

Treat each sprite as a rectangle that contains an origin, width and height.

var rect1 = {x: 5, y: 5, width: 50, height: 50}
var rect2 = {x: 20, y: 10, width: 10, height: 10}

if (rect1.x < rect2.x + rect2.width &&
   rect1.x + rect1.width > rect2.x &&
   rect1.y < rect2.y + rect2.height &&
   rect1.height + rect1.y > rect2.y) {
    // collision detected!
}

(this came from here: https://developer.mozilla.org/kab/docs/Games/Techniques/2D_collision_detection )

If this is confusing, just draw some example shapes on squared paper and make sense of the maths visually. It's what I did. 2D graphics programming is a rare oppotunity to visualise what's going on by using paper and a pencil.

You now have basic axis-aligned bounding-box collision detection. Let's move on and make this pixel-perfect...

2. Calculate collision mask intersections

If you have two overlapping rectangles, the next step is to find out which exact parts of the rectangles overlap.

https://stackoverflow.com/questions/4549544/total-area-of-intersecting-rectangles

Once you know which parts, a small amount of maths is required to turn that into the pixel locations within the sprite's image. Your sprite might be at 50,50 and its area of collision might be from 60,60 for a 10x10 pixel area. So you will need to subtract the location of the sprite from the collision co-ordinates.

( This website helped, but the code isn't very useful https://www.gamedev.net/articles/programming/general-and-gameplay-programming/intelligent-2d-collision-and-pixel-perfect-precision-r3311/ )

3. React to the collisions

For this part I'm using function pointers to create callback functions that fire when collisions happen. So far it seems to work quite well.