Create a custom theme
Intelligent 2D collision and Pixel Perfect precision
Posted by dejaime,
in
Basic 2D Posts
22 December 2011
·
3,644 views
Please feel free to comment and tell me if I missed something or if there's anything wrong! Feedback is really appreciated!
Intelligent 2D collision and Pixel Perfect precision
When you're making a 2D game where collision is an important factor, the more precise your logic is, the better! But perfect colision in 2D games oftenly involve pixel perfect collision, what 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 the collision will affect the game. What to do now? There're lots of ways to reduce this overhead, we'll discuss some of them here today.
For the post, 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 is the bounding box check.
The bounding box check is both, the most easy 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, that has 4 coordinates: OB1top, OB1bot, OB1Left, OB1Right, the same for OB2.
Where
Now you create something similar to this:
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 deppends alot 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 immagine if instead of 6 soldiers, we had 12, and all of them shot twice as much projectiles, total 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 (~=10.8)! As you can see, it's impracticable.
How can we further increase our collision performance if we already removed almost all pixel level collisions?
The answer is still simple, we 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, sectionize it, so you will check collisions only between objects in the same sections!
Sector (Grid) Collision Check
Using both, grid and bounding box, you'll have this:
As can be seen here, there're 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? bbox 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:
Ta-da! Our collision system is finally optimized and ready to grow in scale! (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, let's make some analysis of our previous situations!
Bounding Box introduced
When we made that bounding box collision checker function we simply checked for:
If you see, lots of the objects have approximatedly 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 a half of it's original configuration, result:
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, 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 in 4 cartesian-like quarters I divided in horizontal sections?
Well, here's the result of this:
Note: This horizontal grid makes testing horizontal collision check unnecessary. If it was vertical, it would make vertical collision unnecessary.
You may want to make an optimized function w/o these, if that's the case.
Changing your grid will greatly influence the number of collision checks you'll make, changing how many sections, the sections' shapes...
The least size of a section 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, instead of diminish, increase.
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 bbox collisions checks made and take note of your grid and this number until you find an optimus grid configuration for your game, one that minimizes the number of calls.
I've already used rectangular sections just like the first example, I've used vertical/horizontal sections, I've even used overlaping circular sections (worked really well as all my objects were circular), It really depends on your game.
Other way to optimize this is to change your grid implementation to something better.
Some implementations of collision sections uses quad trees, red-black trees and other kind 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!
If you're interested try searching the net!
Intelligent Collision segregation
Now it gets a bit more complex and harder to make 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!
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?
(Has lol) As you can see here, this part is the one that depends the most on your game.
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.
Intelligent 2D collision and Pixel Perfect precision
When you're making a 2D game where collision is an important factor, the more precise your logic is, the better! But perfect colision in 2D games oftenly involve pixel perfect collision, what 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 the collision will affect the game. What to do now? There're lots of ways to reduce this overhead, we'll discuss some of them here today.
For the post, 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 is the bounding box check.
The bounding box check is both, the most easy 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, that has 4 coordinates: 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 deppends alot 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 immagine if instead of 6 soldiers, we had 12, and all of them shot twice as much projectiles, total 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 (~=10.8)! As you can see, it's impracticable.
How can we further increase our collision performance if we already removed almost all pixel level collisions?
The answer is still simple, we 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, sectionize it, so you will check collisions only between objects in the same sections!
Sector (Grid) Collision Check
Using both, grid and bounding box, you'll have this:
As can be seen here, there're 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? bbox 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<Object*> allObjectsList; //Contains all active objects
std::list<Object*> 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[i]) )
insert (allObjectsList[obj], sectionList[i])
}
}
Ta-da! Our collision system is finally optimized and ready to grow in scale! (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, let's make some analysis of our previous situations!
Bounding Box introduced
When we made that bounding box collision checker function we simply checked for:
- Vertical collision Possibility
- Horizontal collision Possibility
If you see, lots of the objects have approximatedly 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 a half of it's original configuration, 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, 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 in 4 cartesian-like quarters I divided in horizontal sections?
Well, here's the result of this:
Note: This horizontal grid makes testing horizontal collision check unnecessary. If it was vertical, it would make vertical collision unnecessary.
You may want to make an optimized function w/o these, if that's the case.
Changing your grid will greatly influence the number of collision checks you'll make, changing how many sections, the sections' shapes...
The least size of a section 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, instead of diminish, increase.
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 bbox collisions checks made and take note of your grid and this number until you find an optimus grid configuration for your game, one that minimizes the number of calls.
I've already used rectangular sections just like the first example, I've used vertical/horizontal sections, I've even used overlaping circular sections (worked really well as all my objects were circular), It really depends on your game.
Other way to optimize this is to change your grid implementation to something better.
Some implementations of collision sections uses quad trees, red-black trees and other kind 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!
If you're interested try searching the net!
Intelligent Collision segregation
Now it gets a bit more complex and harder to make 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!
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?
(
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 ((OB1.x-OB2.x)²+(OB1.y-OB2.y)²<(OB1.Radius+OB2.Radius)²) return true;
return false;
}
I personally use bounding box collision for most projects, and sometimes I mix in using an array to check a grid. I rarely use Pixel Perfect unless need be, but I have a great desire to make more classic games.
Keep up the great work!