Swept AABB Collision Detection and Response Problems

Question

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  |
|        ‖        |
|________‖________|

sh4dow sh4dow · Accepted Answer · 2016-02-09T17:30:18

I'd guess the problem is the entity colliding with the box in every frame (because of touching AABBs). Try moving the entity a tiny amount away from the block to see whether the error persists.

Swept AABB Collision Detection and Response Problems

3 Answers