swept AABB collision detection implemented in Lua (commentated)

swept-aabb.lua

--[[
	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