Collision Detection

Once several things move, the engine has to know when they touch, how far they overlap, and which way to push them apart. After this lesson your program will report every overlapping pair of boxes with a penetration depth and a push direction, and will answer a second question that catches fast objects: "if this box moves this far in one frame, what does it hit first?"

Boxes and the overlap test

An AABB (axis-aligned bounding box) is a rectangle whose sides are parallel to the axes, stored as a corner and a size. Two AABBs overlap exactly when their shadows overlap on both axes. On one axis the shadows of A and B overlap by

overlap = min(A.right, B.right) - max(A.left, B.left)

If that is zero or negative on either axis there is a gap, or the boxes merely touch, and they do not collide. This is the separating-axis idea in its simplest form: one axis with a gap is enough to say "no".

Depth and normal

When both overlaps are positive, resolving the contact needs a depth and a normal. Push along the axis with the smaller overlap, because that is the cheapest way out. The normal points from A towards B along that axis: compare the centres. To stay in integers, compare 2*x + w rather than halving.

Worked example: A is at (0,0) size 6x6 and B at (4,5) size 6x6. On x the overlap is min(6,10) - max(0,4) = 2. On y it is min(6,11) - max(0,5) = 1. The smaller is y, so the depth is 1; the centres are 6 and 16 on y, so B is above A (larger y) and the normal is (0,1). Pushing B up by 1 separates them.

Broadphase and narrowphase

Testing every pair is O(n^2): 1,000 objects mean half a million tests per frame. A broadphase cheaply discards pairs that cannot touch, and the exact test above (the narrowphase) runs only on the survivors. Common broadphases: a spatial hash that drops each box into the grid cells it covers and only compares boxes sharing a cell (remember a pair can share several cells, so deduplicate), a quadtree, or sweep-and-prune. Whatever the broadphase, the result must be the same set of pairs, reported in a fixed order.

Tunnelling and swept tests

A bullet moving 100 units a frame can jump over a wall 1 unit thick: before the move it is on one side, after the move on the other, and no frame ever shows an overlap. Continuous collision detection tests the whole move instead. For a moving box and a static one, work out per axis the fraction of the move (0 to 1) at which the boxes start overlapping and at which they stop. The boxes are touching only while both axes overlap, so:

• the entry time is the later of the two entry times;
• the exit time is the earlier of the two exit times;
• there is a hit if entry is between 0 and 1 and entry comes strictly before exit.

On an axis with no movement the shadows either always overlap (entry minus infinity, exit plus infinity) or never do. The normal of the face that was hit is the axis that entered last, pointing against the movement.

Example: a 3x3 box at (0,0) moves 20 to the right towards a tall wall whose left edge is at x=15. The box's right edge starts at 3, so on x it enters the wall's shadow at (15 - 3) / 20 = 0.6 of the move, and the y axis always overlaps. The hit is at t = 0.6 and the normal is (-1,0), because the box was moving right. A box that already overlaps the other one has a negative entry time; that pair belongs to the narrowphase, not to the sweep.

Common mistakes

• Using < where touching boxes must not collide: overlap <= 0 means no contact.
• Pushing along the larger overlap, which teleports objects across each other.
• Comparing only one axis, or the corners instead of the shadows.
• Sweeping against a box the mover already overlaps and reporting a negative time.
• Reporting pairs in discovery order. Sort them: broadphases find pairs in different orders.

Your exercise

Implement contact and sweep_hit as described in the exercise. The starter registers boxes, loops over the pairs, picks the nearest sweep hit and prints. The most likely mistake is the sign of the normal.