After implementing SAT (separating axis theorem) and not being happy with it only working on stationary shapes, this in theory allowing for fast objects to glitch through others, I came up with this approach to detect collisions between moving objects.
Algorithm explained
The idea is quite simple:
I figured that, if two shapes A and B aren't intersecting in their starting positions and A moves relative to B, the two shapes collide if and only if
a) any vertex of A crosses a segment of B or
b) any segment of A touches ("sweeps over") a vertex of B.
A vertex of A collides with a segment of B when the segment from A to A + V, V being the velocity of A (aka. it's movement) intersect. That is implemented in the line intersection method of the line class (see below).
Lastly, if I loop through all vertices in A and B and let them collide with all segments of the respective other and repeat the same with B and A with the movement vector turned 180 degrees, the shortest distance any point can travel until a collision happens is the shortest distance A can travel until it collides with B.
To figure out if two segments intersect, I first trasnform them both so that the first segment goes from (0, 0) to (1, 0). Then, the two segments intersect if and only if the second segment cuts the X axis between 0 and 1, which is trivial to implement.
Implementation
Collision detection itself
local function single(a, b, v)
local vertices = {a:vertices()}
local segments = {b:segments()}
local min_intersection
for idx,vertex in ipairs(vertices) do
local v_end = vertex + v
local projection = line(vertex.x, vertex.y, v_end.x, v_end.y)
for idx,segment in ipairs(segments) do
min_intersection = nil_min(min_intersection, projection * segment)
end
end
if min_intersection == 1 then return nil end
return min_intersection
end
function module.movement(a, b, v)
return nil_min(single(a, b, v), single(b, a, -v))
end
Line intersection
intersection = function(self, other)
if not is_line(other) then error("Invalid argument; expected line, got "..type(other), 2) end
local origin, base = self:vectors()
local a = vector_2d(other.x_start, other.y_start)
local b = vector_2d(other.x_end, other.y_end )
a = (a - origin):linear_combination(base)
b = (b - origin):linear_combination(base)
-- Both points are above or below X axis
if a.y < 0 and b.x < 0 or a.y > 0 and b.y > 0 then
return nil
end
-- A always has the smallest X value
if a.x > b.x then
a, b = b, a
end
local x0 = a.x + (b.x-a.x) * a.y / (a.y-b.y)
if x0>=0 and x0<=1 then
return x0
else
return nil, x0
end
end
Cheaty linear combination
As you can see, I only need the linear combination of a given vector and that same vector rotated by 90 degrees, making it quite trivial. Implementation with two vectors is irrelevant to this situation and may get implemented in the future should I need it.
linear_combination = function(self, basis_x, basis_y)
if basis_y then
error("Not Implemented!", 2)
else -- Assumes basis_y is basis_x + 90 degrees
local angle = self:angle() - basis_x:angle()
local f_len = self:length() / basis_x:length()
return vector_2d(
round(f_len * cos(angle)),
round(f_len * sin(angle))
)
end
end;
Okay, that's pretty much it. I have done some testing using busted and it seems to work, but I am not sure if I may have overlooked some stupid mistake that might lead to complications later on. I am also unsure if that algorithm will be fast enough. Considering 3D games do complex collision detection these days, I would assume even a slightly slower algorithm wouldn't impact a 2D game on a modern gaming PC, but since this is löve, would this run on a mid-tier android phone or tablet at an acceptable framerate?
Assumptions:
- Any game this might be used in will not have an unhealthily high number of collisions
- It is purely meant for 2D, no intention to try it in 3D
- most shapes will be rectangles, on average they may have at most 10 or so vertices
- Vectors and segments are implemented using LuaJIT FFI structs, not Lua Tables
As a small extra: The angle at which the first vertex collides with a segment of the other shape, can easily be used to obtain the angle to apply a force to both shapes at the point of collision. This can mean anything from just bouncing the entire object without considering center of mass, to more advanced phyiscal calculations that apply an actual force to the object. While this is interesting and a nice feature of the algorithm, it is trivial to implement and thus out of scope for the actual question.