Skip to content

Instantly share code, notes, and snippets.

@tesselode
Last active March 31, 2023 04:18
Show Gist options
  • Save tesselode/e1bcf22f2c47baaedcfc472e78cac55e to your computer and use it in GitHub Desktop.
Save tesselode/e1bcf22f2c47baaedcfc472e78cac55e to your computer and use it in GitHub Desktop.
swept AABB collision detection implemented in Lua (commentated)
--[[
moves rectangle A by (dx, dy) and checks for a collision
with rectangle B.
if no collision occurs, returns false.
if a collision does occur, returns:
- the time within the movement when the collision occurs (from 0-1)
- the x component of the normal vector
- the y component of the normal vector
the goal is to find the time range in which rectangle A
is overlapping rectangle B on the X axis, and the time range
in which they overlap on the Y axis. when they're overlapping
on both axes, that's when there's a collision, and the beginning
of that time range is when the collision starts, which is
what we want to return.
]]
local function sweep(a, dx, dy, b)
--[[
first let's find out when the rectangles start and stop overlapping
on the X axis.
]]
local entryTimeX, exitTimeX, entryTimeY, exitTimeY
if dx == 0 then
--[[
if rectangle A isn't moving on the X axis and it's already overlapping
rectangle B on the X axis, then we'll just say it started overlappnig
forever ago and will never stop overlapping.
]]
if a.x < b.x + b.w and b.x < a.x + a.w then
entryTimeX = -math.huge
exitTimeX = math.huge
--[[
if rectangle A isn't moving on the X axis *and* it's not already
overlapping, then A will never collide with B, so we can just stop now.
]]
else
return false
end
else
--[[
otherwise, we know that the amount of distance rectangle
A has travel to overlap rectangle B on this axis is the
distance between the near sides of the boxes.
if A is moving right, then the distance is the left edge of
B minus the right edge of A. if A is moving left, then it's
the left edge of A minus the right edge of B.
]]
local entryDistanceX
if dx > 0 then
entryDistanceX = b.x - (a.x + a.w)
else
entryDistanceX = a.x - (b.x + b.w)
end
--[[
once we have the distance rectangle A has to travel to overlap
with rectangle B on the X axis, we can figure out the time it
takes to overlap, which is distance / speed. in this case,
speed is the amount we're travelling on the X axis in this
movement, which is the absolute value of dx.
]]
entryTimeX = entryDistanceX / math.abs(dx)
--[[
as you might guess, the exit distance is the distance between the
far sides of the rectangles.
]]
local exitDistanceX
if dx > 0 then
exitDistanceX = b.x + b.w - a.x
else
exitDistanceX = a.x + a.w - b.x
end
-- and the exit time is just distance / speed again
exitTimeX = exitDistanceX / math.abs(dx)
end
-- now we'll do the same for the y-axis.
if dy == 0 then
if a.y < b.y + b.h and b.y < a.y + a.h then
entryTimeY = -math.huge
exitTimeY = math.huge
else
return false
end
else
local entryDistanceY
if dy > 0 then
entryDistanceY = b.y - (a.y + a.h)
else
entryDistanceY = a.y - (b.y + b.h)
end
entryTimeY = entryDistanceY / math.abs(dy)
local exitDistanceY
if dy > 0 then
exitDistanceY = b.y + b.h - a.y
else
exitDistanceY = a.y + a.h - b.y
end
exitTimeY = exitDistanceY / math.abs(dy)
end
--[[
now we have the separate time ranges when rectangles A and B
overlap on each axis. the time range when they're actually colliding
is when both time ranges overlap. if the time ranges never overlap,
there's no collision. we can check this the same way we check
for overlapping boxes.
]]
if entryTimeX > exitTimeY or entryTimeY > exitTimeX then return false end
--[[
if they do collide, then the time when they start colliding must be
the later of the two entry times. after all, upon the first entry time,
the rectangles are only overlapping on one axis.
]]
local entryTime = math.max(entryTimeX, entryTimeY)
--[[
if the entry time is outside of the range 0-1, that means no collision
happens within this span of movement.
]]
if entryTime < 0 or entryTime > 1 then return false end
--[[
the last step is to get the normal vector. the normal vector is a
unit vector pointing left, right, up, or down that represents which
way rectangle B would push rectangle A to stop it from moving.
we know whether the collision is horizontal or vertical from which
entry happens last, and we know the sign of the vector from the
direction rectangle A moved.
]]
local normalX, normalY = 0, 0
if entryTimeX > entryTimeY then
normalX = dx > 0 and -1 or 1
else
normalY = dy > 0 and -1 or 1
end
return entryTime, normalX, normalY
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment