C++ and SFML: Tile-based Collision Detection and Response

Reading the book “SFML Game Development By Example” i finally reached Chapter 7, which covers the topic Collision Detection and Resolution.

When I applied the described concepts from the book to my own platformer-game i headed into some surprising problems which forced me to dive deeper into Collision Resolution regarding AABB Bounding-Boxes.

When resolving a collision, you always have to figure out from which direction the object (here it’s the player-object) comes and in which direction the occurring collision has to be resolved.

Collision Resolution with Square Objects

The mentioned book uses the distance between the center of the object and the tile to determine the side of the collision, which is crucial for resolving the collision.

When the distance between the center of the player and the center of the tile on the X-Axis is longer than the distance on the Y-Axis, the object is either on the left or right side of the tile, but not above or below the tile. From here it is easy to figure out how to resolve the collision: if the X-Coordinate of the players center is smaller than the X-Coordinate of the tile-center, thus on the left side, move the player back to the left side to resolve the collision, otherwise move him to the right side of the tile.

Obviously, all of this applies to the resolution on the Y-Axis:

When the distance between the center of the player and tile on the Y-Axis is longer than on the X-Axis, it usually indicates, that the Player is above or below the tile, but not left or right of it. From here you can further determine if the player is above or below the tile by comparing their center on the Y-Axis as described before.

The thumb of rule may be: 

abs(diffX) > abs(diffY) = horizontal collision 

abs(diffX) < abs(diffY) = vertical collision

However, this solution has one flaw: It works best with square AABB-Bounding Boxes.

When the AABB Bounding-Box of the object is not square, you may run into trouble. This is illustrated by the following listing:

Here the height of the players Bounding-Box is bigger than its width. In this case the distance between the two center on the Y-Axis (diffY) is longer than the distance on the X-Axis (diffX), even when the Player is standing clearly left or right of the tile.

The bigger diffY-Value in comparison to the diffX-Value tricks the program to falsely assume, that the player is located above or below the tile and resolves it respectively. Instead of being pushed to the left side of the tile, the player gets tackled to the top of it. 

The bigger the difference between width and height of the Bounding-Box, the more extreme the effect occurs.

Collision Resolution with Rectangular Objects

To get rid of the described behaviour you could proceed as follow: 

1. Move the player on the X-Axis
2. Check for collisions
3. Resolve occurring collisions on the X-Axis
4. Move the player on the Y-Axis
5. Check for collisions
6. Resolve occurring collisions on the Y-Axis.

The basic steps 1.-6. could be implemented this way: 

void Player::move(float x, float y) {
    mPosition.x += x;
    updateAABB();
    checkCollisions(); // collect info of all tiles player intersects with
    resolveXCollisions();
    mPosition.y += y;
    updateAABB();
    checkCollisions();
    resolveYCollisions();
}

It is important to separate the movement into 2 separate Axis to resolve occurring collisions.

Therefore, you should not update the movement on the X- and Y-Axis at once.

void Player::move(float x, float y) {
// mPositon is of Type sf::Vector2f
mPosition += sf::Vector2f{x,y}; // WRONG
/*...*/
}

Here is why updating X and Y at once is not a good idea:

When the velocity is applied to both mPosition.x and mPosition.y at the same time (Frame 1), the player may intersect with the tile on both the X-Axis and Y-Axis (Frame 2).

In the shown Player::move(float x, float y)-method the collisions get resolved on the X-Axis first and then on the Y-Axis. This is why collisions will always be resolved on the X-Axis when dealing with concurrent collisions on both the X- and Y-Axis, which may occure when you move on the X- and Y-Axis at once. The player will get pushed to the left or right side of the tile, but not to the top as it is supposed to happen (Frame 3). The attempt to avoid this by resolving the collisions on the Y-Axis first, may work when approaching the tile from above, but it will end up with the basically same wrong resolution on the Y-Axis, when touching the tile from the side.

Because of this behaviour it is important to first move on the X-Axis alone, check for collisions, resolve them, and then move on to the Y-Axis and repeat the procedure. 

Resolving Collisions on each Axis

So you can basically store all needed information about the collision (like the size of the area of intersection between the intersecting objects and the current Bounding-Boxes of all tiles the object collides with), sort them from tiles with bigger intersection to smaller intersection, and resolve the collisions accordingly. 

For the Collision Resolution on the X-Axis such implementation could look like this:

void Player::resolveXCollisions() {
    std::sort(mCollisions.begin(), mCollisions.end(), [](CollisionInfo& lhs, CollisionInfo& rhs)->bool{
       return lhs.mArea > rhs.mArea;
    });
        //collision-objects store the Bounding-Boxes of the tiles the player did collide with
    for(auto& collision : mCollisions){
        //if collision already resolved, move on
        if(!mAABB.intersects(collision.mBounds)) continue;

        sf::Vector2f entityCenter = {(mAABB.left + mAABB.width) / 2.f,
                                     (mAABB.top + mAABB.height) / 2.f};

        sf::Vector2f tileCenter = {(collision.mBounds.left + collision.mBounds.width) / 2.f,
                                   (collision.mBounds.top + collision.mBounds.height) / 2.f};

        //left of tile
        if( entityCenter.x <= tileCenter.x){
            mPosition.x += -(mAABB.left + mAABB.width - collision.mBounds.left);
            updateAABB();
        }
            //right of tile
        if( entityCenter.x >= tileCenter.x){
            mPosition.x += (collision.mBounds.left + collision.mBounds.width) - mAABB.left;
            updateAABB();
        }
    }
    mCollisions.clear();
}

The code for the Y-Axis would look basically the same, taking the vertical resolution into account instead of the horizontal.

First you have to determine the center of the object and tile. We already now, that a collision between the object and tile had occured (otherwise the tile-bounds of the tile would not be stored in the mCollisions-Container). Now we just have to check on which side the object is in regard to the tile and move it back the same amount it intersects with the tile. That is all there is to do. 

This approach does not rely on square AABB Bounding-Boxes for an appropriate behaviour. It also does not matter, how many tiles you collide with, because they get sorted and the tile with the biggest intersection gets handled first.