1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Why are you setting the velocity to 800 * dt.asSeconds() if it is greater than 800? That would make it suddenly slow down if fast enough. Did you mean to just clamp it to 800? \$\endgroup\$ – Moother Apr 8 '15 at 4:34
  • \$\begingroup\$ Yeah that's what I'm supposed to do, I was just testing if the problem didn't come from there, I edit my code. \$\endgroup\$ – Lisible Apr 8 '15 at 6:29
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for you interesting answer. I'll try that later today. \$\endgroup\$ – Lisible Apr 8 '15 at 10:44
  • \$\begingroup\$ For more info you may want to read this article: gafferongames.com/game-physics/fix-your-timestep \$\endgroup\$ – rioki Apr 8 '15 at 11:29
  • 1
    \$\begingroup\$ I think I figured out how to implement this in my game, now collisions look fine. Thank you very much. \$\endgroup\$ – Lisible Apr 8 '15 at 19:26
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.