Flick Ninjas Dev Part 4: Pixel based collision detection in 2D games

Flick Ninjas was approved for sale tonight on the iTunes App Store!  To celebrate I thought I'd offer some inside info into the collision detection and response system that I implemented in Flick Ninjas.  Check out Part 3 of my series to read about why I think that Apple is still way ahead of Android when it comes to helping out indie developers.

When designing the collision detection system for Flick Ninjas, I originally determined that I would use a simple tile based system with maybe some 45 degree angles for good measure.  I actually implemented the prototype of the game this way to prove that the control scheme could be fun.  But when it came down to designing the visual appearance of the game, I felt that the limitation of square and 45 degree angles just wasn't going to work.  I really wanted to have arbitrary level designs. I looked to games like Worms for inspiration and started searching the web for ideas when it came to collision detection.

I found a couple of articles explaining how games like Worms and Scorched earth did their collision detection, but quickly found that these methods would not be sufficient.  In these types of games they simply test a single pixel on the bottom of the Worm.  When it overlaps a pixel they simply move the Worm up a pixel at a time until it is no longer overlapping.  This is called collision detection and response.  The detection part simply looks to see if there is an overlap, and the response portion involves moving the entity until it no longer overlaps.

Worms collision detection and response

The weaknesses of this approach became apparent very quickly.  When it came to side and top collisions, this technique wasn't smart enough.  It could only really determine that the response would move the entity too many pixels high, and thus prevent forward progress, however it couldn't tell me how far it had moved into the wall as you could only inch one pixel at a time in worms.  There simply wasn't enough information to tell me what I needed to know when I impacted a wall, a floor or a ceiling, or any combination of all three.  I needed a new approach.

First, I needed a collision detection technique.  I decided that I would test every pixel that overlapped my entity instead just a single pixel, this way I could see where overlaps took place.  I created tiles that were essentially 32 DWORD values where each bit represented whether a pixel was on or off.  I would then see how the entity overlapped the world tiles by ANDing the DWORDS together.  This meant I just needed to test 32 values using bitwise operators per frame.  Pretty cheap!  This approach worked great for collision detection.  I knew exactly when I was overlapping and which pixels overlapped. From here I assumed it would be easy to determine how to respond based on the number of pixels overlapping in each direction. 

Sadly I was incorrect.  It was non-trivial to determine whether a pixel overlap should shift my entity up, down, left, or right. I needed a way to isolate each side of the entity from the other sides, so that I knew how many pixels I should shift in a given direction.  After a few days of beating my head agains the problem, I discovered an interesting approach illustrated by the image below:

Cross Mask Collision Tile

I call this approach, a Cross Mask.  Essentially I created a new 32 DWORD tile that only flags some of the pixels as part of the collision volume.  I then do the same ANDing process with the world tiles, and check only the top 8 DWORDS for Top, the bottom 8 for Bottom, and the middle 16 as the two sides.  I then needed to tell the difference between the left and right.  I did this by only testing if values were greater or less than the values representing the inside portions of the mask.

This approach allowed for almost everything I wanted. I could tell how many pixels I needed to shift, and what direction for up to two sides at a time.  This is where the only downfall to this approach presented itself.  I couldn't test both the top and bottom, or both the left and right at the same time.  I tried prioritizing certain sides and such, but to no avail.  I may approach this problem again, but to solve it, I simply don't allow gaps smaller than 32 pixels wide in the level.  In cases where the style required it, I simply created a special entity that block progress further into these sections of the level.

If you have any questions about this approach, let me know in the comments.  And check out my personal development blog for a look at both my official trailer, and my new launch campaign series of trailers. Also, feel free download Flick Ninjas for just $0.99 now if you feel so inclined.