How can I detect and resolve collision in my 2D tilebased game?

Question

I'm trying to wrap up collision for my 2D super mario bros clone made in c++ with SFML 2.1 . I have tried sooo many different solutions and ideas but I can't get anything to work correctly.
I have a player which currently checks for collision in it's own Update() (shown below)

Currently:
1. My collision detects collision slightly offsetted. If you could find any obvious error I'd be happy to know.
2. I'm unsure if this is a good enough solution since I need to detect collision in 4 directions (Jumping, hitting my head on blocks. Falling down onto blocks, and left/right collision)
3. When I detect collision, I don't know how to correct the player in the right direction.

I have cleaned up all unnecessary code and removed code that doesen't work below.

void Player::Update(Camera& camera, Level& level, sf::RenderWindow& window)
{
    input.Update(*this); // Read input logic
    physics.update(*this, level, camera, window); // Update physics (movement, gravity)
    drawing.update(*this); // Update animation ( does NOT draw player )

    if(Collision(level, camera, getPosition())) // Check for collision
    {
        CollisionResponse(); // If we had collision, do something about it
    }
}

The Collision() function takes three arguments:
- level: is the map - camera: returns which tiles are shown from map, on the screen - getPosition(): simply the position of the player in the window

The function looks like this:

bool Player::Collision(Level& level, const Camera& camera, const sf::Vector2f& position)
{
    // Rectangle surrounding player
    sf::FloatRect playerRectangle = sprite.getGlobalBounds();

    int tileSize = 32;
    Tile* tile;

    // smallBounds is the area on the screen where we check collision.
    // We dont check the whole screen, only tiles that CAN collide with player.
    sf::IntRect smallBounds = sf::IntRect(
        (position.x / tileSize) + camera.GetTileBounds(tileSize).left,
        position.y / tileSize,
        ((position.x + tileSize) / tileSize) + camera.GetTileBounds(tileSize).left,
        (position.y + tileSize) / tileSize);

    // Loop through all tiles
    for (int y = smallBounds.top; y < smallBounds.height; y++)
    {
        for (int x = smallBounds.left; x < smallBounds.width; x++)
        {
            // Get the tile we are drawing
            tile = level.GetTile(x, y);
                if(tile && !tile->GetWalkable())
            {
                sf::FloatRect tileRectangle(tile->GetSprite().getPosition().x,
                                            tile->GetSprite().getPosition().y,
                                            tileSize,
                                            tileSize);
                tileRect = tileRectangle;
                if(Intersect(playerRectangle, tileRectangle))
                {
                                    // Woah, collision detected!
                    return true;
                }
            }
        }
    }
    return false;
}

and the CollisionResponse function:

void Player::CollisionResponse(void)
{

}

Please leave a comment below if I have missed out on any helpful information.

The map is made up of diffrent tiles saved by coordinates not where they are actually located but their location in the array so a sample map would look like this:
0,0 0,1 0,2
1,0 1,1 1,2
2,0 2,1 2,2
The collision function then checks collision in relation to thoose tiles around the player.

What I've tried:
A lot of different collision methods to solve x and y collision at once.
Collision response to move player back to last position.
Collision response to move player back by the size of the intersected rectangle (this worked in y axis, but not in x axis). I'll write more when my head doesen't feel like melted cheese.

Answer 1

Moving the player back to the last known good position will result in the behavior you're experiencing; the player will remain some distance away from what he's about colliding with. To take an example: if your character is moving at 300 pixels/sec and they're 5 pixels away from a wall, the next collision occurs in 1/60th of a second. If your framerate is 60FPS, a collision will be detected in the next frame, and the character will be moved back to the 5 pixels away from the wall he was at before the collision occured. Certainly undesirable.

The method you hit upon should work (moving the player back by the size of the intersected rectangle), as long as you're calculating the amount correctly. The Separating Axis theorem is good for this (in that article, see specifically section 7, "Finding the MTV").

Another method you could try, not involving calculations: on collision, move the player backward in small timesteps (maybe even pixel-by-pixel) until he stops colliding with the wall. Then, you'll know a spot that is much closer to the wall where it's safe to place him. Less efficient, but easier to implement.

Yet another method is continuous collision detection. It's somewhat more complex in nature. You should be able to find some information on it by simply searching around for "continuous collision", but the basic idea is:

1. Figure out when and where the next collision will take place.
2. If the next collision will occur within the current timestep, move the object to the position where the collision takes place.
3. If the next collision doesn't occur within the current timestep, just move the object forward its current movement speed.

Answer 2

For my game (in java with Libgdx) i used AABB collision detection too. There are 2 different ways you can detect and handle collision:

• calculate the new position before you move. If there is an object don't move. To have a gliding movement check for collision in x- direction, if there is a collision, don't move. If there is no collision, check the same for y. If there is a collision, don't move in y. Still no collision check for collision on x and y (your real new position). If there is a collision stop both movements.
• move to the new position. If you collide there, in x direction reset x-movement, if you collide in y-direction reset y-movement, collision in both directions, reset both.

As you are using a TileBased map you don't need to use "intersection" tests.
Instead you can store the 4 corner points of your character, rounded to the Tile he is on (if every Tile is one unit big and the characters foot is on P(0.5;0.5), you need to check the Tile (0;0)).
The position of the Player is his lower, left corner (normally), so his other 3 points are P2(player.position.x.+player.width;player.position.y), P2(player.position.x.+player.width;player.position.y+player.height), P3(player.position.x;player.position.y+player.height), always rounded down to the Tiles position.

Hope it helps.