Collision detection logic

Question

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.

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

(Pseudo 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!

Answer 1

Demonstration:

Crude but functional collision detection and response

Video: https://vimeo.com/64923588

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.

Original answer:

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

Please, see this: http://www.metanetsoftware.com/technique/tutorialA.html

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.

Answer 2

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.

Answer 3

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!

Answer 4

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.

Answer 5

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.