2
\$\begingroup\$

I'm working through the book 'Introduction to Game Physics with Box2D' and I've created a little pool game with the example code. Despite the name, there is NO box 2D used in this particular exercise.

The example in the book can be seen in this video by the author which only consists of the cue ball and 8-ball. This all works well.

I've written my own version from scratch (using SDL instead of DirectX), using the code in the book as a guide. When I limit it to two balls, everything works great.

When there are more than two balls, things are sometimes problematic in a way I can't predict. Breaking can be fine on one run, or it can cause the balls to 'jump' and flicker as they move presumably looking for empty space. Generally, problems occur when there are more than two balls in a collision.

I've read around and it seems that I need to perform more 'iterations' to get closer to the correct result, but the code that I'd learned will work the same regardless of the number of times it is performed - it sets the positions of any overlapping balls so that they are barely touching. I've tried changing it so it 'pushes' the balls slightly in the direction of the collision normal, with no success.

Here's the relevant code:

bool BallManager::ballBounce(Ball& ball1, Ball& ball2)
{
    float r = static_cast<float>(ball1.diameter_ + ball2.diameter_) * 0.5f;

    // Calculate direction of relative velocity.
    Vector2 v = ball2.velocity_ - ball1.velocity_;
    Vector2 vhat = v.normalized();

    // Calculate relative displacement along normal to collision tangent.
    Vector2 c = ball2.position_ - ball1.position_;

    Vector2 n = c.normalized();

    // Relative distance along normal to tangent.
    float cdotvhat = dot(c, vhat);

    // Balls don't collide, exit early.
    float discriminant = cdotvhat * cdotvhat - c.lengthSquared() + r*r;
    if (discriminant < 0.0f)
    {
        return false;
    }

    // The distance we want to move ball2 back by.
    float dist2 = cdotvhat + sqrt(discriminant);

    float relativeVelocity = 0.0f;
    if (ball2.velocity_.length() > 0.0f)
    {
        relativeVelocity = ball1.velocity_.length() / ball2.velocity_.length();
    }

    // The distance we want to move ball1 back by.
    float dist1 = dist2 * relativeVelocity;

    // Move balls in reverse direction of velocity to point of impact.
    Vector2 v1hat = ball1.velocity_.normalized();
    Vector2 v2hat = ball2.velocity_.normalized();
    ball1.position_ -= dist1 * v1hat;
    ball2.position_ -= dist2 * v2hat;

    // Adjust ball velocities after reflection.
    Vector2 vDiff = ball1.velocity_ - ball2.velocity_;
    vDiff = dot(vDiff, n) * n;
    ball1.velocity_ -= vDiff;
    ball2.velocity_ += vDiff;

    // Finally, move balls again to where they should have bounced to.
    v1hat = ball1.velocity_.normalized();
    v2hat = ball2.velocity_.normalized();
    ball1.position_ += dist1 * v1hat;
    ball2.position_ += dist2 * v2hat;

    return true;
}

At the moment I'm mainly looking for a pointer in the right direction or suggestions since I'm new to physics programming.

\$\endgroup\$
  • \$\begingroup\$ So have you actually tried to perform the collision resolution multiple times instead of just once? The idea behind that approach is that you stop two objects from overlapping by pushing one away and then you start again, checking if this did not cause another overlap with another object \$\endgroup\$ – UnholySheep Oct 21 '14 at 14:33
  • \$\begingroup\$ Yes, I've tried that. The problem is that either they barely get pushed at all and remain overlapping (even after 100 iterations per frame, which is extreme) or the balls 'hop' over each other after the 1st iteration. So does this mean that I've got the right approach but the details are wrong? I'll post some code of the multiple iteration version. \$\endgroup\$ – usm Oct 21 '14 at 15:32
  • \$\begingroup\$ Why implement a "ball only" physics engine when there are perfectly good ones that support all shapes? I am not saying it's wrong, I'm just asking what brought you to do this? I did this myself awhile back and never regretted it. It is really interesting to see how many tiny collisions could exist each frame in a densely populated area. \$\endgroup\$ – AturSams Oct 30 '14 at 10:30
  • \$\begingroup\$ @Zehelvion I'm not opposed to using a library, but right now my goal is to learn the basics of game physics. I'm still working on it (right now, in fact), and I managed to get collisions working better, with some edge cases to sort out. \$\endgroup\$ – usm Oct 30 '14 at 11:30
2
\$\begingroup\$

I've managed to get it working, thanks to @UnholySheep for convincing me that I was on the right track which helped me through some head scratching. Things move smoothly now, and the balls don't stick together either.

I've changed my ballBounce() function to return a bool if there is still a collision/overlap so that my main game loop will iterate again, up to a specified limit.

(EDIT: I've made it a lot simpler, and more accurate - the balls are pushed by the penetration depth, which works in 1 step for several balls) I've also changed the function to push the balls by a tiny amount instead of placing at the edge of the other ball, because even though that worked for two balls, it causes multiple colliding balls to 'jump' to the next empty space instead of moving naturally.

Here is the changed function:

bool BallManager::ballBounce(Ball& ball1, Ball& ball2)
{
    Vector2 c;
    float cdotvhat = 0.0;
    float discriminant = 0.0;
    bool collision = ball1.checkBallCollision(ball2, c, cdotvhat, discriminant);
    if (!collision)
    {
        return false;
    }

    float relativeSpeed = 0.0f;
    if (ball2.velocity_.length() > 0.0f)
    {
        relativeSpeed = ball1.velocity_.length() / ball2.velocity_.length();
    }

    float penetrationDepth = (ball1.getDiameter() + ball2.getDiameter()) * 0.5f - c.length();

    Vector2 n = c.normalized();

    // Adjust ball velocities after reflection.
    Vector2 vDiff = ball1.velocity_ - ball2.velocity_;
    vDiff = dot(vDiff, n) * n;
    ball1.velocity_ -= vDiff;
    ball2.velocity_ += vDiff;

    // BALL_RESTITUTION is 0.9f.
    ball1.velocity_ *= BALL_RESTITUTION;
    ball2.velocity_ *= BALL_RESTITUTION;

    ball1.position_ -= c.normalized() * (penetrationDepth * 0.5f);
    ball2.position_ += c.normalized() * (penetrationDepth * 0.5f);

    return collision;
}

The method checkBallCollision() is just a refactoring of code from the old version of ballBounce(), because I experimented with checking for overlaps in various parts of my code:

bool Ball::checkBallCollision(const Ball& otherBall, Vector2& c, float& cdotvhat, float& discriminant)
{
    float r = static_cast<float>(getDiameter() + otherBall.getDiameter()) * 0.5f;

    // Calculate direction of relative velocity.
    Vector2 v = otherBall.getVelocity() - getVelocity();
    Vector2 vhat = v.normalized();

    // Calculate relative displacement along normal to collision tangent.
    c = otherBall.getPosition() - getPosition();

    // Relative distance along normal to tangent.
    cdotvhat = dot(c, vhat);

    // Balls don't collide, exit early.
    discriminant = cdotvhat * cdotvhat - c.lengthSquared() + r*r;
    if (discriminant < 0.0f)
    {
        return false;
    }

    return true;
}

Finally, (leaving out a few layers of abstraction), here's an excerpt from my main loop (EDIT: I've made changes based on @Roy T.'s suggestions, as well as the well-known GafferOnGames article):

const unsigned int FRAMES_PER_SECOND = 60;
const unsigned int MILLISECS_PER_FRAME = 1000 / FRAMES_PER_SECOND;

const unsigned int PHYSICS_TICKS_PER_SECOND = 100;
const unsigned int MILLISECS_PER_PHYSICS_TICK = 1000 / PHYSICS_TICKS_PER_SECOND;

bool quit = false;

unsigned int lastTickStart = g_timer.time();

while (!quit)
{
    input();

    const float dt = static_cast<float>(MILLISECS_PER_PHYSICS_TICK) / 1000.0f;
    float accumulator = 0.0f;

    unsigned int newTime = g_timer.time();
    unsigned int frameTime = newTime - currentTime;

    accumulator += static_cast<float>(frameTime) / 1000.0f;

    bool unresolvedCollision = true;
    while (accumulator >= dt)
    {
        unresolvedCollision = update(t, dt);
        accumulator -= dt;

        t += dt;
    }

    const double alpha = accumulator / dt;

    renderFrame(alpha);

    currentTime = newTime;

    int delayTime = MILLISECS_PER_FRAME - (g_timer.time() - currentTime);
    if (delayTime > 0)
    {
        SDL_Delay(static_cast<unsigned int>(delayTime));
    }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Don't you need to know the number of iterations up front so you can adjust your delta time? I don't see that happening anywhere at the moment. It seems that if you have 5 iterations now, 5x the normal frame time has passed! \$\endgroup\$ – Roy T. Oct 21 '14 at 20:58
  • \$\begingroup\$ I've added some more code to my answer which shows that I'm doing everything at a fixed rate. Your comment has made me think about timing now - although it now "works" it's not really accurate when there's more than 1 iteration. \$\endgroup\$ – usm Oct 21 '14 at 21:24
  • \$\begingroup\$ I've thought about it and experimented with the code and as far as I understand it is accurate enough. The only situation where it won't be accurate is when we have gone over 10 iterations and we still have balls overlapping. Otherwise, each iteration performs 1/10th of the frame time, and the keepIterating flag is only true if the balls have reached their final resting position, which means no changes will happen for the rest of the frame time, and therefore acting as a nice optimization. I worry that this may be completely wrong. \$\endgroup\$ – usm Oct 21 '14 at 23:38
  • 1
    \$\begingroup\$ Ok, I'm still not 100% sure this is correct. Check out some articles by Gaffer especially "Fix Your Timestep". Its really important to get this right, if you want to achieve stable physics. gafferongames.com/game-physics/fix-your-timestep \$\endgroup\$ – Roy T. Oct 22 '14 at 12:01
  • \$\begingroup\$ Alright, after some consideration, it seems that the solution is to remove the keepIterating flag and always run the same number of iterations on each tick, which removes all variability (but the flag is useful for debugging). A fixed time step only works under the assumption that both rendering and the simulation take very little time compared to each frame time, which is a slightly separate issue, but a valid concern nonetheless. So I'll go ahead and decouple my physics tick rate from the rendering rate too. Thanks! \$\endgroup\$ – usm Oct 26 '14 at 5:11

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.