Game Physics Programming: Algorithms and Collision Response
Implementing a physics engine from scratch is one of the most educational exercises in game programming. It teaches spatial reasoning, numerical methods, and systems architecture — skills that transfer directly to engine plugin development, gameplay programming, and performance optimization. This guide covers the core algorithms for collision detection, impulse-based response, continuous detection, and engine architecture, with reference implementations and connections to production engines like PhysX and Box2D.
Broad Phase Collision Detection
The broad phase efficiently filters out pairs that cannot possibly collide, reducing an O(N²) problem to O(N log N) or better.
Sweep-and-Prune (SAP)
Sweep-and-prune projects all bounding volumes onto an axis (typically X) and sorts their min/max values. As the sweep progresses, overlapping intervals on the sort axis are tracked — only objects with overlapping X intervals proceed to test Y and Z axes. SAP works well for scenes with coherent object movement where overlaps change gradually. The algorithm is O(N log N) for sorting and O(N + M) for the sweep where M is the number of overlapping pairs. In practice, M is much smaller than N² for typical game scenes. Box2D’s broad phase uses a modified SAP with pair buffering for temporal coherence.
Spatial Hashing
Spatial hashing divides the world into a grid of cells and assigns each object to the cell containing its center or bounding box. Collision tests are performed only between objects in the same or adjacent cells. The hash function maps grid coordinates to an index in a flat array, avoiding the memory overhead of a full 2D/3D array. A common hash function for 2D: hash = (x * 73856093) ^ (y * 19349663) % tableSize. The implementation maintains a hash map from cell coordinates to a list of contained object IDs. This approach is cache-friendly and parallelizable, making it the preferred broad phase for particle systems and games with many dynamic objects. The GDC 2016 talk “Physics Optimization in Cities: Skylines” (Colossal Order) described how spatial hashing enabled 100,000+ simulated citizens by limiting collision checks to 3×3 cell neighborhoods.
Bounding Volume Hierarchies
A BVH is a tree structure where each node stores the bounding volume of all objects in its subtree. Dynamic BVHs support efficient insertion, removal, and refitting when objects move. The tree is built bottom-up: adjacent objects are grouped into parent nodes until a single root node contains everything. Querying the BVH for collision candidates is a recursive descent — if the query volume does not intersect a node’s bounding volume, the entire subtree is skipped. The Bullet Physics SDK uses a dynamic BVH as its default broad phase with configurable tree quality heuristics for rebuild frequency.
Narrow Phase Collision Detection
The narrow phase performs exact intersection tests on pairs that pass the broad phase.
AABB Collision Test
The Axis-Aligned Bounding Box test checks for overlap on each axis independently. If ranges overlap on all axes, the boxes intersect. This is the cheapest narrow-phase test — four comparison operations in 2D, six in 3D — and forms the basis for all bounding volume tests.
Oriented Bounding Box (OBB) Test
OBBs rotate with the object, providing tighter fits than AABBs for rotated geometry. The Separating Axis Theorem tests all 15 potential axes in 3D: 3 face normals from each box (6 axes), and 9 edge cross products (3 from each box × 3 from each box). For real-time applications, the SAT test for OBBs is often optimized using the following insight: if the projected intervals of the two boxes onto any axis do not overlap, the boxes do not intersect. Early-exit strategies test the most likely separating axes first (face normals before edge cross products) to minimize average-case cost.
GJK and EPA
The Gilbert-Johnson-Keerthi (GJK) algorithm computes the minimum distance between two convex shapes. It iteratively searches the Minkowski difference (the set of all difference vectors between points in the two shapes) for the point closest to the origin. GJK works with any convex shape by implementing a support function that returns the farthest point in a given direction — this allows collision detection between different primitive types (sphere vs. box, cylinder vs. convex hull). The Expanding Polytope Algorithm (EPA) extends GJK to compute the penetration depth and contact normal when shapes overlap. The Bullet Physics SDK documentation includes detailed GJK and EPA implementation notes.
Impulse-Based Collision Response
After detecting a collision, the physics engine must resolve it by separating the objects and modifying their velocities.
Contact Point Computation
The contact point is the location where the two objects first touch. For box-box collisions, the contact manifold contains up to 8 contact points at the intersecting feature combinations (vertex-face, edge-edge). The deepest penetrating point is typically used as the primary contact for response computation. The contact normal points from object B toward object A along the direction of minimum penetration.
Impulse Resolution Formula
The impulse magnitude for a collision between two rigid bodies is computed from their relative velocity at the contact point, the contact normal, and the restitution coefficient. The impulse J is:
J = -(1 + restitution) × (relativeVelocity · contactNormal) / (1/mA + 1/mB + …inertial terms…)
For spheres, the inertial contribution is zero (the contact normal passes through the center of mass). For general bodies, the inertial term depends on the torque generated by applying force at the contact point — this is the cross product of the contact offset and the contact normal, then transformed by the inverse inertia tensor.
Friction
Friction is resolved as a tangential impulse at the contact point. Compute the tangent direction perpendicular to the contact normal, calculate the desired friction impulse magnitude using the Coulomb model (friction coefficient × normal impulse magnitude), and clamp it to prevent exceeding the maximum static friction. The sequential impulse solver in most engines (PhysX, Box2D, Bullet) iterates over all contact points 3–10 times per frame to converge on a stable solution.
Continuous Collision Detection
Standard discrete collision detection checks for overlap at the end of each frame. Fast-moving objects can tunnel through thin geometry between frames.
Swept Sphere
For a sphere moving in a straight line over a frame, swept collision computes the earliest time of impact (TOI) along the path. Parameterize the sphere’s center as C(t) = C0 + v × t for t in [0, 1]. Solve the quadratic equation for when the distance from C(t) to the triangle plane equals the sphere radius, then test whether the impact point lies within the triangle.
Conservative Advancement
For arbitrary convex shapes, conservative advancement iteratively moves the shape forward by small steps using the GJK distance result. At each step, if the minimum distance between the shapes is below a threshold, the shapes are in contact. This approach handles rotation and curved paths at the cost of multiple iterations. The Box2D continuous physics uses conservative advancement for objects with CCD enabled, limiting it to bodies marked as “bullet” type to control performance cost.
One-Sided Collision for Character Controllers
Character controllers typically use one-sided collision with a kinematic capsule — the capsule moves and the engine detects obstacles along the path, stopping at the first contact. This is not true CCD but provides adequate behavior for player characters at typical movement speeds. Unity’s CharacterController and Godot’s CharacterBody3D both use this approach internally.
Physics Engine Architecture
Fixed Timestep Loop
A physics engine runs at a fixed timestep (dt), typically 1/60 (16.67 ms) or 1/50 (20 ms). The main game loop accumulates time and runs physics iterations until the accumulated time is consumed. This ensures deterministic, stable behavior regardless of display frame rate.
Island Simulation
Physics engines partition the world into islands — groups of interacting bodies (colliding, joint-connected, or within a distance threshold). Each island can be solved independently, enabling parallel execution. Static and sleeping bodies are excluded from islands, reducing solver work. The Unreal Chaos Physics documentation describes how islands are detected via graph connectivity and assigned to worker threads.
Warm Starting
Warm starting reuses contact impulses from the previous frame as the initial guess for the current frame’s solver. This dramatically improves convergence speed for stacks of objects — instead of starting from zero each frame, the solver begins close to the correct solution. Box2D’s iterating solver uses warm starting with Baumgarte stabilization to handle contact and joint constraints with 3–8 iterations per frame.
For practical integration with engines, see Game Physics Guide. For performance optimization of physics-heavy games, refer to Game Optimization.
Frequently Asked Questions
Q: When should I implement my own physics engine instead of using a built-in one? A: Build your own for educational purposes, for 2D games with very specific physics requirements (custom vehicle physics, rope simulations), or for games needing deterministic lockstep physics across network peers. For most projects, built-in engines (PhysX, Chaos, Box2D) are more stable and feature-complete.
Q: What is the difference between sequential impulse and PGS solvers? A: Sequential impulse (SI) resolves one constraint at a time, iterating through all constraints and applying impulses immediately. Projected Gauss-Seidel (PGS) solves constraint equations simultaneously using matrix projection. SI is simpler and more memory-efficient; PGS converges faster for large systems. Most modern engines use a hybrid approach.
Q: How do I handle collision between a moving character and a rotating platform? A: The platform’s velocity at the contact point includes rotational velocity (omega cross radius). Add this velocity to the platform’s linear velocity when computing the relative velocity for the collision response. The character receives the platform’s motion through the contact impulse.
Q: What causes physics instability with stacked boxes? A: Floating-point precision limits, insufficient solver iterations (need 8+ for stacks), large mass ratios (keep under 10:1), and small penetrations from earlier solver iterations. Use smaller timesteps, increase solver iterations, enable sleeping, and avoid mass ratios above 10:1.
Q: How do I implement breakable joints? A: Track the cumulative impulse or force applied to a joint each frame. When it exceeds a threshold, destroy the joint and optionally activate connected bodies with an impulse derived from the breaking force. This creates the visual of chains snapping, ropes breaking, and structures collapsing under load.
For a comprehensive overview, read our article on 2D Game Development Guide.
For a comprehensive overview, read our article on 3D Game Development Guide.