Collision response

Introduction

The following tutorial attempts to tackle some of the challenges of writing a collision system for simple games.

Simulation

We begin with "unconstrained" motion based on simple Newtonian physics. Each object has a velocity vector that is added to its position using the formula: 
velocity = velocity + gravity*dt
position = position + velocity*dt
These calculations are performed during each step of the simulation for every moving (dynamic) object. For practical reasons, it's useful to limit the velocity of moving objects to a certain threshold (maxVelocity). It's also common in games to have non-moving or "static" objects. Static objects are not affected by gravity or collisions and can be used to represent platforms, walls and so on. 

-- updates the simulation
function update(dt)
  -- update velocity vectors
  local grav = gravity*dt
  for i = 1, #dynamics do
    local d = dynamics[i]
    -- gravity
    d.yv = d.yv + grav
    d.xv, d.yv = clampVec(d.xv, d.yv, maxVelocity)
  end
  -- move dynamic objects
  for i = 1, #dynamics do
    local d = dynamics[i]
    moveShape(d, d.xv*dt, d.yv*dt)
    -- check and resolve collisions
    for j, s in ipairs(statics) do
      checkCollision(d, s)
    end
    for j = i + 1, #dynamics do
      checkCollision(d, dynamics[j])
    end
  end
end
The technique can be summed up as:
    1. Update the velocities and positions of all moving objects
    2. Iterate all pairs of intersecting objects
      a) Move one of the objects (so the two no longer intersect)
      b) Adjust the velocities of both objects

Detection

First, we want to check if two objects are intersecting. We'll be looking at axis-aligned rectangles in particular since they are simple and sufficient for most old-school games. One approach is to represent each rectangle shape as a center position with half-width/height extents.

Axis-aligned rectangle with position and extents

This way, we can simply compare the distance between the centers of two rectangles against the sum of their extents. The following algorithm checks the X and Y axis separately: 

function testRectRect(a, b)
  -- distance between the rects
  local dx, dy = a.x - b.x, a.y - b.y
  local adx = math.abs(dx)
  local ady = math.abs(dy)
  -- sum of the extents
  local shw, shh = a.hw + b.hw, a.hh + b.hh
  if adx >= shw or ady >= shh then
    -- no intersection
    return
  end
  -- intersection

Separation

Suppose that the previous algorithm detects an intersection between two rectangles.

Intersection between two rectangles

Next, we have to figure out how much the first rectangle (a) needs to be displaced (sx, sy) so that the two shapes are no longer intersecting. The result is sometimes called the "shortest separation" vector. 

  -- shortest separation
  local sx, sy = shw - adx, shh - ady
  -- ignore longer axis
  if sx < sy then
    if sx > 0 then
      sy = 0
    end
  else
    if sy > 0 then
      sx = 0
    end
  end
  -- correct sign
  if dx < 0 then
    sx = -sx
  end
  if dy < 0 then
    sy = -sy
  end
  return sx, sy
end
The "separation" vector gives us two important pieces of information about the intersecting shapes:
    1. magnitude (penetration depth)
    2. direction (penetration axis or the "collision normal")
Once we know how to find the "separation vector", it's easy to move the two colliding objects apart. This alone is enough for games (like the original Super Mario, Megaman or Contra) where you just want to ensure that the player cannot pass through the static environment. 
-- checks for collision
function checkCollision(a, b)
  local sx, sy = testRectRect(a, b)
  if sx and sy then
    solveCollision(a, b, sx, sy)
  end
end

-- resolves collision
function solveCollision(a, b, sx, sy)
  -- find the collision normal
  local d = math.sqrt(sx*sx + sy*sy)
  local nx, ny = sx/d, sy/d
  -- relative velocity
  local vx, vy = a.xv - (b.xv or 0), a.yv - (b.yv or 0)
  -- penetration speed
  local ps = vx*nx + vy*ny
  -- objects moving towards each other?
  if ps <= 0 then
    -- separate the two objects
    moveShape(a, sx, sy)
  end
end

Response

Generally speaking, "realistic" physics simulation is a difficult problem. So a lot of games have some collision response (like pushable blocks) that although not physically accurate, make a fun addition to the gameplay. We can produce a variety of effects by modifying the velocities of one or both objects during a collision.

Relative velocity

First, we subtract the velocities of the two objects. This gives us the relative velocity during impact.


Subtracting the velocities of objects a and b allows us to treat shape b as if it is stationary. 

-- resolves collision
function solveCollision(a, b, sx, sy)
  -- find the collision normal
  local d = math.sqrt(sx*sx + sy*sy)
  local nx, ny = sx/d, sy/d
  -- relative velocity
  local vx, vy = a.xv - (b.xv or 0), a.yv - (b.yv or 0)
Next, we have to figure out how the moving shape should react to the collision (bounce, slide or stop completely). This is done be "splitting" the relative velocity into penetration and tangent components.

Velocity components:
v: velocity (black)
vp: penetration component (red)
vt: tangent component (yellow)
n: collision normal axis (blue)

The dot product (ps) between the relative velocity and the collision normal (vx*nx + vy*ny) gives us the speed at which the two objects are moving toward each other. This product (ps) may be positive or negative depending on whether the objects are moving apart or toward each other. 

-- penetration speed
local ps = vx*nx + vy*ny
-- objects moving apart?
if ps > 0 then
  return
end
-- penetration component
local px, py = nx*ps, ny*ps
Usually, we calculate the tangent component by rotating the collision normal 90 degrees and using the dot product: 
-- tangent speed
local ts = vx*ny - vy*nx
-- tangent component
local tx, ty = ny*ts, -nx*ts
However, since we already know the penetration speed (ps) and velocity (px, py) at which the two objects are colliding, we can just subtract it from the relative velocity (vx, vy): 
-- penetration speed
local ps = vx*nx + vy*ny
-- penetration component
local px, py = nx*ps, ny*ps
-- tangent component
local tx, ty = vx - px, vy - py

Restitution or bounce

The restitution coefficient (or bounce) describes how "elastic" is the collision. This coefficient is a value between 0 and 1, where 0 means "inelastic" and 1 means "perfectly elastic".

Example of an elastic (green) versus non-elastic collision (pink).

Restitution always acts along the penetration axis (parallel to the collision normal). Remember that the "collision normal" is basically the axis of shortest separation between two colliding shapes. 
-- penetration speed
local ps = vx*nx + vy*ny
-- penetration component
local px, py = nx*ps, ny*ps
-- restitution
local r = 1 + math.max(a.bounce, b.bounce or 0)
-- change the velocity of shape a
a.xv = a.xv - px*r
a.yv = a.yv - py*r

Friction

The friction coefficient describes how much velocity is "lost" when the edges of two shapes are touching. Friction always acts along the tangent axis (perpendicular to the collision normal).
Note that the two objects may have different friction or restitution (bounce) coefficients. Combining each two coefficients "realistically" involves additional math so we use the "min" and "max" functions as a simplification. 
-- penetration speed
local ps = vx*nx + vy*ny
-- penetration component
local px, py = nx*ps, ny*ps
-- tangent component
local tx, ty = vx - px, vy - py
-- restitution
local r = 1 + math.max(a.bounce, b.bounce or 0)
-- friction
local f = math.min(a.friction, b.friction or 0)
-- change the velocity of shape a
a.xv = a.xv - px*r + tx*f
a.yv = a.yv - py*r + ty*f

Finaly, we multiply the penetration component by the restitution (r), the tangent component by the friction (f) and add them together to get the resulting change in velocity of the moving shape.

Physics

Mass and momentum

Roland Yonaba pointed out that the equations above do not take mass into consideration. Therefore a small rectangle can easily push large rectangles when they collide. In a sense, all rectangles (regardless of their size) are treated as if they have equal mass. This is usually fine for old-school games and makes the equations a little bit easier to understand. Mass can be introduced to the simulation as follows: 
-- how mass affects impulse
ChangeInVelocity = FinalVelocity - InitialVelocity
Impulse = Mass*ChangeInVelocity

-- how mass affects momentum
Momentum = Velocity*Mass

-- how mass affects force
Acceleration = ChangeInVelocity/Time
Force = Mass*Acceleration

Coulomb's law and friction

The code in this tutorial makes some obvious simplifications to the real laws of physics. However a somewhat subtle error is allowed in the way friction is simulated. With real life collisions: "the force of friction is always less than or equal to the normal [separation] force multiplied by some constant (whose value depends on the materials of the objects)". Without taking Coulomb's law into consideration objects with friction tend to behave like they're "sticky". I mention this perhaps to stir your interest in real physics and how many of its rich and interesting equations could be simulated in games.


Demo: simple collision response