Collision Detection: Overview of the Basic Approach

Overview of the Basic Approach

I have two approaches to collision detection, each has its advantages and disadvantages.  When used used in combination the result is quite effective.

Approach #1. Step and Check

"Step and Check" breaks the simulation into steps of time, usually matching the "display frames" of the simulation, or an integer multiple of the "frame rate".  The simulation loop advances all moving object one frame, then check if any objects overlap.  If object overlaps then it computes the appropriate response.  The response is usually a "bounce" but it could be any number of things.  [see: collision response]

In the simplest form, you check every moving object against every other object in the simulation, every frame.

// Do not use this code.  This is just the simple general idea.
// mob == Moving Object

DoOneFrame()

{

    foreach(mob in mobList)

        AdvanceOneFrame(mob)

    foreach(obj in allObjList)

    {

        foreach(obj2 in allObjList)
        {
            // don't compare against itself
            // don't compare two fixed objects.

            if(obj != obj2 && (obj1->isMob() || obj2->isMob))

                if(IsOverlapping(obj1, obj2)

                    Respond(obj1, obj2);
        }

    }

}

Sort and Sweep

"Sort and Sweep" is an optimization to "Step and Check" where all the objects are sorted on one coordinate axis.  Then rather than a full N squared compare, the simulation sweeps through the sorted list only comparing objects adjacent and overlapping on the sorted list.
This is a huge reduction on "big O" complexity of the simulation and becomes the center point of the design.

DoOneFrame()

{

    foreach(mob in mobList)

        AdvanceOneFrame(mob)

    sortedList = SortMobs(allObjList);

    for(int i=0; i<sortedList.size(); i++)

    {

        obj1 = sortedList[i];

        for(int n=i+1; n<sortedList.size(); n++)

        {

            obj2 = sortedList[n];

            if(!OverlapsOnSortAxis(obj1, obj2))

                break;

            // don't check two fixed objects.

            if(obj1.isMob() || obj2.isMob())

            {

                if(IsOverlapping(obj, obj)

                    Respond(obj1, obj2);

            }

        }

    }

Pros:

• Easy to implement.
• Works with any sort of motion.
• The Sort-and-sweep optimization is very powerful.

Cons:

• Fast moving objects can "jump" past walls or each other.
• Doesn't handle multiple objects colliding within a single step.
• Doesn't handle object "rattle", i.e. multiple collisions inside of a single step.

Approach #2. Predictive Collision Queue

With "Predictive Collision Detection", the simulation projects the moving objects forward solving for their intersections in the future.  All future collisions are  sorted by time into a queue.  The top item is the next collision in simulation.
The "frame rate" of the application is outside of the collision detection.  There is no "per frame" collision engine work, as there is in "Step and Check".  Several collisions for a single objects can be processed between two consecutive frames.  If the next collision is predicted to be many "frames" away, the objects can moved through those frames with no collision engine work at all.

When the time of the next collision arrives the collision object is popped off the queue. and processed.  If the motion of the object(s) is changed by the collisions, all queued future predictions for the object are removed from the queue. The moving objects involved in then collisions compared against all the other objects in the simulation for all future collisions and the new collisions are sorted into the queue.

Pros:

• Very exact, not dependent on frame rate.  Yielding a better simulation.
• Can be very efficient if there are few collisions.

Cons:

• Predicting the collision require solving for the intersection of the object's predicted path.  This only works for motion that can be describing the motion with analytic function: straight lines, parabolas, etc.  
• A colliding object must be compared against every other object every time its motion changes.  This can be very expensive where there are lots of collisions and lots of objects.
• Sort and Sweep optimization cannot be applied if we predict arbitrarily far out because the bounding box of future path can be very large.

Synthesis #1 + #2

Plug the two approaches together.   Project the motion of all the objects forward one frame.  Instead of moving the objects forward we compute a path for each from last frame's position to this frame's position, and a Bounding Box of the complete path of the object in the inter-frame time period.
The objects of the "sort and sweep" collision detection are these bounding boxes of each object's motion.
When bounding boxes are found to overlap in the sort and sweep phase, their objects are put in a "Predictive Collision Queue" to do a full predictive analysis for the interaction, but only extent of the inter-frame time period.
We still have the restriction that the motion (path) of the object must be an analytic function (ie. line, parabola, etc.) but this approximation is only applied one frame at a time.  The endpoints of the per-frame motion are controlled by the object and over-all game simulation.  It is only the path between the frames, between those points, that is mathematically simplified.

Collision Detection: Minimum Goals

Introduction

When writing a Real Time Strategy game, or a Creature Simulation there is a need for a system to efficiently detect when items are near or touching each other.  This would be a minimal Collision Engine.

Goals

The minimum useful interesting Collision Engine would be:

• 2 dimensional.
• All moving objects are represented with circular bounding containers
• All fixed objects are represented as either circular, line segments, points (very small circles) or collections of these.
• Collision objects can be physical boundaries (actual collisions) or notification boundaries (like doorways or line of sight limits)
• Minimum of "physical" simulation: objects have mass, surfaces have restitution(*), but no friction, and no rotational momentum, or spinning.

(*) Restitution or "Coefficient of Restitution" is the "bounciness" of the surface.  See Wikipedia.