android - 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
    heroCenterX  = hero.xScreen+(hero.quadWidth/2);
    heroCenterY  = hero.yScreen+(hero.quadHeight/2);


    //Iterate through all platforms to check for collisions
    for(x=0;x
    //Set platform Center for this iteration
    platformCenterX = platformCoords[x]+(platforms.quadWidth/2);
    platformCenterY = platformCoords[x+1]+(platforms.quadHeight/2);

    // 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

    //If 2
    //Same as above but for the Y axis, if this is also true, then we have a collision
    if(difY        //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;
    }

Answer

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:

|_
  |_
    |_

      |_
        |_
          |_
            |_
              |_

What about teleporting sprites?

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.