Can't find out why aren't those collisions framerate independent

Question

I'm making a 2D Platform game and I'm having trouble with my collision detection. It doesn't seems to be framerate independent even though I used deltatime there.

The problem is that at 60fps, a collision is sometimes detected too early whereas at 500fps there's no problem (so it really seems like this isn't framerate-independent but I don't know why).

Here's a video of the game running at 60fps https://www.youtube.com/watch?v=P0hRJbw_gcw

And here's the code which is moving my character (I inspired myself about 2D Collision detection from the youtuber dermetfan):

/// Makes the entity jump
void Entity::jump()
{
    m_onGround = false;
    setVelocity(sf::Vector2f(getVelocity().x, -500));
}


/// What to do at each frame
void Entity::update(sf::Time dt)
{
    if (getVelocity().y > 800)
    {
        setVelocity(sf::Vector2f(getVelocity().x, 800));
    }
    else
    {
        setVelocity(sf::Vector2f(getVelocity().x, getVelocity().y - m_map->getGravity()*dt.asSeconds()));
    }


    checkCollisions(dt);
}

/// Collision functions
void Entity::checkCollisions(sf::Time dt)
{
    float oldX = getPosition().x;
    float oldY = getPosition().y;

    bool collX = false;
    bool collY = false;


    setPosition(getPosition().x + getVelocity().x*dt.asSeconds(), getPosition().y); // Setting the position on x

    m_collisionIncrement = (getSize().x < getMap().TILE_SIZE) ? getSize().x / 2 : getMap().TILE_SIZE / 2;

    if (getVelocity().x < 0)
        collX = collidesLeft(); // Using collision tests
    else if (getVelocity().x > 0)
        collX = collidesRight();

    if (collX){ // Testing if there was a collision
        setPosition(oldX, getPosition().y); // Correct position
        setVelocity(0, getVelocity().y*dt.asSeconds());
    }

    setPosition(getPosition().x, getPosition().y + getVelocity().y* dt.asSeconds()); // Setting the position on y

    m_collisionIncrement = (getSize().y < getMap().TILE_SIZE) ? getSize().y / 2 : getMap().TILE_SIZE / 2;

    if (getVelocity().y > 0)
    {
        collY = collidesBottom();
        m_onGround = collY;
    }
    else if (getVelocity().y < 0)
    {
        collY = collidesTop();
    }


    if (collY){ // Testing if there was a collision
        setPosition(getPosition().x, oldY);
        setVelocity(getVelocity().x*dt.asSeconds(), 0);
    }
}

bool Entity::collidesRight()
{
    for (float step = 0; step <= getSize().y; step += m_collisionIncrement)
    {
        if (getMap().isCollideable(getPosition().x + getSize().x, getPosition().y + step))
            return true;
    }
    return false;
}
bool Entity::collidesLeft()
{
    for (float step = 0; step <= getSize().y; step += m_collisionIncrement)
    {
        if (getMap().isCollideable(getPosition().x, getPosition().y + step))
            return true;
    }
    return false;
}
bool Entity::collidesTop()
{
    for (float step = 0; step < getSize().x; step += m_collisionIncrement)
    {
        if (getMap().isCollideable(getPosition().x + step, getPosition().y))
            return true;
    }

    return false;
}
bool Entity::collidesBottom()
{
    for (float step = 0; step < getSize().x; step += m_collisionIncrement)
    {
        if (getMap().isCollideable(getPosition().x + step, getPosition().y + getSize().y))
            return true;
    }
    return false;
}

Answer 1

Making collision detection frame rate independent is basically impossible. While you can reasonably implement frame rate independent rigid body motion and many other simulations by multiplying by dt (delta time), actual collision detection is "impossible" to do frame rate independent.

To illustrate the issue let us assume you have a small cube moving at a high velocity and there is a thin wall in the way. Physics simulation is generally implemented by checking if there are collisions, apply any forces/impulses if it was the case and then advance the simulation by a fixed or dynamic amount of time. The problem comes if the speeding cube is before the wall in one frame and completely after the wall in the next. It did not collide (= intersect) with the wall in the first and it does not collide next frame, for all purposes of the simulation it never collided with the wall.

To remedy this problem there are two solutions. The first is to take into account the motion since the previous frame and take that into account during collision detection. The problem with this is that it makes an already quite computationally expensive operation even more expensive. The second solution is to ensure that your tick rate is sufficiently small to represent the velocities in play. This can either be solved my reducing the tick rate or limiting the maximum velocities of the simulation.

Generally speaking the optimal solution to numeric simulations (rigid body simulation is one) is to use a fixed dt and simply accumulate the ticks in a frame rate (graphic) independent fashion. For example you decide to let your physic simulation tick at 10ms. But you (must) do the simulation interleaved with the render loop. Say this frame 54ms where passed since the last simulation, then you call the simulation 5 times with 10ms and add 4ms to an accumulator. The next frame 68ms where passed, since you have 4ms on the accumulator you run the simulation 7 times and add set the accumulator to 2ms (68+4=72). This also works well when the frame rate is below the tick rate, if 7ms passed since the last frame add 7ms to the accumulator, if it is below 10ms you skip the simulation for this frame.

A constant tick rate for the simulation not only ensures that the collision detection is more stable, it also makes the simulation more deterministic. This means that two machines running the same simulations will have the same result.

Answer 2

If you keep track of the position at last frame you can also create a line from last position to current position and do line to rectangle collision detection to see if you went though the terrain.