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.

I did not read everything, especially not the code (c++ is not my fav language^^), but i have a few questions: What Shapes are the characters, for which you want to detect collisions, made of? Can they move at high speed (more then 1 tile in 1 update)? — Robert P
I'm using rectangles (AABB I believe) and they are not moving fast enough for "bullet-through-paper" problem. — Pontus Magnusson

Chaosed0 Chaosed0 · Accepted Answer · 2014-04-10T20:03:52

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:

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

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

2 Answers