<< Back to Developer Musings
Collision Detection (March 31, 2015)
Collision detection is one of those things that you don't notice when done correctly, but when done wrong, can result in exteme cases of rage quitting. There's nothing I hated more than playing a Nintendo game and dying when I KNEW that that missle didn't hit me! Or even worse, jumping onto a platform and then falling right through because I'm not close enough to the center.
The interesting thing about collision detection (at least for 2D games) is that not much has changed in the past 25 years. Believe it or not, the algorithms to handle collision detection in 2D haven't changed much since the days of Atari. Even so, there's good collission detection, and then there's really bad collision detection.
There are a few types of collision detection that are generally used in 2D games. The first (and slowest type) is pixel-perfect collision detection which actually compares all non-alpha pixels of every collidable object and raises a collision whenever there's an overlap detected. This type of collision detection gives you a very accurate result, but at the expense of performance. Games these days need to run at 60 FPS, and while doing pixel-perfect collision detection is doable with today's hardware, you're going to use up some of those valuable one frame 16.6 milliseconds that could be better spent doing AI, graphics, and physics calculations.
Fortunately there's a simpler, and faster, way to do collision detection, and you've probably figured it out already. We simply draw an invisble box, called a bounding box, around each sprite and do the much faster rectangle overlap calculations. Now because every sprite isn't a perfect rectangle (thanks to all those alpha pixels), these bounding boxes are not going to be 100% accurate. This is where a lot of games shit the bed when it comes to collision detection. The trick to using bounding boxes is that you have to use smaller boxes than your actual sprite -- and you have to tweak this area so that it takes into account your physics timestep (see below). A good starting point is to make your bounding box 10% smaller than the sprite itself, and no I didn't just pull this number out of thin air -- I got it from a classic video game programming book: Tricks of the Video Game Programming Gurus, which is an old book from the DOS days, but also the greatest video game programming book ever written (in my opinion).
The really nice thing about SpriteKit is that you can define these bounding boxes in code and then turn on the SKScene's ShowPhysics property to visually see these bounding boxes:
Here you can see the blue lines that define the collidable area of each sprite. In my Android engine I had to actually change the sprites in the textureatlas to be able to see these types of lines, so I really appreciate how easy SpriteKit makes it to debug collision issues.
So back to the 10% rule, once you've got that implemented it's time to actually play the game and make sure it "feels" right. It's really quite an art because physics play a huge part in collision detection. For instance: if an object is traveling at a very high speed towards you and each physics step is only 16.6ms, then it's very possible that the object could pass right through you without registering a collision! Likewise if you're moving quickly and an object is moving quickly towards you and you jump at the last minute, it's very possible that you'll jump at the same time as the collision registers. This is where I made the decision to have "jumping" override the fact that you were technically hit at the same time you jumped. Early beta tests showed a lot of pissed off testers whenever they would jump at the last moment and still be hit by a bowling ball the moment they jumped. Again, it wouldn't have been "technically" wrong to count this as a collision, but it just felt more right to give the player the benefit of the doubt.
Another Cool Performance Tweak
Another really cool retro performance tweak I wanted to talk about. Imagine you're playing a game like asteroids where there are 5 asteroids on the screen, plus your ship. Asteroids bounce off of each other, and also destroy your ship if touched. Right here we're calculating 30 possible collisions. That's not too bad, you could handle this in 16.6ms even on a shitty phone. Now imaging you have 100 asteroids. Now we're talking about 10K collision checks per frame! As you can see, this doesn't scale very well and your game's quickly going to tank once too many asteroids are on sceen at once.
The trick here is to divide your screen into 'zones'. Perhaps 20 different square zones. Each asteroid should have a property that keeps track of which 'zone' it's in. Now when you're doing your collision checks you do zone-by-zone checks and the overall number of collision checks is going to be much lower. Obviously there's some overhead when asteroids move into a different zone, but this overhead is going to occur far less than collision checks which happen every frame.
... or you could just be super lame and cap the # of asteroids to 100 ;)