Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
18Likes
Dislike

Intelligent 2D Collision and Pixel Perfect Precision

By Dejaime Antônio de Oliveira Neto | Published Aug 17 2013 12:36 AM in Game Programming
Peer Reviewed by (Dave Hunt, BeerNutts, Dragonsoulj)

2d collision detection pixel precision sprites bounding box

Originally published in 22 December 2011.

Please feel free to comment and tell me if I missed something or if there's anything wrong! Feedback is really appreciated!

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:


Attached Image: 2hqqdj6.png


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.


Attached Image: b843u8.png


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.


Attached Image: n6sx2r.png


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 (~=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:


Attached Image: 1zowxus.png


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<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, 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:


Attached Image: 2hqqdj6.png


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:


Attached Image: 206blhf.png


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.

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 (worked really well as all my objects were circular) - it really depends on your game.

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!

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.

Attached Image: Untitled.png

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:

Attached Image: Untitled2.png

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.

Attached Image: Untitled3.png

How to deal with so many possible cases?
To simplify things up:
Vertically, test from the lowest "top" coordinate (in red below) to the highest "bottom" coordinate (in blue).
Horizontally, test from the highest "left" coordinate (in yellow ) to the lowest "right" coordinate (in orange).

Attached Image: Untitled4.png

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[i][j] = 0;
			else matrix[i][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;

}



License


GDOL (Gamedev.net Open License)




Comments

thanks

Very interesting read. I hadn't heard of breaking the world up into sections. But I'm still confused as to how this helps provide pixel-perfect collision detection. It minimizes unnecessary tests, which is great, but how, for example, would I check if a hexagon and a rotated diamond were touching using the stuff you described?

 

I also like that you pointed out some obvious stuff that I hadn't actually thought about until now, like the fact that horizontal collision is usually the best thing to test first.

 

Anyway, thanks for the article!

Very interesting read. I hadn't heard of breaking the world up into sections. But I'm still confused as to how this helps provide pixel-perfect collision detection. It minimizes unnecessary tests, which is great, but how, for example, would I check if a hexagon and a rotated diamond were touching using the stuff you described?
 
I also like that you pointed out some obvious stuff that I hadn't actually thought about until now, like the fact that horizontal collision is usually the best thing to test first.
 
Anyway, thanks for the article!

Sorry, looks like I neglected the pixel collision itself!

Removed mistaken answer, I'll add that content to the article soon.

Take a look at this link here: http://wiki.allegro.cc/index.php?title=Pixel_Perfect_Collision

I've used the peer review system to vote that your article is "unclear or incomplete", simply because it promises to introduce pixel-perfect collision detection, but (as already noted) fails to actually do so.

 

Otherwise, it's a good article, and I'll be more than happy to reverse my vote if you either edit the article to include pixel-perfect, or simply edit the title and introduction to remove the suggestion that pixel-perfect will be covered! 

 

Great contribution -- I just don't want people to be mislead by the title if you're not actually covering that subject. :-)

 

Pixel perfect is now included in the article.  I haven't had time to verify correctness, but I'm resetting my vote marking the article as "unclear or incomplete" for now. smile.png

Your pixel collision functions are wrong. You don't take into account the relative positions of the sprites, for starters. Even with the generous assumption that both sprites are the same size and at the same location, your function checks all pixels against all pixels. This means that if both sprites have a non transparent pixel it will return true, regardless of where the pixel is within the sprite. I expect every sprite to have a non-transparent pixel.

 

I've taken the time to write a highly optimized version of your function:

return true;

why don't you introduce quadtree instead of this weird line thing ? I was expecting some information about it when you started to talk about grid separation optimization.

I seriously hope you don't update the article using the code you posted in response to @Shaquil above. As @RAXORUNREAL pointed out, that code is seriously flawed. Both the unoptimized and optimized versions are broken.

 

Perhaps you should just change the title and let the article focus on avoiding premature pixel perfect collision checking...

The code I wrote is in fact wrong, I am sorry for that mistaken late night post.
 
I'll just add the content to the article itself later.
 

why don't you introduce quadtree instead of this weird line thing ? I was expecting some information about it when you started to talk about grid separation optimization.

Quad-Trees, R-Trees, Red-Blacks all need some knowledge on Data Structures that I'm assuming the reader doesn't necessarily have, given this is a guide for complete beginners, aiming for need of a really basic game.
 
If I ever create a new article on this, I'll give the trees the attention deserve.
Hi again,

The missing content is now online, anyone, please review it and look for any mistakes or missing stuff, I'll fix the article asap.

Thank you!

If I were to need to implement pixel perfect collision, I would be very interested in trying out a span map across the horizontal axis of the game at the pixel level. In theory it would be a fast spatial subdivision and mechanisms to test the pixel collision all in 1 data structure.

 

If you create a pointer array(representing head pointers of a linked list) with the size based on the number of horizontal pixels across the level, and then create a linked list of occupancy spans on each of those elements. Then, knowing the bounding box of any entity, and having its own span map representing its pixel occupancy, you can pretty easily index into the span map based on the current position and step through the linked list of occupancies to check for overlaps. The code should all be very simple, and since the spatial subdivision and collision testing is essentially automatic in the data structure representation, you don't need to maintain a higher level subdivision. In fact, the operation of adding an entity to the span map by linking it in to the horizontal spans it is touching is basically a spot in the code where you can mark touching entities as part of putting them into the structure, so querying for overlaps between 2 entities would basically be free, as they could be cached as part of them being added to the structure. In your sample images, each horizontal pixel row probably wouldn't exceed 4-5 spans in their lists, so the searches would be trivial and cache friendly.

 

Anyone ever considered doing pixel collision in this way?

You can avoid rebuilding the section grid each frame by having it persist between frames and make objects maintain their grid data positions, removing and re-inserting themselves when they move to a different grid cell. Since most objects are unlikely to be moving more than 1 cell per frame this would likely be an efficiency gain.


Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS