# Collision detection logic

Edit 2

In the following picture sprite1 (the red square) is hitting the platform from the left, so:

`````` sprite1_rightEdge>platformSprite leftEdge
``````

would be true, so I can simply reposition sprite1 to align it with the left edge of the platform. So....

``````sprite1X=platformSpriteX-platformSpriteWidth
``````

This is fine, however, lets say that sprite1 hits from the right, the problem I have here is that the first condition (above) is still true. So....

``````sprite1_rightEdge>platformSprite leftEdge
``````

So my sprite1 still gets positioned at the left edge of the platform......

The same also happens in reverse....

Using velocity

I've had some success with velocity, but again I'm not clear on how this works properly.

For example, if I say something like:

``````if (Sprite1 moving right at time of collision)
``````

Then I can assume it's hit the platform from the left. This works, but what if the sprite is 'falling' from the top and lands on the platform while also moving right? It will again get re-positioned at the left edge of the platform.

partial sucess

So far, I managed to get this working (although not fully implemented yet), by saving the old position of Sprite1, repositioning it and checking the old position, so if the old position was to the left of the platform, then I can assume it came in from the left.

Sorry for the length of this question but I just wanted to show what I had tried thus far. So if someone could let me know the best way to proceed it would be much appreciated.

Just to clarify what I'm asking - I have 2 objects - 1 is a platform and the other is the main character, I wish to make the player stop regardless of which side he hits the platform (from the top, bottom, left or right) - I will definitely be moving at distances of more than 1 px at a time).

I've attempted using velocity but this doesn't seem to work correctly as well as double checking x/y positions once a collision has happened but again I get some very off results. Some pseudo code of how to detect which side a sprite has hit would be much appreciated :-)

I have researched this and have seen pretty much every Q&A on this site regarding this subject (as far as I know) but the answers are either not relevant to my particular query or I simply don't understand them.

Original question

I understand the basic principles of collision detection for squares / rectangles

i.e.,

(Psuedo code)

``````public boolean testCollision(){

if (bottom of sprite1<top of sprite2)
return false;

if(top of sprite1>bottom of sprite2)
return false;

if(left edge of sprite1 > right edge of sprite2)
return false;

if(right edge of sprite1 < left edge of sprite2)
return false;

return true;
}
``````

I also know that I can stop my sprite going off the edge of the screen like so:

``````if(spriteX<0){spriteX=0};
``````

However using something akin to the first method above for detecting collision between 2 specific objects, how can I make my 1st sprite actually stop so he can't pass through it?

At the moment, although I can detect when the two are touching, I'm unsure how to make it so that they can't actually pass through each other.

A push in the right direction would be a great help - thanks!

-
This is a very interesting question. In fact, I would like to add one more point which you need to think about or ask in addition: collision in reality is not that simple as you describe and as I see it answered. e.g. imagine shape A moving with 10px/frame speed. shape B moving with 10px/frame speed. When animating, you first move one of them (A) - no collision, then another (B) and detect collision. However, A has already moved by 10 px. Instead, collision should have happened in between, so you should somehow deal with A's rollback as well. How do you handle that? – Tengiz Apr 24 '13 at 19:56
Indeed, this is a good point and something I was thinking about after posting my initial question - that of fast moving objects, another way to think about it would be say you have a platform which is 20 pixels high and an object falling at 30 pixels per frame, in one frame it will be above the platform and in another, below it, but never actually in contact with it, so contact will have to be 'predicted' or worked out retrospectively by taking the moving object's trajectory and velocity taken into account. How this would be achieved I have no idea though, ideas and explanations welcome.... – BungleBonce Apr 25 '13 at 0:30

Demonstration:

Crude but functional collision detection and response

The idea is that the player controlled sprite (actually a 32x32 pixels red box) can raise the speed of its next move, but it cannot go back to original speed except if it collide with something. Also if speed is enough the green wall can be "damaged" until it finally is destroyed. Gravity can be disabled. This situation shows AABB in action.

In the video, the red text shows some game variables, penx y peny are the lengths of penetration vectors into each axis (of the player sprite into other objects).

T.x and T.y are the coordinates of the 2d vector that go from the center of a box to the one again it is tested. If you go for AABB as I recommend, you will need T.

The formula used for T is:

``````T = PlatformAABB.position - PlayerAABB.position
``````

Vector from Platform to Player.

If you do not want to use an structure/class to represent vectors, then another option is to use separate variables for x and y elements:

``````Tx = platform.x - player.x
Ty = platform.y - player.y
``````

Note that the position of each AABB is measured from its center, not from top, left corner. So if you are positioning your sprites like me, using left and top to mean the upper left corner of the rectangle containing the sprite, then you may need to calculate the AABB center like this: PlayerAABB.position.x = player.left + player.width / 2. And the same for y but replacing left for top and width for height.

``````Tx = (platform.left + platform.width / 2) - (player.left + player.width / 2)
Ty = (platform.top + platform.height / 2) - (player.top + player.height / 2)
``````

If your x and y coordinates are taken from the center of each sprite then don't worry simply apply the first formula.

To detect if boxes overlap

``````if (absolute(T.x) > (currentSpr.width / 2) + (otherSpr.width / 2)) stop here;
if (absolute(T.y) > (currentSpr.height / 2) + (otherSpr.height / 2)) stop here;
``````

Is enough to know that T is greater in one axis than the sum of the length of the two relevant half extents of each involved box to know that there is no overlapping. Then you can stop and assume no collision.

Logic to detect collision finalizes here for most games. If your objects are moving really fast, more than its width or height in a single game tick, then you will need a more complex method, like divide the movement in small steps (less than the box dimensions) and then do the collision check. Remember the previous position is useful for this.

What to do when colliding?

For the case of Player Sprite vs Platform. Assuming Platforms never move, whatever impacts them.

If collision is positive, then you will have to find penetration vector to move the player sprite back. We are using AABB to make that task simple. You want the sprite to remain in touch with the platform, not to go back to its previous position, that may be far away.

We already calculated T, and used it to find overlapping, now we will use it again:

Formula for penetration vectors lengths. (We don't know direction yet).

``````penx = (currentSpr.width / 2) + (otherSpr.width / 2) - absolute(T.x);
peny = (currentSpr.height / 2) + (otherSpr.height / 2) - absolute(T.y);
``````

Now, we choose the lesser of them to displace the sprite back. If you want to understand why the lesser, do the opposite, run your program and have some fun watching the result.

And we need a direction too, we know that we are always axis aligned but we still have 2 choices, left or right, up or down.

``````if (peny <= penx)
{
if (T[1] < 0) spr1.top += peny;
else
if (T[1] > 0) spr1.top -= peny;
} else
{
if (T[0] < 0) spr1.left += penx;
else
if (T[0] > 0) spr1.left -= penx;
}
``````

(formula edited to make it more readable)

I have to do some extra calculations because of the left, top, system. I hope this does not make it to look more complicated than it really is.

What to do when colliding to another thing than a platform?

Be creative. You can divide the penetration vector by 2 and displace both sprites but in opposite directions. Or simply destroy the player. Or think in something more complex. Articles for "friction" in games exists.

Notes:

To return absolute values in C++ use fabs() function. In javascript use Math.abs(). Other languages have their owns.

I think that you don't need a vector library for this, as only basic operations were used.

Depending how you iterate through objects in your scene, the player sprite will not always be at the left (currentSpr in the examples) and the platforms may not always be at the right (otherSpr) in the calculations, beware of not applying the penetration vector to a platform by mistake.

Save the previous position of the sprite before move to the next position is what I'm doing for my game and I see no shame on that. I like the solution.

Now that you have previous position and current position, the vector giving you the direction of movement when colliding with other non movable objects (platforms, walls) has its tail in current position, and its head in previous position.

The question that remains to be answered is how much the colliding object should retreat. You don't want it to move back to previous position in all cases, specially when the speed of a given movement is too high. You probably want the object to remain in contact to the platform without trespassing its borders.

The SAT (Separating Axis Theorem) is what I would use in this case:

1 - Find penetration vector using SAT

2 - Move the penetrating sprite back by apply the penetration vector

For this specific problem read sections, 0, 1 and 2.

Separating Axis Theorem for AABBs is what you need for this specific case.

Note the case where two character sprites collide is another story. You can use SAT too for detect penetration vector, but you probably want some kind of physics acting in both sprites, and alter the position of both. Depending on the game, maybe destroy the player sprite is enough, in this case no penetration vector needed.

-
Thanks @Hatoru, I'm not having any luck so far with this. This is pretty math heavy! So I guess you're telling me I need to find the direction the sprite hit (using the vector) and move it back by the amount it has penetrated into the static shape? – BungleBonce Apr 25 '13 at 12:53
@user22241 Move back in direction of sprite movement is exactly what I though first and is an option. But now that I think again about it, we are using Axis Aligned to save us from doing more complex calculations. So it may be better to move in the direction of one axis. In the flash animation from metanet it is the violet arrow. The violet arrow is always aligned to x or y axis and they choose always the shorter one to apply to sprite position, not both. AABB is ideal for 2D scrolling games. – Hatoru Hansou Apr 25 '13 at 22:04
Thanks @HatoruHansou, this is an incredibly detailed answer! I'm going to go attempt it, I've already got collision detected using the method you describe and I now just need to try to work out the direction etc... I will give it a go and check back - thanks again – BungleBonce Apr 27 '13 at 16:46
Awesome - I implemented all of this and it works perfectly - thank so much for this and for explaining it so well - If I come across related problems (like bullet through paper etc) I will ask another more specific question - thanks again! – BungleBonce Apr 28 '13 at 0:19
I'm glad I was of help. Note that the last formula (used to decide direction of penetration vector) had a minor bug. In the original I divided penetration by 2 because I was processing some sprites twice. I noticed it after posting. I've corrected it in the answer. – Hatoru Hansou Apr 29 '13 at 2:08

Here's a different algorithm; instead of stepping the player forward and moving him back if he's colliding, check where the next collision will occur:

1. Get the position of a corner of the object.
2. Shoot a line down (or up, or to the right/left, depending on your movement direction) from that position.
3. Figure out the first place that line intersects a platform.
4. Get the distance from that place to the corner.
5. Repeat for the other corner of the object you need to check.
6. Move the player down the minimum of his current movespeed and both of those distances.

So, if the player's moving in an X direction, such as right, you need to take the top right and bottom right corners (left; top left and bottom left corners, respectively). For a Y direction, such as down, you take the bottom left and bottom right corners (and similarly for the up direction).

Basic code for detecting collisions below the character:

``````float botLeftDist = GetDistToNearestPlatform(botLeftCorner);
float botRightDist = GetDistToNearestPlatform(botRightCorner);
float minDist = min(botLeftDist,botRightDist);
sprite.move(min(moveSpeed.x, minDist), 0.0);
``````

Do this for all four directions, every frame. For example, checking for a collision on the right side of the player object would be the same, except replace `botLeft` with `topRight`.

There's three basic cases:

1. If you're high in the air, it'll just move the character down depending on his movespeed, because moveSpeed < nearest platform position.
2. If you're about to hit the platform, it'll move the character down to the platform, and won't leave him in the air.
3. If you're touching the platform, it won't move the character at all, since the platform is 0 distance away.

Putting it all together, you get something like this:

``````float nearestY, nearestX;
if(movingUp)
float nearestY = GetNearestUp();
else
float nearestY = GetNearestDown();

if(movingLeft)
float nearestX = GetNearestLeft();
else(movingRight)
float nearestX = GetNearestRight();

sprite.move(min(moveSpeed.x, nearestX), min(moveSpeed.y, nearestY));
``````

where `GetNearestDown()` contains the first three lines of the first three lines of the code above (the first portion in this post), and returns `minDist`. The other three functions are defined similarly.

EDIT: As for implementing `GetDistToNearestPlatform`, it depends on how you implement your scene. It could be as expensive as starting at the position you want, moving pixel-by-pixel and checking each platform to see if they contain that pixel. I implemented this algorithm in a tile-based system, so I moved down tile-by-tile until I found an occupied tile, then checked pixels within that tile until I found an occupied one.

-

If the player is touching the platform and the velocity is pushing it down, then move it back to it's last posistion.

Save the old position:

``````Position oldPosition = player.position;
``````

Now do all your input checks here.

Then check for collision:

``````if (player.checkCollision(platform) == false && player.velocity < 0)
{
player.velocity = 0;
player.position = oldPosition;
}
``````

Of course, replace the type Position in the example about with an object that stores the players and/or platforms location. Also when I mention velocity, I mean vertical velocity. And not to mention that when I put player.velocity < 0 generally that means the player is being pulled down. Good luck!

-
Hey @user1870398 - thanks for this, I'm still having a lot of trouble understanding it though, I've updated my question with an image to show the trouble I'm having - thanks! – BungleBonce Apr 24 '13 at 14:19

So instead of checking their current position for collision. You can check where they will be.

IE: (very pseudo code)

``````newPos = currentPos + movement;
if(checkCollision(newPos,otherSpritePos) == FALSE) { currentPos = newPos; }
else { /*oh noes collision!*/ }
``````

As for determining which side the object is colliding with:

``````difference = objectBCenter - objectACenter;
if(|difference.x| > |difference.y| && difference.x > 0) {left side}
if(|difference.x| > |difference.y| && difference.x < 0) {right side}
if(|difference.x| < |difference.y| && difference.y > 0) {top side}
if(|difference.x| < |difference.y| && difference.y < 0) {bottom side}
``````

note this is all designed around boxes with relatively small movement steps. the || around the variables indicates absolute value.

-
That's a great tip @UnderscoreZero, Thanks! I'm using prediction already, but I wasn't sure how to 'reset' the position of the sprite, so you're saying to 'save' the position and then to reset it if the new position is within the boundaries of the other sprite? This is really good, however how would you deal with fast moving sprites? Lets say my sprite is accelerating and moving at 10 px every frame. If it's next 10 pixel movement takes it 1 pixel inside the other sprite, then it will in effect move it back to 9 pixels away from that sprite. Any idea how I would deal with that? Thanks!! – BungleBonce Apr 23 '13 at 22:48
You could determine which edge it collided with, and return that from your collision detection function and use that to determine the position to move it back from. IE: collision detection function returns 0 for no collision, 1 for top 2 for right 3 for bottom 4 for left. and then if it hit the top, you can do currentPos.y = otherSpritePos.y - currentSprite.height. I am sure there are better ways to do that though. – UnderscoreZero Apr 23 '13 at 23:08
Thanks for this @UnderscoreZero, I've been trying to implement this, but I'm having a lot of difficulty understanding how to determine from which side the sprite has hit - could you give any clues as to how this could be achieved? Thanks again. – BungleBonce Apr 24 '13 at 0:57
If you want that sprite to be a sphere, you're going to have to do a different style of collision detection than box/box collision as has been described. I haven't done that style of collision yet. I'll update my answer for determining the side. – UnderscoreZero Apr 24 '13 at 15:27
Sorry, this was my mistake my sprites are actually rectangles, I've corrected this in the picture.... – BungleBonce Apr 24 '13 at 17:03

Building up on the discussion from @UnderscoreZero's answer... You can have something like this:

``````public float testCollision(){

if (bottom of sprite1<top of sprite2)
return <top of sprite2>;

if(top of sprite1>bottom of sprite2)
return <bottom of sprite2>;

if(left edge of sprite1 > right edge of sprite2)
return  <right edge of sprite2>;

if(right edge of sprite1 < left edge of sprite2)
return <left edge of sprite2>;

return 0; // or some value that cannot be attained by any return value and make sure you replace that value in the if condition below
}

newPos = currentPos + movement;
checkCollision = testCollision();
if(checkCollision != 0) { currentPos = checkCollision }
else { currentPos = newPos }
``````

EDIT

This is fine, however, lets say that sprite1 hits from the right, the problem I have here is that the first condition (above) is still true. So....

sprite1_rightEdge>platformSprite leftEdge

So my sprite1 still gets positioned at the left edge of the platform......

The same also happens in reverse....

This is simple: Modify the collision check as follows:

``````if (top of sprite1<top of sprite2 && bottom of sprite1 > top of Sprite2)
return <top of sprite2>;

else if(top of sprite1<bottom of sprite2 && bottom of sprite1 > bottom of Sprite2)
return <bottom of sprite2>;

if(left edge of sprite1 < right edge of sprite2 && right edge of sprite1 > right edge of sprite2)
return  <right edge of sprite2>;

else if(left edge of sprite1 < left edge of sprite2 && right edge of sprite1 > left edge of sprite2)
return <left edge of sprite2>;
``````

A word of caution here... These conditions only checks for collision in one dimension, if you are going to have collision detection in two dimensions, like your image you may want to break the tie b/w position based on the direction of motion or any other parameter you define and have to modify the return values and conditions appropriately.

-
Hey @Ani - thanks for this, I'm still having a lot of trouble understanding it though, I've updated my question with an image to show the trouble I'm having - thanks! – BungleBonce Apr 24 '13 at 14:18
updated the answer! – Ani Apr 24 '13 at 18:56