Originally published in 22 December 2011. [color=#8B0000]Please feel free to comment and tell me if I missed something or if there's anything wrong! Feedback is really appreciated![/color] When you're making a 2D game where collision is an important factor, the more precise your logic is, the better! But perfect collision in 2D games often involves pixel perfect collision, which generates an overhead. This type of collision, at least in some simplementations, uses a secondary 1-bit bitmap (mask) where you have only black and white, for the example, or a boolean matrix, so you get the origin of two sprites, get their masks and check for collisions of white-pixels (colliding "trues", if using the matrix), if there's any, the objects are in fact colliding. When you have 100 small sized objects, it's ok to check every one against every other. But when this changes to multiple hundreds of relatively big resolution sprites, the overhead of the collision calculations will affect the game. What to do now? There are lots of ways to reduce this overhead, we'll discuss some of them here today. For the article, I'll be using the following situation: Here, we have 32 different objects (the topmost platform is formed by 2 rectangles), and the ground rectangles are way too big to check pixel perfect collision, it'll surely be a problem.

Bounding Box

Probably the most basic collision test is the bounding box check. The bounding box check is both the easiest and the most efficient way we have to reduce overhead on pixel-perfect collision games! Before you check if two sprites are colliding you check if they are near enough to have any chance of collision. If their bounding boxes aren't touching, there's no reason to check for pixel collision, since all pixels are necessarily inside their bounding boxes. To verify if a bounding box is touching another is really simple. We have 2 objects, OB1 and OB2, each one have 4 coordinates, for OB1 it would be: OB1top, OB1bot, OB1Left, OB1Right, the same for OB2. Where

• OB1top is the y coordinate of point A;
• OB1bot is the y coordinate of point B;
• OB1left is the x coordinate of point A;
• OB1bot is the x coordinate of point B.

Now you create something similar to this: bool colliding (Object OB1, Object OB2){ // Check the collision Vertically if (OB1bot>OB2top) return false; /* this means that OB1 is above OB2, far enough to guarantee not to be touching*/ if (OB2bot>OB1top) return false; /* this means that OB2 is above OB1 */ // Check the collision Horizontally if (OB1left>OB2right) return false; /* this means that OB1 is to the right of OB2 */ if (OB2left>OB1right) return false; /* this means that OB2 is to the right of OB1 */ return true; /* this means that no object is way above the other nor is to the right of the other meaning that the bounding boxes are, int fact, overlapping.*/ } Just by doing this simple check, you'll reduce the overhead to your perfect collision enormously, without reducing its precision. A major advantage on this approach is that it's independant of the size of the objects! While the pixel perfect collision depends a lot on the size of the objects being tested, this will have constant check time. Now let's think in numbers: If we collide every object againt every other, the number of collision checks will be nothing less than: 32 objects X 31 other objects / 2 since we will check each pair only once = 32*31/2 = 496 collision checks! Now imagine if instead of 6 soldiers, we had 12, and all of them shot twice as many projectiles, for a total of 88 projectiles: The number of objects would rise to 104 but the number of checks would rise to no less than 5356! While we rose from 32 objects to 104 (3.25 times), the collision tests rose to more than 10 times than before ([size=2]~=10.8)! As you can see, it's rather impractical. How can we further increase our collision performance if we have already removed almost all pixel level collisions? The answer is still simple - we have reduced the time each collision takes to be calculated, now we have to reduce the total number of collision checks! It may look weird, but to reduce collisions you'll need to create new special collisions! You can chop your playable area, section it up, so you will check collisions only between objects in the same sections!

Sector (Grid) Collision Check

Using both a grid and bounding boxes, you'll have this: As can be seen here, there are four objects under 2 sections (2 bullets and 2 ground tiles!) and, if we had an object in the exact point where the lines cross each other, that object would be in all 4 sections. When this happens, you have to check the collision of these objects against every object in each sections that part of it belongs. But how do I know if an object is in a section? Do a bounding box collision check against the sections! If the bounding box return true, the object is in fact in that section. In this case, we would have something like this: //All of this is in pseudo-code //It's really game-specific std::list allObjectsList; //Contains all active objects std::list sectionList[4]; /*Contains all objects within the sections*/ Object sections[4]; void insert (Object object, sectionList List){ //insert Object in sectionList } void flush (){ //remove all objects on sectionList[0,1,2 and 3] } void sectionizeObjects (){ flush(); for(int obj = 0; obj < allObjectsList.lenght; obj++){ for (int i = 0; i < 4; i++) if( checkBBoxCollision(allObjectsList[obj], sections) ) insert (allObjectsList[obj], sectionList) } } Ta-da! Our collision system is finally optimized and ready to grow in scale![size=2] (relatively)

What now?

We have our pixel perfect collision world set up, working and really optimized in questions of performance when compared to the initial situation. How can we further optimize this collision system? Now we are entering the zone of game-specific intelligent collision! We have lots of ways of further optimizing this environment, so let's make some analysis of our previous situations!

Bounding Box Re-introduced

When we made that bounding box collision checker function we simply checked for:

1. Vertical collision Possibility
2. Horizontal collision Possibility

but let's look at our situation again: If you see, lots of the objects have approximately the same Y while different X coordinates. The ones with different Y will have different X as well... This will be most of the cases of our little game here! So, the majority of the collision tests will pass the first two tests with no conclusion and go to last 2 (horizontal check) where the collision will be denied. So, we are making lots of vertical tests that are inconclusive, while the most conclusive tests here are horizontal... If we simply swap the positions of both code parts, we will cut the number of comparisons to almost half of our original configuration. The result: bool colliding (Object OB1, Object OB2){ // Check the collision Horizontally /* checking horizontally first will make sure most of the functions will return false /* with one or two tests, instead of the previous use.*/ if (OB1left>OB2right) return false; if (OB2left>OB1right) return false; // Check the collision Vertically if (OB1bot>OB2top) return false; if (OB2bot>OB1top) return false; return true; } Now that we have optimized our bounding box algorithm logic, we have to move further to more advanced stuff.

Sector (Grid) Collision Check

If you pay attention to our grid, it has only 4 sections and the sections will have lots of objects in them. What if we increased the number of sections to... let's say... 10? What if, instead of dividing the scene into 4 cartesian-like quarters I divided it in horizontal sections? Well, here's the result of that: [color=#8B0000]Note: This horizontal grid makes testing vertical collisions unnecessary. If it was vertical, it would make horizontal collision checks unnecessary. You may want to make an optimized function when using these, if that's the case.[/color] Changing your grid will greatly influence the number of collision checks you'll make, changing how many sections, the sections' shapes... The smallest size of a section in this case should be the size of a soldier. If the grid was smaller than a soldier, there'd be soldiers in 6 different sections, bullets in 4 sections, and the number of collision tests would increase instead of diminish. So, how do I choose a size and shape for my grid? The only way I know is: Think and Try. Create a variable that stores the total number of bounding box collision checks made and take note of your grid and this number until you find an optimal grid configuration for your game, one that minimizes the number of calls. I've already used rectangular sections just like the first example and I've used vertical/horizontal sections as well. I've even used overlaping circular sections [size=2](worked really well as all my objects were circular) - it really depends on your game. [color=#8B0000]Another way to optimize this is to change your grid implementation to something better. Some implementations of collision sections use R-trees, quad trees, red-black trees and other kinds of segregation. I will not enter this realm since it's probably worthy a full post! But I'll leave some links at the bottom![/color] If you're interested try searching the net!

Intelligent Collision segregation

Now it gets a bit more complex and harder to make an example under a single simple situation as our little war zone here. How can we make our collision check smarter? Let's say in our game the bullets will pass through each other, they won't destroy when impacting with other bullets. This way, we can go ahead and remove all bullet vs bullet collision checks! The same can be done with allied soldiers, if in our game they block each other's way, we have to do the collisions, but if allied soldiers can run through each other, there's no need to collide them. The same with allied soldiers/allied bullets. If our game has no Friendly Fire, why calculate these collisions? As you can see here, this part is the one that depends the most on your game.

Pixel Perfect Collision

Now that we have done all we can to avoid doing pixel-perfect collisions and could not evaluate the collision as false, we'll have to do the pixel-perfect collision test. What'll we see here? 1 - How cover all the necessary pixels doing the necessary test to see if one of them is transparent 2 - How to simplify the pixel comparison So, first of all, we need to define what we are doing here. When testing sprites for collision, we have a collision when there's one or more non-transparent pixel of one sprite on the same global position of other non-transparent pixels of another sprite. In the first case, the images are colliding, while on the second they are not, despite of the confirmation of the bounding box check. What now? We have to do pixel versus pixel testing, to ensure that no pixel are overlaping any pixels on the second sprite. We now need to evaluate which pixels to check against which other ones. Remember that Bounding Box check where we took the top-left corner and bottom-right corner to calculate its coordinates? We have to do something like that here too. On a collision where the first object is above and to the left of the second object (like in the image), we have to test from the second sprite's top-left corner up to the bottom-right corner of the first sprite. This will give us a smaller test area, as can be seen here: There are four simple cases like this one here, the first object is to the top-left, top-right, bottom-left or finally to the bottom-right of the second object. There's also the possibility of an object being totally or partially (horizontally or vertically) inside the other. How to deal with so many possible cases? To simplify things up: Vertically, test from the lowest "top" coordinate (in [color="red"]red[/color] below) to the highest "bottom" coordinate (in [color="blue"]blue[/color]). Horizontally, test from the highest "left" coordinate (in [color="yellow"][background="darkgray"] yellow [/background][/color] ) to the lowest "right" coordinate (in [color="orange"]orange[/color]). Now that we understand what we need to do, time to move on to how to do it. Your collidable sprites, as parts of actors or any entities, probably have a position on your game's coordinate system. We have to take these into account when calculating the overlapping area of our sprites. When I say overlapping area, I mean the coordinates as described above. Let's take a look on how it would be done: int lowTop, highBottom, highLeft, lowRight if (OB1top>OB2top) lowTop = OB2top; else lowTop = OB1top; if (OB1bot>OB2bot) highBottom = OB1bot; else highBottom = OB2bot; if (OB1left>OB2left) highLeft = OB1left; else highLeft = OB2left; if (OB1right>OB2right) lowRight = OB2right; else lowRight = OB1right; We are going to use these numbers in order to create our loops and test our sprites against each other looking for colliding pixels. for (int h = highLeft; h <= lowRight; h++) { //horizontal for (int v = highBottom; v <= lowTop; v++) { //vertical //Do Tests } } Note that these coordinates are global, we'll probably have to do some math here, prior to starting the loop. In my example, I'll use a common system, where the bitmap starts on its top-left corner (top-left pixel has [0, 0] as its coordinates). How do we compare two pixels using the global coordinates, both sprites coordinates and those h and v values? First of all, we need to calculate offsets in order to adjust both values h and v to the sprites. The variables h and v are, in this case, both global. This means all we have to do here is adjust the "difference" between the global coordinate and the sprite coordinate od the pixel. In this case, the horizontal coordinate has the same orientation on both, sprite and world systems, but the vertical doesn't, as the sprite counts from up-down, opposite to the global system. We can make a simple function to adjust this when testing: vector2d globalToSprite (entity Obj, vector2d GlobalPosition){ vector2d adjusted; //Obj.position holds the position of the topLeft corner of the object. adjusted.x = GlobalPosition.x - Obj.position.x; adjusted.y = Obj.position.y - GlobalPosition.y; //This inversion happens due to the //reverse vertical coordinate on the sprite. return adjusted; }You could also make it two inline functions, one for horizontal and other for vertical adjust, or even better, implement this adjust inside your sprite/entity class. Just as a reminder, how you handle your coordinates is completely up to you. Now that we have our loop and adjust functions, we can finally do the tests. vector2d OB1adjusted = globalToSprite (OB1, toVector(h, v)); //Adjust First Offset vector2d OB2adjusted = globalToSprite (OB2, toVector(h, v)); //Adjust Second Offset if ( !OB1.sprite.isTransparent(OB1adjusted) && !OB2.sprite.isTransparent(OB2adjusted) ) return true; //Returns true if both sprites are non-transparents on the pixel being tested. //This means we have a collision. Compiling the final function, this is what we'd have: bool pxCollision (entity OB1, entity OB2){ //Creating loop control variables int lowTop, highBottom, highLeft, lowRight; //Calculating the "Lowest Top" of both sprites if (OB1.top()>OB2.top()) lowTop = OB2.top(); else lowTop = OB1.top(); //Calculating the "Highest Bottom" of both sprites if (OB1.bot()>OB2.bot()) highBottom = OB1.bot(); else highBottom = OB2.bot(); //Calculating the "Highest Left" of both sprites if (OB1.left()>OB2.left()) highLeft = OB1.left(); else highLeft = OB2.left(); //Calculating the "Lowest Right" of both sprites if (OB1.right()>OB2.right()) lowRight = OB2.right(); else lowRight = OB1.right(); for (int h = highLeft; h <= lowRight; h++) { //Horizontal check from Highest Left to Lowest Right for (int v = highBottom; v <= lowTop; v++) { //Vertical, from Highest Bottom to Lowest Top vector2d OB1adjusted = globalToSprite (OB1, toVector(h, v)); //Adjust Offset for OB1 vector2d OB2adjusted = globalToSprite (OB2, toVector(h, v)); //Adjust Offset for OB2 if ( !OB1.sprite.isTransparent(OB1adjusted) && !OB2.sprite.isTransparent(OB2adjusted) ) return true; //If both pixels are simultaneously non-transparent, we have a collision. } } return false; //No collision detected, there was always at least one transparent pixel } As you can see, this is a really costly operation and that's why we try to avoid calling it as much as possible! We can also make things faster by creating "collision masks" for our sprites when creating them. These masks can be bitmaps, matrixes or anything that can perform a check faster than our isTransparent() function. They would be generated right after the sprite itself, during the entity construction and then used over and over until the entity itself get destroyed. If you share a sprite between multiple entities, create the mask once and use for every one of them, until the sprite itself is destroyed. I personally like to use boolean matrixes void generateCollisionMatrix (bool* matrix, sprite Spr){ for (int i = 0; i < Spr.size.w; i++) for (int j = 0; j < Spr.size.h; j++) if ( Spr.isTransparent( toVector(i,j) ) ) matrix[j] = 0; else matrix[j] = 1; } If we had done this prior to our pxCollision function call, look what our if statement would be:if ( !OB1.colMatrix(OB1adjusted) && !OB2.colMatrix(OB2adjusted) ) return true;We just turned two isTransparent calls into simple getter functions that can be faster depending on the implementation of your isTransparent. Now that our function is done, it'll return true on collision or false otherwise. Did you notice how rectangles always return true when testing their pixels? If you are familiar with OO programming, it would be wise to replace their isTransparent function with one that always returns true.

Good Sources

http://www.gamedev.n...-detection-r735 http://www.flipcode....ersection.shtml http://www.metanetso.../tutorialA.html http://go.colorize.n..._xna/index.html http://www.fourtwo.s...exing-in-a-grid http://gamedev.stack...gic-into-action http://stackoverflow...ision-detection http://stackoverflow...for-a-game-in-c http://www.gamasutra...s_for_games.php http://www.wildbunny...on-for-dummies/ soldier sprite taken from the flying yogi's SpriteLib (here)

Appendix A: Circular Collision Detection

To calculate if two circles are colliding, you need to check if the distance between their centers is less than the sum of their radius. Some games have the collision between entities as being simple circle collisions. This way, the entities need only a 2D position and a Radius. bool colliding (Object OB1, Object OB2){ if ( squared(OB1.x-OB2.x) + squared(OB1.y-OB2.y) < squared(OB1.Radius+OB2.Radius)) return true; return false; }