1
\$\begingroup\$

I am working on a simple 2D game, and I am having problems with collision detection and response. I am using code adapted from this article: http://www.gamedev.net/page/resources/_/technical/game-programming/swept-aabb-collision-detection-and-response-r3084

I have tried many alterations to the code, but I cannot seem to get it to behave as expected. My algorithm attempts to detect collisions between a single moving entity and one or more static blocks. It uses the following logic:

1. Broad-phase collision detection:

Create an AABB that encapsulates the movement of an entity, then detect overlaps with the AABBs of static blocks. Add those collision events to a list, and sort that list by time of impact.

2. Narrow-phase collision detection:

Calculate the time of impact and collision normal for each collision event, and move the entity to the proper position outside of each static block. Use the collision normal to slide the entity to the proper position.

Here is the code I am using to calculate the time of impact for a collision event:

float Collision::collisionTime(QVector2D &normal)
{
    // _one is our moving entity, _two is a static block

    // Calculate the distance to entry and distance to exit
    QVector2D distToEntry, distToExit;
    QVector2D velocity = _one->velocity();

    if (velocity.x() > 0)
    {
        distToEntry.setX(_two->rect().left()  - _one->rect().right());
        distToExit.setX( _two->rect().right() - _one->rect().left());
    }
    else
    {
        distToEntry.setX(_two->rect().right() - _one->rect().left());
        distToExit.setX( _two->rect().left()  - _one->rect().right());
    }

    if (velocity.y() > 0)
    {
        distToEntry.setY(_two->rect().top()    - _one->rect().bottom());
        distToExit.setY( _two->rect().bottom() - _one->rect().top());
    }
    else
    {
        distToEntry.setY(_two->rect().bottom() - _one->rect().top());
        distToExit.setY( _two->rect().top()    - _one->rect().bottom());
    }

    // Calculate the entry and exit times.
    QVector2D entry, exit;
    if (velocity.x() == 0)
    {
        entry.setX(-std::numeric_limits<float>::infinity());
        exit.setX(std::numeric_limits<float>::infinity());
    }
    else
    {
        entry.setX(distToEntry.x() / velocity.x());
        exit.setX(distToExit.x() / velocity.x());
    }

    if (velocity.y() == 0)
    {
        entry.setY(-std::numeric_limits<float>::infinity());
        exit.setY(std::numeric_limits<float>::infinity());
    }
    else
    {
        entry.setY(distToEntry.y() / velocity.y());
        exit.setY(distToExit.y() / velocity.y());
    }

    if (entry.x() > 1.0)
    {
        entry.setX(-std::numeric_limits<float>::infinity());
    }
    if (entry.y() > 1.0)
    {
        entry.setY(-std::numeric_limits<float>::infinity());
    }

    // Find the earliest / latest times of collision.
    float entryTime = std::max(entry.x(), entry.y());
    float exitTime  = std::min(exit.x(),  exit.y());

    // If there was no collision...
    if ((entryTime > exitTime) ||
        (entry.x() < 0 && entry.y() < 0))
    {
        normal = QVector2D(0, 0);
        return 1.0;
    }

    // If there was a collision,
    // set the proper normal and return.
    if (entry.x() >= entry.y())
    {
        if (distToEntry.x() < 0)
        {
            normal = QVector2D(1.0, 0);
        }
        else
        {
            normal = QVector2D(-1.0, 0);
        }
    }
    else
    {
        if (distToEntry.y() < 0)
        {
            normal = QVector2D(0, 1.0);
        }
        else
        {
            normal = QVector2D(0, -1.0);
        }
    }
    return entryTime;
}

And here is the code that generates a collision response:

bool Collision::resolve()
{
    QVector2D collisionNormal;

    // Calculate the collision time and normal.
    float time = collisionTime(collisionNormal);

    // Move to the point of collision.
    _one->setPos(_one->pos().x() + _one->velocity().x() * time,
                 _one->pos().y() + _one->velocity().y() * time);

    float remainingTime = 1.0 - time;

    // If remainingTime > 0, there was a collision.
    // Apply a slide effect.
    if (remainingTime > 0)
    {
        float dotProduct = (_one->velocity().x() * collisionNormal.y() + _one->velocity().y() * collisionNormal.x()) * remainingTime;
        _one->setVelocity(QVector2D(dotProduct * collisionNormal.y(), dotProduct * collisionNormal.x()));
        return true;
    }
    return false;
}

Now, the problems--In the following situations, the moving entity stops completely. I had expected it to slide horizontally in both cases. I have been unable to determine if it is a problem with the collision detection code, or the collision response code:

1. 
     |¯¯¯¯¯¯¯¯|
     | Entity |
     |        |
     |________|
|¯¯¯¯¯¯¯¯|     ⇲ velocity
| Block  |    
|        |    
|________|

2.
|¯¯¯¯¯¯¯¯|
| Entity |
|        | ⇲ velocity
|________|
|¯¯¯¯¯¯¯¯‖¯¯¯¯¯¯¯¯|
| Block  ‖ Block  |
|        ‖        |
|________‖________|
\$\endgroup\$
1
\$\begingroup\$

First, this line:

float dotProduct = (_one->velocity().x() * collisionNormal.y() + _one->velocity().y() * collisionNormal.x()) * remainingTime;

is calculating the wrong quantity (it should be x * x + y * y).

Second, if you want to slide, you simply need to set the component of the velocity parallel to the normal of the collision surface to 0, and retain the velocity orthogonal to that. Ie, you should be doing

// Apply a slide effect.
if (remainingTime > 0)
{
    // This should be a negative value since they are anti-parallel before collision
    // also notice the lack of time in this calculation, so the units of dotProduct will be velocity
    float dotProduct = (_one->velocity().x() * collisionNormal.x() + _one->velocity().y() * collisionNormal.y());

    // now we need to set the velocity in terms of the previous velocity
    // if you do the math, you'll find that v_perp (the sliding velocity) = v + (v.n)*collisionNormal
    // the + comes from the fact that collisionNormal is anti-parallel to the velocity component in the normal direction
    // if it's not then you don't have a collision
    _one->setVelocity(_one->velocity() + dotProduct * collisionNormal);
    return true;
}
\$\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.