Well, I’m starting to settle into this Cocos2d-XNA framework and I must say, I’m really having a great time with it. The last few weeks have been spent exploring collision detection techniques and how I might implement pixel-perfect collisions in C2D, so I thought I’d share my wanderings with you in this post. It seemed like a natural progression to me following my first couple areas of exploration which concerned using sprites and actions in the framework, learning the basics of movement, rotation, scaling, etc. With collision detection implemented, I have the basic tools that are necessary to create a variety of different games; a lot of the other stuff revolves around making a game shiny, adding game play depth, etc.
Collision detection in games is an interesting subject, comprised of numerous and varied algorithms based on the particular issues your game is trying to solve. In general, you won’t find one collision detection method that you’ll use in all the games you ever write. For example, one game may only require a simple bounding box collision to function well as being in the general area is good enough (think character collisions for starting an encounter in an RPG game). However, that won’t fly for a shooting style game where your guy disappears off the screen before it looks like the bullet gets there (think crappy game engine) – I mean, that bullet missed my guy by a full two pixels! Boo. So you need to pick a method that fits the needs of your game and doesn’t detract from the game play. In many instances, a layered approach using a few different algorithms may yield the best results depending on the game.
One of the main goals of good collision detection is the speed at which your game can detect a collision. A lot of times, you’ll be checking for collisions during each update cycle of your game and slow, lumbering collision detection can mean dropped frame rates and less time to do other needed things in your game. For the example I chose for this tutorial (a space shooter – I’ve always loved games like Galaga, etc.), I needed a reasonably fast algorithm to check for pixel-perfect collisions between my ship, enemy ships, and bullets. Even with 2013 technology, doing a straightforward pixel level check between most objects (or even just a few objects) in a game is extremely slow and wasteful as well, since many objects probably don’t even need to be checked if they aren’t near each other, don’t collide with each other, etc.
C2D provides the CCMaskedSprite object to help facilitate pixel-perfect collisions in your games. Derived from the CCSprite object, It accepts a byte array containing the mask of the sprite for the object, which is just a text file of 0/1 values stored in a *.mask file, with 0 representing transparent areas of the sprite where a collision shouldn’t occur. You check for a collision using the CollidesWith method of the class. It does a simple bounding box collision check first and if that succeeds, it performs checking against the masks of the sprites for a true collision. It also returns the point at which the collision occurred if you need it.
It wasn’t obvious how these masks were created, but a post on the forum helped clear that up. Masks for your sprites can be created with the Collision Mask Generator utility in the Cocos2d-XNA framework, found in the cocos2d-xna/tools/CollisionMaskGenerator directory. After generating your mask files, you’ll need a way store them in your game. One of the chaps from the C2D dev team (totallyevil) suggests storing them as embedded resources in your assembly instead of XNB files from your Content project as they’re easier to port to other platforms and you avoid custom content issues.
Even with the help that C2D provides with the CCMaskedSprite, I still needed a way to narrow down my collisions so I wasn’t checking all sprites in my game for collisions during each update cycle. So after some Google-Fu and some meandering about the Internets, I found a good article on 2D collision detection methods that I think is well worth reading called Methodologies for Quick Approximation of 2D Collision Detection Using Polygon Armatures. One of the suggestions it provided was to only check objects for collision that are near each other on the screen, which makes good sense in my scenario (and probably in general) as most times I won’t have a bunch of objects together in the same place. You can do this by implementing a spatial partitioning system, which is just a fancy way to describe splitting the screen up into a defined set of spaces. A tree structure is often used for such a system, but the authors suggested a simpler approach of a predefined partition size that only requires each object to sorted into it’s appropriate location (they refer to this as ‘binning’). I refer to it as a Collision Grid. One assumption made with this particular method is that the objects in the game are of similar size; in other words, the size of each square in the grid can contain any whole object in your game. This means that any object would only be in 1, 2, or 4 grid squares in a given update cycle, based on whether it crossed horizontal/vertical boundaries of a grid square. If objects aren’t of a similar size, modifications would have to be made or a different scheme used altogether.
I basically implemented my collision grid as follows:
- I start with my collision grid at a fixed size of 100 x 100 pixels per grid square. I then distribute any space remaining across all grid squares to “fit” the screen as much as possible. This provides you with a set of defined rows/columns for the screen. For example, at a resolution of 1024 x 768, I have 8 rows x 11 columns to contain all visible space on the screen.
- I number each square in my collision grid starting from 0 at the bottom left of the screen, continuing to the right across columns and then up by rows. For example, a grid with 8 rows and 11 columns would be numbered 0-10 for row 1, 11-20 for row 2, etc.
- I created a Dictionary of ‘bins’ (i.e. grid squares), with each bin containing a List of the game objects that it contains for that update cycle (Dictionary<int,List<GameObject>>).
- During each update cycle, the following steps are taken:
- The dictionary of bins is cleared.
- Each game object is assigned to the appropriate bin based on the screen position of the four corners of it’s bounding box.
- I check the player’s ship and player’s missiles for possible collisions by seeing if their bins contain any other objects (checking enemy and enemy missile collisions would be redundant in my case).
- After sorting out any invalid collisions (e.g. player ship with player bullet, etc.), I then call the CCMaskedSprite.CollidesWith method from C2D to check for an actual collision.
- Rinse and repeat.
Aside from the collision grid, I also made a base class called GameObject from which all the various game objects derive (Ship, Enemy, Bullet). This allowed me to keep most code with the appropriate objects, though the processing is mainly handled in the GameObjectLayer class since it knows about all the players and the collision grid. You can see a screenshot of the final result below.
As I meant this to be a learning exercise as opposed to a real game, I built in some controls to the game to show various parts and let you control some objects so you can get a feel for how the collision works and/or if you wanted to break through the code easily. The controls are as follows:
- Arrow keys – move the player’s ship up/down/left/right. Speed of the ship is adjustable through the ShipSpeed constant in the Ship class, in case you want to slow it down for testing.
- Left Control – Fires bullet from player’s ship.
- B – Show/hide bounding boxes for the game objects on the screen.
- G – Show/hide the collision grid on the screen.
- E – Enables/disables movement of enemy ships.
- S – Enables/disables movement of enemy bullets.
The result of this effort is contained in a new project called Collision Detection in my Cocos2D-XNA-Tutorials solution on GitHub. The code is heavily commented so you should be able to find your way around without too much effort. Hopefully you find it helpful, I had a lot of fun coding it and seeing it work. Well, that’s it for now, it’s past my bed time. Happy proggy.