(Collision Detection) Move Object 1 To Edge Of Object 2

[Master Jake]

When I google "SDL Collision Detection" I find this code re-used over, and over, and over again.

Code: Select all

int IsCollision(SDL_Rect *r1, SDL_Rect *r2)
{
	if (r1->x + r1->w < r2->x ||
	    r1->x > r2->x + r2->w ||
	    r1->y + r1->h < r2->y ||
	    r1->y > r2->y + r2->h)
		return 0;
	
	else
		return 1;
}

The problem with this code is that it only tells if you if there is a collision and I need to know from what side the collision occurred.

Why?

Say we have 2 objects, square and ball.

Square is stationary, ball is moving at 5 pixels per frame (60 frames per second).

Using the above collision detection code, we can move ball 5 pixels in whatever direction each frame and then check if there was a collision. If there was, we just reverse the x (and/or) y velocities of the ball and move it back that many pixels.

The problem with that is, unless the ball collides perfectly 5 pixels inside the square, then when we move it back those 5 pixels, it won't be directly on the edge of the square but some pixels off.

This would be horrible in a platform game or any game in general really, because it's not precise.

As lazy foo stated, the better way of going about this would be to check:

"If there is a collision, move object 2 to the outskirts of object 1 on the side in which object 2 collided."

For instance, if the ball hit the square from the right side of the square, move the balls x coordinate to the squares x coordinate plus the squares width (assuming the x, y native point for the square was the top left corner, which in my case it is).

-----

So sorry for the long drawn out explanation. I just wanted everyone to be on the same page as me.

I can't use precise detection if I don't know which side the collision occured from.

I searched these forums and found a post Falco made not to long ago about separating axis theorem which I haven't gotten into yet. I wasn't able to get that code to work properly with my game for some reason. Even so, that only checks if the collision was x or y which checks the left, right, and up, down sides. I need to check from all 4 sides since I'm using square-based objects.

-----

If anyone knows of a better way of doing this, please let me know.

[Falco Girgis]

I answered an extremely similar problem (pretty much the exact same thing) with detailed explanation and code here: http://elysianshadows.com/phpBB3/viewto ... art=999999. I think you will find that extremely helpful.

Basically, you want to resolve the collision by determining a collision normal (direction) and depth (amount of penetration), and move one of the objects back along the normal.

I searched these forums and found a post Falco made not to long ago about separating axis theorem which I haven't gotten into yet. I wasn't able to get that code to work properly with my game for some reason. Even so, that only checks if the collision was x or y which checks the left, right, and up, down sides. I need to check from all 4 sides since I'm using square-based objects.

...I have no idea what you're trying to say here.

Utilizing separating axis theorem based collision would solve your issue and then some. It's the equivalent to your problem (and the one in the link that I posted) for oriented bounding boxes--meaning they can both be rotated at different angles for collision.

[Master Jake]

That's actually the same post I was talking about.

I couldn't get the code to work properly. There were "conversion warnings [loss of data]" probably because my coords are ints instead of floats. So I changed all the necessary datatypes in the function to ints, and set it up basically like this:

Code: Select all

int IsCollision(SDL_Rect *rect1, SDL_Rect *rect2)
{
    //Determine overlap for each axis
    int xDist = abs((rect1->x + rect1->w / 2) - (rect2->x + rect2->w / 2)); // x + width / 2 so that the x is in the center of the square
    int yDist = abs((rect1->y + rect2->h / 2) - (rect2->y + rect2->h / 2)); // ditto

    //minimal amount of distance that the two can be apart and not collide
    int xMinDist = rect1->w + rect2->w;
    int yMinDist = rect1->h + rect2->h;

    if(xDist >= xMinDist || yDist >= yMinDist)
		return 0; //neither axis is colliding

    int xOverlap = xDist - xMinDist;
    int yOverlap = yDist - yMinDist;

    if(xOverlap < yOverlap)
		return 1;
    
	else
		return 2;

    return 1;
}

That for the function and then this for the other stuff:

Code: Select all

		// Ball collision paddle_p1
		if (IsCollision(Ball.GetBounds(), Paddle_P1.GetBounds()) == 1)
		{
			Ball.SetXVel(-Ball.GetXVel());
			Ball.SetX(Ball.GetBounds()->x + Ball.GetXVel());
		}
		else if (IsCollision(Ball.GetBounds(), Paddle_P1.GetBounds()) == 2)
		{
			Ball.SetYVel(-Ball.GetYVel());
			Ball.SetY(Ball.GetBounds()->y + Ball.GetYVel());
		}

It should reverse X velocity if it hits from left or right and reverse y if it hits from top or bottom.

But instead, it does something weird. When the ball gets close to the paddle, it sucks it in and then spits it out. It's really weird.

Also, even if I could get it to work, how would I set it up to move it to the edge of the side of the paddle it's colliding with?

[Falco Girgis]

It looks like my previous algorithm had a minimal overlap region that was too wide, because I combined the full widths, rather than the half-widths. That's why I put a disclaimer that it wasn't tested.

I'm going to do something that I normally don't do and give you our actual axis-aligned bounding box collision code from the Elysian Shadows engine. It's guaranteed to work, just remember to move your objects' position to the center (as in the previous algorithm you posted).

Code: Select all

bool AABBCollision(Collidable *body1, Collidable *body2, Vector2 &normal) {
	// The normal vector has to be reset every time this function is called.
	// At this point we do not know which of its components will change to push the object being collided with.
	// The other component is always zero.
	normal.x = 0;
	normal.y = 0;

	Vector2 distance, absDistance;

	// xMag and yMag represent the magnitudes of the x and y components of the normal vector.
	float xMag, yMag;

	// Calculate the difference in position of the two rectangles.
	distance = body2->position - body1->position;

	// xAdd is the combined half-widths of the two rectangles.
	// yAdd is the combined half-heights of the two rectangles.
	float xAdd = ((body1->size.x * body1->scale.x) + (body2->size.x * body2->scale.x)) / 2.0f;
	float yAdd = ((body1->size.y * body1->scale.y) + (body2->size.y * body2->scale.y)) / 2.0f;

	//printf("body1.size %f, %f\n", body1->size.x, body1->size.y);
//	printf("body2.size %f, %f\n", body2->size.x, body2->size.y);

	// Calculate absDistance, according to distance.
	// This will actually be used to determine whether or not the two rectangles are colliding.
	(distance.x < 0) ? absDistance.x = distance.x * -1 : absDistance.x = distance.x;
	(distance.y < 0) ? absDistance.y = distance.y * -1 : absDistance.y = distance.y;

	// The two rectangles are not colliding if both of the following statements evaluate to false:
	// 1. The distance between their x position is less than their combined half-widths.
	// 2. The distance between their y position is less than their combined half-heights.
	// So return false as soon as we know there's no collision!
	if(!((absDistance.x < xAdd) && (absDistance.y < yAdd))) return false;

	// Otherwise, there is a collision:

	// The magnitude of the normal vector is determined by the overlap in the rectangles.
	xMag = xAdd - absDistance.x;
	yMag = yAdd - absDistance.y;

	// Only adjust the normal vector in the direction of the least significant overlap.
	if(xMag < yMag)
		normal.x = (distance.x > 0) ? xMag : -xMag;
	else
		normal.y = (distance.y > 0) ? yMag : -yMag;

	return true;
}

The function returns a bool depending on whether or not a collision was detected. It also returns a collision normal, which is the axis (and amount--it's not normalized) that the collision occurred on.

What does that mean to you? If you move object A by the collision normal like so:

Code: Select all

ObjectA.position += normal

then object A is being pushed back the amount that it has collided. This is useful for an object A hitting an immovable object B (a wall, a pong paddle, a floor tile), and the object A being pushed backwards.

If you were to add the negative normal to object B (the normal is from the perspective of ObjectA):

Code: Select all

ObjectB.position -= normal

then Object B would be pushed away from object A. This is useful for something like object A (a player) pushing object B (a crate) around a level.

[Falco Girgis]

By the way, I also wanted to add something for future generations who look at this topic.

The first algorithm that you posted which only checked whether or not a collision had happened (and provided no other information) could actually still do what you would like.

While the method that I'm about to mention is definitely less efficient in the long-run, it can be very easily implemented. The very first build of Elysian Shadows was doing this kind of collision check for any and all entities (players, physical items, NPCs) against terrain (tiles/objects) on the Dreamcast without any real performance loss.

When an entity changes position, it is moving by a velocity. Rather than just adding this velocity to the position then checking for a collision, you could iterate through each unit of velocity, moving the object one pixel and checking to see if a collision occurred. If the collision DOES occur, you will know the axis based on whether you applied an x or y change in position before the collision was detected. You can then simply break out of the loop, which causes the entity to stop moving forward (to penetrate the other object).

[Milch]

@GyroVorbis
How do you handle the collision today in Elysian Shadows?
What I've seen from your video is that youre using the separating axes theorem for the actual collision - but do you still loop through each element with each element?

[Falco Girgis]

@GyroVorbis
How do you handle the collision today in Elysian Shadows?
What I've seen from your video is that youre using the separating axes theorem for the actual collision - but do you still loop through each element with each element?

OBB collision with the Separating Axis Theorem is considered "fine collision"--it's pixel perfect, and is kind of expensive.

Most games with a decent amount of potentially colliding things have another collision phase called coarse collision to avoid having to check each object against each object, which is O(n^2) time complexity (aka shitty). Popular broad-phase collision algorithms are quad/oct trees, sweep and prune, binary space partitioning, and a whole bunch of others. The downside is that they are usually very complicated algorithms whose goal is to reduce the time complexity of O(n^2) to something more like O(nlog(n)) or better.

For the time being, ES is just comparing each object against each object O(n^2), because we aren't at a stage where we are ready to implement a broad-phase collision detection algorithm. They all have their own strengths and weaknesses, so it really depends on the application.

We undoubtedly will have to in the future (since we're running on a Dreamcast and PSP), but for the time being the computational strain ES puts on the two without broad phase collision detection is still fine.

[Master Jake]

Thanks a lot Falco!!!

This code will help me learn a lot about collision detection. I will also be studying more on Separating Axis Theorem since I had never even heard of it until reading your post. I have a long ways to go, but I'll get there =)

[Milch]

@Jake
Separating Axis Theorem is imo pretty complicated - and is kind of expensive - as Falco mentioned before.
So a better approach would be to combine different ways of collision detection.

For example:
It would be useless to check collision between Object A and Object B if Object A is at one corner of the map, and Object B at the other corner.
So at first you could check with a faster method - like the method you've posted at your first post in this topic.
If this returns true - then you check with a more accurate method ( Separating Axis Theorem ) and so on.

[Falco Girgis]

@Jake
Separating Axis Theorem is imo pretty complicated - and is kind of expensive - as Falco mentioned before.
So a better approach would be to combine different ways of collision detection.

For example:
It would be useless to check collision between Object A and Object B if Object A is at one corner of the map, and Object B at the other corner.
So at first you could check with a faster method - like the method you've posted at your first post in this topic.
If this returns true - then you check with a more accurate method ( Separating Axis Theorem ) and so on.

Eh, to be honest, I don't know about this so much.

If you have two bodies that definitely won't be colliding, they shouldn't be checked together--period. That's the entire point of broad-phase algorithms.

Even if you were to check AABB first then OBB, you're still iterating through every object with a time complexity growth rate of O(n^2). The difference between AABB and OBB collision detection (when written well) is really small in 2D. So small that having to do AABB and OBB every time something could be colliding might actually be slower (or not faster enough to matter). A good implementation of the separating axis theorem should immediately quit the collision check when an axis that isn't overlapping is found. Even worst case you have 4 axis normalizations (square root) and and 4 dot products--not really that big of a deal (usually far less).

Better than checking with AABB would be the simple circle check, which would use the "radius" of the two objects (largest half-widths) to judge whether or not they could potentially be colliding. But the best yet alternative would be to implement a broad-phase collision algorithm to not check every object against every other.

[Milch]

The problem with briad-phase algorithms is, that I have no idea how to implement it.

For example, say I'm using the quad tree method.
I do know how to reduce the field beeing checked until each quad has a given size. ( btw. excellent articel on gamedev.net about quadtrees )
http://www.gamedev.net/reference/progra ... /page2.asp
But what do after that?
Do I still have to check my last ( or all visible ) quad with each game object via AABB?
Because thats the only way I know how to do it - but thats still pretty expensive if my game contains a lot of game objects.

[RyanPridgeon]

But surely if your boxes aren't oriented, SAT can be simplified to hell because you're always gonna have 4 possible overlaps, using the x,y and w,h of the objects?

Something like

find x overlap (x1+w1 - x2)
if this overlap is smallest
then x1 = x2 - w1

But for all 4 overlaps.

Just a suggestion.

[Falco Girgis]

But surely if your boxes aren't oriented, SAT can be simplified to hell because you're always gonna have 4 possible overlaps, using the x,y and w,h of the objects?

Something like

find x overlap (x1+w1 - x2)
if this overlap is smallest
then x1 = x2 - w1

But for all 4 overlaps.

Just a suggestion.

That's exactly what my AABB collision function is doing. It's the same concept of the SAT minus the math for oriented bounding boxes. So yeah, you could easily do:

Code: Select all

if(axisAligned) AABBCollision(body1, body2);
else OBBCollision(body1, body2);

[RyanPridgeon]

My bad, for some reason I thought that only the OBB method was posted.