AABB Collision Detection And Response [TUTORIAL]

[N64vSNES]

I got logged out so I'm writing this for a second time. >:(

I've not really contributed anything to the forum yet so I guessed it's time.

Introduction:
So many people are still asking how this is done past the basics and I've seen a lot of talk about collision on this forum but not any "actual tutorials" so enjoy.

So I hope this tutorial will help you understand it better, I'll be going through everything I know of collision detection starting from basic and moving onto more advanced stuff.
Also I will be using SDL and OpenGL with C++ but I'll try to keep that on a different level of abstraction.

Starting From Basics
The fastest and most simple way of detecting collision is simply saying "Is this and this colliding? Y/N".

Code: Select all

bool Eternal::IsCollision(Rectangle *a, Rectangle *b) {
	if ( a->x + a->w > b->x
      && a->x < b->x + b->w
      && a->y + a->h > b->y
      && a->y < b->y + b->h ) {
      return true;
    }
}

Collision:

None Collision:


Collison detection AND response
What's collision detection without response? We need to make objects solid so we aren't simply informing the player that he's walking through a brick wall.

We could simply do this:

Code: Select all

if ( IsCollision(A,B) ) {
	if ( KeyLeft() ) {
		A.x++;
	}
	else if ( KeyRight() ) {
		A.x--;
	}
	if ( KeyUp() ) {
		A.y++;
	}
	else if ( KeyDown() ) {
		A.y--;
	}
}

But this method seems to feel stiff and un-natural in games where you game 8 directional movement instead of 4 directional per-tile movement.

The work-around is to calculate the overlap of each axis and figure out which one to act upon.

Code: Select all

bool IsCollision(Rectangle *a, Rectangle *b, Vector2 &normal) {

 /* Since the vector is a pointer then it could have been
	intialized to any value so we need to make sure we initalize
	the vectors X and Y to zero */
	normal.x = 0;
	normal.y = 0;

	// The distance between the two objects
	Vector2 Distance;
	// The absDistance between the objects
	Vector2 absDistance;

	float XMagnitute;
	float YMagnitute;

	// Calculate the distance between A and B
	Distance.x = ( ( b->x ) - ( a->x ) );
	Distance.y = ( ( b->y ) - ( a->y ) );

	// Combine both rectangles and half the returned value
	float XAdd = ( ( b->w ) + ( a->w ) ) / 2.0f;
	float YAdd = ( ( b->h ) + ( a->h ) ) / 2.0f;

	// Check if the Distance vector is below 0.0f
	absDistance.x = ( Distance.x < 0.0f ) ? -Distance.x : Distance.x;
	absDistance.y = ( Distance.y < 0.0f ) ? -Distance.y : Distance.y;

	 /*If the absDistance X is less than X add and the absDistance is less thank YAdd
	 then it dosen't take a genius to figure out they arn't colliding so return false*/
	if( ! ( ( absDistance.x < XAdd ) && ( absDistance.y < YAdd ) ) ) {	
	return false;
	}

	/*Get the magnitute by the overlap of the two rectangles*/
	 XMagnitute = XAdd - absDistance.x;
	 YMagnitute = YAdd - absDistance.y;

	/*Determin what axis we need to act on based on the overlap*/
	 if( XMagnitute < YMagnitute ) {
      normal.x = ( Distance.x > 0) ? -XMagnitute : XMagnitute;
	 }
	 else if ( XMagnitute > YMagnitute ) {
      normal.y = ( Distance.y > 0) ? -YMagnitute : YMagnitute;
	}
	// If we reached this point then we now know the was a collision
	return true;

}

I've commented the fuck out of it but I'll go through this in case something doesn't make sense.

Code: Select all

normal.x = 0;
normal.y = 0;

Because the vector is passed by reference we need to make sure the values are at 0, this is important for later.

Code: Select all

Vector2 Distance;
Vector2 absDistance;

float XMagnitute;
float YMagnitute;

This is going to be used to store the distance and the magnitute. I'll explain it further in detail as I get to them.

Code: Select all

Distance.x = ( ( b->x ) - ( a->x ) );
Distance.y = ( ( b->y ) - ( a->y ) );

Nothing complex here, subtract A from B to calculate the distance between the two rectangles.

Code: Select all

float XAdd = ( ( b->w ) + ( a->w ) ) / 2.0f;
float YAdd = ( ( b->h ) + ( a->h ) ) / 2.0f;

Once again, nothing complex. We combine the widths and heights and half it to create a area of collision.

Code: Select all

absDistance.x = ( Distance.x < 0.0f ) ? -Distance.x : Distance.x;
absDistance.y = ( Distance.y < 0.0f ) ? -Distance.y : Distance.y;

And yet again, nothing complex. We set the absDistance to either the +Distance or -Distance depending on the Distance being a positive or negative value.

Code: Select all

if( ! ( ( absDistance.x < XAdd ) && ( absDistance.y < YAdd ) ) ) {	
	return false;
}

If the absDistance is not within the area of collision we just created then the is no collision.
No point going any further, return false and be done with it.

Code: Select all

XMagnitute = XAdd - absDistance.x;
YMagnitute = YAdd - absDistance.y;

Now the clever bit here is we subtract absDistance from the area of collision we created to leave the over lap values.

Code: Select all

if( XMagnitute < YMagnitute ) {
      normal.x = ( Distance.x > 0) ? -XMagnitute : XMagnitute;
}
else if ( XMagnitute > YMagnitute ) {
      normal.y = ( Distance.y > 0) ? -YMagnitute : YMagnitute;
}

Now if we updated the normal's X and Y then it would seem like the 4 directional per-tile movement collision. So we check if XMagnitute or the YMagnitute is greater and the least significant is the one we act on.


Now we can say something like

Code: Select all

Vector2 norm;
if ( IsCollision(&a,&b,norm) ) {
	a.x += norm.x;
	a.y += norm.y;
}

And this can be used to prevent objects from colliding with each other.

Collision:

None Collision:


Notice how the red flashing has gone with the collision?
That's because it's now pushing the object away so it can't intersect with it.

Circular Collision Detection (Because nobody ever talks about it)
This is something I've never seen discussed. But it's pretty straightforward and efficient.

The main advantage to collision detection with a circle is that it has a set radius equal all around it.

Code: Select all

bool IsCollision(Circle a, Circle b) {
	float distX = b.x - a.x;
	float distY = b.y - a.y;
	int radist = a.radius + b.radius;
	if ( distX  * distX  + distY * distY < radist * radist) {
		return true;
	}
	return false;
}

So we use that radius as a "area of collision". You could always add some collision response etc on top of this.

I hope this helps someone, a while back it would've helped me.

I've tested all the code as seen but let me know if you find anything wrong with it.

[Avishaiozeri]

Thanks for the tutorial, its been very helpful! I have a question though..

When you showed the simple way to find collision:

Code: Select all

bool Eternal::IsCollision(Rectangle *a, Rectangle *b) {
	if ( a->x + b->w > b->x
		&& a->x - b->w < b->x
		&& a->y + b->h > b->y
		&& a->y - b->h < b->y ) {
		return true;
	}
	return false;
}

Why did you add B's width and height to A's x and y? that doesn't make any sense.. If the rectangles are in two different shapes, then this would happen:



Shouldn't you add A's own width to its x? so: A->x + A->w > B->x && A->x - A->w < b->x. (Same with y: A->y + A->h > B->y && A->y - A->h < b->y)
That would solve the problem.. But then this happens:



To solve this you just do two check: if A is in B, and if B is in A:

Code: Select all

//check if A is in B
if ( A->x + A->w > B->x && A->X - A->w < B->x)
{
     //collision on  X axis!
}
//check if B is in A
if ( B->x + B->w > A->x && B->X - B->w < A->x)
{
     //collision on X axis!
}

Then it should always find the collision..
(I didn't add the check for collision on the Y axis, but you get the point...)

Am I right? Or am i a complete idiot and just didn't get your way of doing it?

[N64vSNES]

Thanks for the tutorial, its been very helpful! I have a question though..

When you showed the simple way to find collision:

Code: Select all

bool Eternal::IsCollision(Rectangle *a, Rectangle *b) {
	if ( a->x + b->w > b->x
		&& a->x - b->w < b->x
		&& a->y + b->h > b->y
		&& a->y - b->h < b->y ) {
		return true;
	}
	return false;
}

Why did you add B's width and height to A's x and y? that doesn't make any sense.. If the rectangles are in two different shapes, then this would happen:

That's the exact logic being performed, you would draw a line, but we're not checking if it's intersecting the rectangle are we?
Look closely:
if ( a->x + b->w > b->x
&& a->x - b->w < b->x
&& a->y + b->h > b->y
&& a->y - b->h < b->y ) {
return true;
}
We're checking if it's greater than the X position of the rectangle, which is the center. Is that line's length on the X-axis greater than the position of the center? No. So there would be no collision

So remember, we check if it's greater than the position (the center) NOT if it's greater than the position of the closest face.

When you turn it around and use the dimensions of A on A's position, then that will work for most cases. It will work perfectly if both rectangles are of the same dimensions. But if you want the two objects to be of different dimensions, you need to use the B's dimensions. (as you pointed out).

You've very nearly got it, but you seem to think that we're checking if the line touches the rectangle at all. When really, we're not. Only checking if it's greater than the center position.

[Avishaiozeri]

Thanks for the tutorial, its been very helpful! I have a question though..

When you showed the simple way to find collision:

Code: Select all

bool Eternal::IsCollision(Rectangle *a, Rectangle *b) {
	if ( a->x + b->w > b->x
		&& a->x - b->w < b->x
		&& a->y + b->h > b->y
		&& a->y - b->h < b->y ) {
		return true;
	}
	return false;
}

Why did you add B's width and height to A's x and y? that doesn't make any sense.. If the rectangles are in two different shapes, then this would happen:

That's the exact logic being performed, you would draw a line, but we're not checking if it's intersecting the rectangle are we?
Look closely:
if ( a->x + b->w > b->x
&& a->x - b->w < b->x
&& a->y + b->h > b->y
&& a->y - b->h < b->y ) {
return true;
}
We're checking if it's greater than the X position of the rectangle, which is the center. Is that line's length on the X-axis greater than the position of the center? No. So there would be no collision

So remember, we check if it's greater than the position (the center) NOT if it's greater than the position of the closest face.

When you turn it around and use the dimensions of A on A's position, then that will work for most cases. It will work perfectly if both rectangles are of the same dimensions. But if you want the two objects to be of different dimensions, you need to use the B's dimensions. (as you pointed out).

You've very nearly got it, but you seem to think that we're checking if the line touches the rectangle at all. When really, we're not. Only checking if it's greater than the center position.

Oh, the x is the middle spot? I'm using SDL, so for me its the top left point... But still, there can never be a situation where the middle of A + The width of B are greater than the middle of B, and the two rects aren't colliding?

[N64vSNES]

Oh, the x is the middle spot? I'm using SDL, so for me its the top left spot...

Correct. And SDL, Allegro, etc It does not matter. You're the one who decides where the center spot is.

Take the center, transform it and then pass it to SDL if you have to. Or, if you are too lazy, a few lines of code in the collision function can easily fix it.

Code: Select all

int newAX = a->x + (a->w / 2);
int newAY = a->y + (a->h / 2);

If your still struggling with it or anyone else is who comes across this post, here is the actual logic being performed:

[Avishaiozeri]

Wait, I still didn't get it, what about this condition? :

[dandymcgee]

Let me make this easy for you.

Assuming the position (x,y) is the center of the object, you want to check if the distance between the centers is less than the sum of the half-widths for both the x and y axis.

Code: Select all

int deltax = abs(b->x - a->x);
int deltay = abs(b->y - a->y);
if(deltax < (a->w / 2 + b->w / 2) && deltay < (a->h / 2 + b->h / 2) {
    collision = true;
}

Assuming the position (x,y) is the top-left corner of the object, you want to check if opposite edges overlap.

Code: Select all

if ( a->x + a->w > b->x
      && a->x < b->x + b->w
      && a->y + a->h > b->y
      && a->y < b->y + b->h ) {
    return true;
}

Please note: This is not the same as the similar looking code posted above. That code was incorrect.

[Avishaiozeri]

Let me make this easy for you.

Assuming the position (x,y) is the center of the object, you want to check if the distance between the centers is less than the sum of the half-widths for both the x and y axis.

Code: Select all

int deltax = abs(b->x - a->x);
int deltay = abs(b->y - a->y);
if(deltax < (a->w / 2 + b->w / 2) && deltay < (a->h / 2 + b->h / 2) {
    collision = true;
}

Assuming the position (x,y) is the top-left corner of the object, you want to check if opposite edges overlap.

Code: Select all

if ( a->x + a->w > b->x
      && a->x < b->x + b->w
      && a->y + a->h > b->y
      && a->y < b->y + b->h ) {
    return true;
}

Please note: This is not the same as the similar looking code posted above. That code was incorrect.

Its a very nice way of doing it. But Is this what N64vSNES meant? He said to add the width of B to the x of A, and check if its bigger then the middle of B. Is it possible to detect collision like that?

[dandymcgee]

Its a very nice way of doing it. But Is this what N64vSNES meant? He said to add the width of B to the x of A, and check if its bigger then the middle of B. Is it possible to detect collision like that?

No. That is wrong and will not detect all (if any?) cases of collision properly, as you clearly pointed out with your diagram.

Edit: Just now realizing this was a tutorial topic. N64, you may want to double-check your code with some test cases. I don't mean to undermine your obvious effort, but I do believe the code is incorrect.

[Avishaiozeri]

I have a question..
I'm currently working on a tile based side-scroller.. The collision detection I'm using now is terrible, I just move the player/mob/item 1 pixel for each frame, and check for collision with solids in their area. If a collision is detected, I simply move them 1 pixel back... I've decided to stop doing it like that, and now I want to move the objects more each frame.. The problem is, I still didn't get how the "separating axis theorem" works, and can't get the collision detection working! Any advice?

[N64vSNES]

You're absolutely right dandymcgee, good thing you pointed this out.

It did work on objects of the same dimensions, as shown in the screenshot of the first post, but if you want to change the size then it's fucked.

Apologies to anyone I successfully confused the shit out of other than myself

I've edited the post, and fixed it. I wrote this a while back I think most people just use it for the resolution code.

I have a question..
I'm currently working on a tile based side-scroller.. The collision detection I'm using now is terrible, I just move the player/mob/item 1 pixel for each frame, and check for collision with solids in their area. If a collision is detected, I simply move them 1 pixel back... I've decided to stop doing it like that, and now I want to move the objects more each frame.. The problem is, I still didn't get how the "separating axis theorem" works, and can't get the collision detection working! Any advice?

For detection, this works:

Code: Select all

if ( a->x + a->w > b->x
      && a->x < b->x + b->w
      && a->y + a->h > b->y
      && a->y < b->y + b->h ) {
    return true;
}

I've literally just tested it 5 minutes ago, so no worries this time.

For actually acting on a collision, there is no need for the separating axis theorem. That's for if you want to check for collisions against oriented bounding boxes.

Just refer to the second section of my tutorial, it was tested as it was written so it should work. The part about calculating the overlap values.

Once again, sorry for the confusion, nothing annoys me more than when tutorials get written incorrectly.

[dandymcgee]

It did work on objects of the same dimensions, as shown in the screenshot of the first post, but if you want to change the size then it's fucked.

Ahh, that makes sense. I didn't even realize how old this was.