# Collision detection problems using AABB's

I implemented a simple collision detection routine using AABB's between my main game sprite and various platforms (Please see code below). It works great, but I'm now introducing gravity to make my character fall and it's shown up some problems with my CD routine.

I think the crux of the matter is that my CD routine moves the sprite back along the axis in which it has penetrated the least amount into the other sprite. So, if it's more in the Y axis than the X, then it will move it back along the X Axis.

However, now my (hero) sprite is now falling at a rate of 30 pixels per frame (It's a 1504 high screen - I need it to fall this fast as I want to try to simulate 'normal' gravity, any slower just look weird) I'm getting these issues. I will try to show what is happening (and what I think is causing it - although I'm not sure) with a few pictures: (Code below pictures).

I would appreciate some suggestions on how to get around this issue.

For clarification, in the above right picture, when I say the position is corrected 'incorrectly' that's maybe a bit misleading. The code itself is working correctly for how it is written, or put another way, the algorithm itself if behaving how I would expect it to, but I need to change it's behaviour to stop this problem happening, hope that clarifies my comments in the picture.

My Code

``````public boolean heroWithPlatforms(){

//Set Hero center for this frame

//Iterate through all platforms to check for collisions
for(x=0;x<platformCoords.length;x+=2){

//Set platform Center for this iteration

// the Dif variables are the difference (absolute value)
// of the center of the two sprites being compared (one for X axis difference
//and on for the Y axis difference)
difX = Math.abs(heroCenterX-platformCenterX);
difY = Math.abs(heroCenterY-platformCenterY);

//If 1
//Check the difference between the 2 centers and compare it to the vector (the sum of
//the two sprite's widths/2.  If it is smaller, then the sprites are pverlapping along
//the X axis and we can now proceed to check the Y axis
if (difX<vecXPlatform){

//If 2
//Same as above but for the Y axis, if this is also true, then we have a collision
if(difY<vecYPlatform){
//we now know sprites are colliding, so we now need to know exactly by how much
//penX will hold the value equal to the amount one sprite (hero, in this case)
//has overlapped with the other sprite (the platform)
penX = vecXPlatform-difX;
penY = vecYPlatform-difY;
//One sprite has penetrated into the other, mostly in the Y axis, so move sprite
//back on the X Axis
if (penX < penY){hero.xScreen-=penX*(heroCenterX-platformCenterX>=0 ? -1 : 1);}
//Sprite has penetrated into the other, mostly in the X asis, so move sprite
//back on the Y Axis
else if (penY < penX) {hero.yScreen-=penY*(heroCenterY-platformCenterY>=0 ? -1 : 1);}
return true;
}//Close 'If' 2
} //Close 'If' 1
}
//Otherwise, no collision

return false;
}
``````
-
To elaborate, why is it you move sprites back on the other axis: `//One sprite has penetrated into the other, mostly in the Y axis, so move sprite //back on the X Axis` – Blue May 13 '13 at 8:23
Hi @Blue, because the sprite should be corrected along the least penetrating axis, so if the sprite has penetrated the platform more in the X Axis than the Y, it is the Y the should be corrected as it is the lesser of the two. – BungleBonce May 13 '13 at 11:26
possible duplicate of Collision Detection, player correction – Anko May 13 '13 at 22:01
I've read that question before @Anko - it does not give me the answers I need. Hence I composed my own question (Not convinced the asker is asking the exact same thing, although it's hard to be sure) :-) – BungleBonce May 13 '13 at 22:53

during my experiments with HTML5 canvas and AABB I found exactly what you are experiencing. This did happen when I attempted to make a platform from adjacent boxes of 32x32 pixels.

Solutions I attempted by order of my personal preference

1 - Divide movements by axis

My current one, and I think I will continue my game with it. But be sure to check what I call Phantom AABB if you need a quick solution without having to modify a lot your current design.

My game world has very simple physics. There is no concept of forces (yet), only displacement. Gravity is a constant displacement to down. No acceleration (yet).

Displacement are applied by axis. And in this consist this first solution.

Each game frame:

``````player.moves.y += gravity;
player.moves.x += move_x;
``````

move_x is set according to input processing, if not arrow key pressed then move_x = 0. Vales below zero mean left, otherwise to the right.

Process all other moving sprites and decide the values of their "moves" component, they have the "moves" component too.

Note: after collision detection and response, the move component must be set to zero, both x and y properties, because the next tick the gravity will be added again. If you not reset, you will end with a moves.y of two times the desired gravity, and in the next tick it will be three times.

Then enter the displacement applying and collision detection code.

The moves component is not really the current position of the sprite. The sprite has not moved yet even if moves.x or y changed. The "moves" component is a way to save displacement to be applied to sprite position in the correct part of the game loop.

Process first the y axis (moves.y). Apply moves.y to sprite.position.y. Then apply AABB method to see if the moving sprite being processed is overlapping a platform AABB (you already understood how to do this). If it overlaps then move the sprite back in the y axis by applying penetration.y. Yes, as opposed to my other answer, now this move evolved method ignores the penetration.x, for this step of the process. And we use the penetration.y even if it is greater than penetration.x, we aren't even checking for it.

Then process the x axis (moves.x). Apply moves.x to sprite.position.x. And do the opposite than before. You will move the sprite only in the horizontal axis this time by applying penetration.x. As before, you don't care if penetration.x is less or greater than penetration.y.

The concept here, is that if the sprite is not moving, and was initially not colliding, then it will remain like that in the next frame (sprite.moves.x and y are zero). The special case where another game object magically teleports to a position that overlaps the sprite begin processed is something I will handle later.

When a sprite begin to move. If it moving only in the x axis, then we are only interested if it penetrates something by the left or the right. As the sprite is not moving down, and we know this because the y property of the moves component is zero, we don't even check the calculated value for the penetration.y, we only see at penetration.x. If penetration exist in the axis of movement, we apply correction, otherwise we simply let the sprite move.

What about diagonal displacement, not necessarily in a 45 degrees angle?

The proposed system can handle it. You only need to process each axis separately. During your simulation. Different forces are applied to the sprite. Even if your engine does not understand forces yet. These forces translates to an arbitrary displacement in the 2D plane, this displacement is a 2D vector in any direction and of any length. From this vector you can extract the y axis and the x axis.

What to do if the displacement vector is too large?

You don't want this:

``````|
|
|
|
|
|
|
|_ _ _ _ _ _ _ _ _
``````

As our new moves applying logic process an axis first and then the other, a large displacement may end being saw by the collision code like a big L, this won't correctly detect collisions with objects that are intersecting your displacement vector.

The solution is to divide large displacements in small steps, ideally your sprite width or height, or half your sprite width or height. To obtain something like this:

``````|_
|_
|_
|_
|_
|_
|_
|_
``````

If you represent teleporting as a large displacement, using the same moves component as a normal move, then no problem. If you don't, then you have to think a way to mark the teleporting sprite to be processed by the collision code (adding to a list dedicated to this purpose?), during response code you can directly displace the standing sprite that was in the way when the teleportation occurred.

2 - Phantom AABB

Have a secondary AABB for each sprite affected by gravity that starts at the sprite bottom, has the same width of the sprite AABB, and 1 pixel height.

The idea here is that this phantom AABB is always colliding with the platform below the sprite. Only when this phantom AABB is not overlapping anything gravity is allowed to be applied to the sprite.

You don't need to calculate penetration vector for the phantom AABB and the platform. You only interested in a simple collision test, if it overlaps a platform, gravity cannot be applied. Your sprite can have a boolean property that tells if it is over a platform or in the air. You are in the air when your phantom AABB is not colliding with a platform below the player.

This:

``````player.position.y += gravity;
``````

Becomes something like this:

``````if (player.onGround == false) player.position.y += gravity;
``````

Very simple and reliably.

You leave your AABB implementation as is.

The phantom AABB may have a dedicated loop that process them, that only check for simple collisions, and do not waste time calculating the penetration vector. This loop must be before the normal collision and response code. You may apply gravity during this loop, for those sprites on the air apply gravity. If the phantom AABB is in itself a class or structure, it may have a reference to the sprite it belongs to.

This is very similar to the other proposed solution where you check if your player is jumping. I giving a possible way of detect if the player has its feet over a platform.

-
I like the Phantom AABB solution here. I've already applied something similar to get around issue. (But not using a phantom AABB) - I'm interested in learning more about your intial method above, but I'm a little confused by it. Is the Moves.x (and .y) component basically the amount that the sprite will be moved by (if it is allowed to move)? Also, I'm unclear how it would help with my situation directly. Would be grateful if you could edit your answer to show a graphic how it could help with my situation (as in my graphic above) - thanks! – BungleBonce May 15 '13 at 18:07
About the moves component. It represent future displacement, yes, but you do not check if you allow movement or not, you actually apply the movement, by axis, first y, then x, and then see if you collided with something, if you do you use the penetration vector to move back. Why save displacement for later processing differs from actually apply the displacement when there are user input to process or something happened in game world? I will try to put this in images when I edit my answer. Meanwhile lets see if somebody else comes with an alternative. – Hatoru Hansou May 16 '13 at 5:46
Ah OK - I think I understand what you're saying now. So, instead of moving x & y and then checking collision, with your method, you move X first, then check collision, if it collides then correct along the X axis. Then move Y and check collision, if there is a collision, then move along the X-Axis? This way we always know the correct axis of impact? Have I got this right?! Thanks! – BungleBonce May 16 '13 at 12:50
Warning: you wrote "Then move Y and check collision, if there is a collision, then move along X-Axis?" Its Y-Axis. Probably a typo. Yes, that my current approach. For very large displacements, more than your sprite width or height, you need to divide in smaller steps, and that is what I mean with the L analogy. Beware of not applying a large displacement in y axis and then a large x, you need to divide both in small steps and intercalate to get correct behavior. Something to care only if large displacements are allowed in your game. In mine, I know they will occur. So I prepared for it. – Hatoru Hansou May 17 '13 at 4:21
Brilliant @HatoruHansou, I never thought of doing things this way, I will certainly give it a try - thanks very much for your help, I will mark your answer as accepted. :-) – BungleBonce May 17 '13 at 23:08

I would combine the platform tiles into a single platform entity.

For example, say you take the 3 tiles from the pictures and combine them into a single entity, your entity would have a collision box of:

``````Left   = box1.left
Right  = box3.right
Top    = box1.top
Bottom = box1.bottom
``````

Using that for collision will give you the y as the least penetrating axis throughout most of the platform while still allowing you to have specific tiles within the platform.

-
Hi @UnderscoreZero - thanks, this is one way to go, the only thing is I'm currently storing my tiles in 3 separate arrays, one for left edge tiles, on for middle tiles and one for right edge tiles - I guess I could combine them all into one array for the purpose of CD, just not sure how I could write code to do that. – BungleBonce May 13 '13 at 22:41
Another option you could try that a lot of physics engines use is once the object has landed on a flat plane, they disable gravity for the object to prevent it from trying to fall through. Once the object receives sufficient force to pull it away from the plane or it falls off the side of the plane, they re-enable gravity and perform physics as per normal. – UnderscoreZero May 15 '13 at 15:52

Problems like these are common with new collision detection methods.

I don't know too much about your current collision setup, but here is how it should go:

First off, make these variables:

1. Make a X and Y velocity
2. Make a Gravity
3. Make a jumpSpeed
4. Make a isJumping

Second off, make a timer to calculate the delta to affect the velocity of the object.

Third off, do this:

1. Check if the player is pressing the jumping button and isn't jumping, if so add jumpSpeed to the Y velocity.
2. Subtract gravity from the Y velocity each update to simulate gravity
3. If the player y + height is smaller then or equal to the y of the platform, set the Y velocity to 0 and put the player's Y to the platform's y + the player's height.

If you do this, there shouldn't be any problem. Hope this helps!

-
Hi @user1870398, thanks, but my game doesn't even have jumping at the moment, the question related to the problems that arise through use of the 'least penetrating axis' method of correcting the sprite's position. The problem is that gravity is pulling my character further into my platforms along the Y Axis than it is overlapping on the X Axis, thus my routine (as is correct for this type of algorithm) is correcting the X axis, thus I can't move along the platform (as the CD routine sees the individual tiles and treats them as such even though they are presented as one platform). – BungleBonce May 13 '13 at 11:35
I get your problem. It's just that you aren't properly correcting your movement. You need an isJumping variable. If you hit the jump button and are not jumping you set it to true, if you hit the ground set it to false, move the player's Y to the correct position (platform.y + player.height), and set isJumping to false. Next, right after checking for those things, do if (left_key) player.velocity.x -= (player.isJumping ? player.speed : player.speed - player.groundFriction). I know you haven't implemented jumping yet so simply always have isJumping set to false. – LiquidFeline May 15 '13 at 0:12
I don't have jumping but if an 'ifJumping' variable is always set to false, how is this any different to not having one? (say in games where there is no jumping) I'm just a little confused as to how an 'isjumping' boolean could help in my situation - would be grateful if you could explain a bit more -thanks! – BungleBonce May 15 '13 at 18:12
It isn't needed. Just better to implement it while you'r still programming it. Anyway, the reason for isJumping is to organize your code, and prevents problems by only adding gravity while the player is jumping. Just do what I recommended. This method is what most people use. Even Minecraft uses it! This is just how gravity is effectively simulated! :) – LiquidFeline May 16 '13 at 6:51