Collision between two axis-aligned moving rectangles

[RNavega]

This is a method for detecting the collision between two axis-aligned moving rectangles.

Usually in a game or some other type of real-time app, the movements of things on each frame (like every 16ms at 60 FPS) is usually small enough that you can get away with moving a rectangle and then checking for collisions after the fact. In this way, one rectangle is moving while the other is stationary, which is an approximation, or as the bump docs put it:

bump is not a good match for:

• Games that require very fast objects colliding realistically against each other (in bump, being gameistic, objects are moved and collided one at a time).

So the challenge was to find a way to calculate the exact collision moment when both of them are moving during the same frame.
I also want to make some mockup images of how the math involved works, to practice some design -- and I'll add it in here later.

The code is all in the main.lua below, especially in function "find_sweep_collision".
It's pretty fun trying to find a near-miss scenario, like moving the destination of a rectangle far enough that it speeds up and nearly misses the other.

preview.png (26.22 KiB) Viewed 3104 times

Code: Select all

-- Recipe for collision detection between two axis-aligned moving rectangles.
-- (Also works for moving vs still rectangles, and for still vs still rectangles)
--
-- By Rafael Navega (2025);
-- Frame of reference optimization by Pedro Gimeno (2025).
--
-- Public Domain

io.stdout:setvbuf('no')


local rect_a = {x = 80, y = 400, w = 220, h = 150, vx = 320, vy = -240}
local rect_b = {x = 650, y = 380, w = 50, h = 80, vx = -105, vy = -160}
rect_b.cx, rect_b.cy = rect_b.x, rect_b.y


local speed = 300.0

local anim_speed = 0.7
local preview_t = 0.25


function love.load()
    love.graphics.setLineWidth(1.0)
end



function find_sweep_collision(a_x, a_y, a_w, a_h, a_vx, a_vy,
                              b_x, b_y, b_w, b_h, b_vx, b_vy)
    -- Frame of reference optimization: reimagine the velocity of A
    -- so that the rectangle B is considered as not moving.
    -- This allows finding the moment of collision 't', if any, using the simpler
    -- code for the "moving rectangle vs still rectangle" collision case.
    a_vx = a_vx - b_vx
    a_vy = a_vy - b_vy

    -- Consider the line equation / linear motion formula:
    -- p = p0 + v . t
    -- Finding the 't' when the leading_x edge aligns with opposing_x edge:
    -- opposing_x = leading_x + vx . t_align_x
    -- t_align_x = (opposing_x - leading_x) / vx
    -- (Similar for the Y axis, finding t_align_y.)

    local t_align_x, t_align_y

    -- Vertical edges.
    if a_vx > 0.0 then
        -- Leading  X: a_x + a_w (A RIGHT edge)
        -- Opposing X: b_x       (B LEFT edge)
        t_align_x    = (b_x - (a_x + a_w)) / a_vx
    elseif a_vx < 0.0 then
        -- Leading  X: a_x       (A LEFT edge)
        -- Opposing X: b_x + b_w (B RIGHT edge)
        t_align_x    = ((b_x + b_w) - a_x) / a_vx
    else
        t_align_x = -1.0
    end
    -- Horizontal edges.
    if a_vy > 0.0 then
        -- Leading  Y: a_y + a_h (A BOTTOM edge)
        -- Opposing Y: b_y       (B TOP edge)
        t_align_y    = (b_y - (a_y + a_h)) / a_vy
    elseif a_vy < 0.0 then
        -- Leading  Y: a_y       (A TOP edge)
        -- Opposing Y: b_y + b_h (B BOTTOM edge)
        t_align_y    = ((b_y + b_h) - a_y) / a_vy
    else
        t_align_y = -1.0
    end

    local collided = false
    local collision_t

    -- Empirically tested: if the alignment moments are both below zero, or if either
    -- of them are above 1, then a sweeping collision can't happen.
    if (t_align_x > 1.0 or t_align_y > 1.0) or
       (t_align_x < 0.0 and t_align_y < 0.0) then
        collision_t = nil
        -- At least test for a pre-collision.
        if a_x < b_x + b_w and b_x < a_x + a_w and
           a_y < b_y + b_h and b_y < a_y + a_h then
            collided = true
        end
    else
        -- Through testing it was found that the edge of B that will collide
        -- during the sweep of A will be the one with the largest parameter 't'.
        if t_align_x > t_align_y then
            local a_edge_start = a_y + a_vy * t_align_x
            local a_edge_end   = a_edge_start + a_h
            if (a_edge_start < (b_y + b_h) and b_y < a_edge_end) then
                collided = true
                collision_t = t_align_x
            end
        else
            local a_edge_start = a_x + a_vx * t_align_y
            local a_edge_end   = a_edge_start + a_w
            if (a_edge_start < (b_x + b_w) and b_x < a_edge_end) then
                collided = true
                collision_t = t_align_y
            end
        end
    end
    return collided, collision_t
end


function draw_movement_shape(rect)
    local left1   = rect.x
    local right1  = rect.x + rect.w
    local top1    = rect.y
    local bottom1 = rect.y + rect.h

    local left2   = left1 + rect.vx
    local right2  = right1 + rect.vx
    local top2    = top1 + rect.vy
    local bottom2 = bottom1 + rect.vy
    if rect.vx > 0.0 then
        if rect.vy > 0.0 then
            -- RIGHT, BOTTOM.
            love.graphics.line(left1, bottom1, left2, bottom2)
            love.graphics.line(right1, top1, right2, top2)
            love.graphics.line(right1, bottom1, right2, bottom2)
            love.graphics.line(right2, top2, right2, bottom2)
            love.graphics.line(left2, bottom2, right2, bottom2)
        elseif rect.vy < 0.0 then
            -- RIGHT, UP.
            love.graphics.line(left1, top1, left2, top2)
            love.graphics.line(right1, bottom1, right2, bottom2)
            love.graphics.line(right1, top1, right2, top2)
            love.graphics.line(right2, top2, right2, bottom2)
            love.graphics.line(left2, top2, right2, top2)
        else
            -- RIGHT.
            love.graphics.line(right1, top1, right2, top2)
            love.graphics.line(right1, bottom1, right2, bottom2)
            love.graphics.line(right2, top2, right2, bottom2)
        end
    elseif rect.vx < 0.0 then
        if rect.vy > 0.0 then
            -- LEFT, BOTTOM.
            love.graphics.line(left1, top1, left2, top2)
            love.graphics.line(right1, bottom1, right2, bottom2)
            love.graphics.line(left1, bottom1, left2, bottom2)
            love.graphics.line(left2, top2, left2, bottom2)
            love.graphics.line(left2, bottom2, right2, bottom2)
        elseif rect.vy < 0.0 then
            -- LEFT, TOP.
            love.graphics.line(left1, bottom1, left2, bottom2)
            love.graphics.line(right1, top1, right2, top2)
            love.graphics.line(left1, top1, left2, top2)
            love.graphics.line(left2, top2, left2, bottom2)
            love.graphics.line(left2, top2, right2, top2)
        else
            -- LEFT.
            love.graphics.line(left1, top1, left2, top2)
            love.graphics.line(left1, bottom1, left2, bottom2)
            love.graphics.line(left2, top2, left2, bottom2)
        end
    elseif rect.vy > 0.0 then
        -- BOTTOM.
        love.graphics.line(left1, bottom1, left2, bottom2)
        love.graphics.line(right1, bottom1, right2, bottom2)
        love.graphics.line(left2, bottom2, right2, bottom2)
    elseif rect.vy < 0.0 then
        -- TOP.
        love.graphics.line(left1, top1, left2, top2)
        love.graphics.line(right1, top1, right2, top2)
        love.graphics.line(left2, top2, right2, top2)
    end
end


function love.draw()
    -- Rectangle A movement shape.
    love.graphics.setColor(0.2, 0.2, 0.2)
    draw_movement_shape(rect_a)
    -- The "preview" of rectangle A.
    love.graphics.setColor(1, 1, 1, 0.4)
    love.graphics.rectangle('line',
                            rect_a.x + rect_a.vx * preview_t,
                            rect_a.y + rect_a.vy * preview_t,
                            rect_a.w, rect_a.h)
    love.graphics.setColor(1, 1, 1)
    love.graphics.rectangle('line', rect_a.x, rect_a.y, rect_a.w, rect_a.h)

    -- Rectangle B movement shape.
    love.graphics.setColor(0.0, 1, 1, 0.4)
    draw_movement_shape(rect_b)
    -- The "preview" of rectangle B.
    love.graphics.setColor(0, 1, 1, 0.4)
    love.graphics.rectangle('line',
                            rect_b.x + rect_b.vx * preview_t,
                            rect_b.y + rect_b.vy * preview_t,
                            rect_b.w, rect_b.h)
    love.graphics.setColor(0, 1, 1)
    love.graphics.rectangle('line', rect_b.x, rect_b.y, rect_b.w, rect_b.h)

    -- Draw the debug text overlay. Switch to false to hide it.
    if true then
        love.graphics.setColor(1, 1, 1)
        love.graphics.print('Use A,W,S,D or the ARROW KEYS to move the rectangle destinations', 10, 10)
        love.graphics.print('Hold Shift to move the rectangles themselves', 10, 30)
        love.graphics.print('Hold 1 or 2 to control the "preview" t', 10, 50)
        love.graphics.print(('Hold Ctrl or Space while using the other keys ' ..
                             'for precision mode (slow motion)'), 10, 70)
        love.graphics.print(('PREVIEW t = %.3f'):format(preview_t), 10, 120)
    end

    local collided, col_t = find_sweep_collision(
        rect_a.x, rect_a.y, rect_a.w, rect_a.h, rect_a.vx, rect_a.vy,
        rect_b.x, rect_b.y, rect_b.w, rect_b.h, rect_b.vx, rect_b.vy
    )
    if col_t then
        love.graphics.setColor(1, 0.6, 0)
        local col_x = rect_a.x + rect_a.vx * col_t
        local col_y = rect_a.y + rect_a.vy * col_t
        love.graphics.rectangle('line', col_x, col_y, rect_a.w, rect_a.h)
        love.graphics.print(('Collision moment (t = %.3f)'):format(col_t), col_x, col_y - 30)
    end
    if collided then
        love.graphics.setColor(0, 1, 1)
        love.graphics.rectangle('fill', rect_b.x, rect_b.y, rect_b.w, rect_b.h)
        -- A valid collision with nil 't' means a pre-collision (colliding at their
        -- starting positions).
        if not col_t then
            love.graphics.print('(Pre-collision)', rect_b.x, rect_b.y + rect_b.h + 5)
        end
    end
end


function love.keypressed(key)
    if key == 'escape' then
        love.event.quit()
    end
end


function love.update(dt)
    if (love.keyboard.isDown('lctrl')
        or love.keyboard.isDown('rctrl')
        or love.keyboard.isDown('space')) then
        dt = dt * 0.1
    end

    if love.keyboard.isDown('1') then
        preview_t = preview_t - anim_speed * dt
        if preview_t < 0.0 then preview_t = 0.0 end
    elseif love.keyboard.isDown('2') then
        preview_t = preview_t + anim_speed * dt
        if preview_t > 1.0 then preview_t = 1.0 end
    end

    local a_dir_x = (love.keyboard.isDown('d') and dt or (love.keyboard.isDown('a') and -dt or 0))
    local a_dir_y = (love.keyboard.isDown('s') and dt or (love.keyboard.isDown('w') and -dt or 0))
    local b_dir_x = (love.keyboard.isDown('right') and dt or (love.keyboard.isDown('left') and -dt or 0))
    local b_dir_y = (love.keyboard.isDown('down')  and dt or (love.keyboard.isDown('up')   and -dt or 0))

    if love.keyboard.isDown('lshift') or love.keyboard.isDown('rshift') then
        rect_a.x  = rect_a.x + speed * a_dir_x
        rect_a.y  = rect_a.y + speed * a_dir_y
        rect_a.vx = rect_a.vx - speed * a_dir_x
        rect_a.vy = rect_a.vy - speed * a_dir_y

        rect_b.x  = rect_b.x + speed * b_dir_x
        rect_b.y  = rect_b.y + speed * b_dir_y
        rect_b.vx = rect_b.vx - speed * b_dir_x
        rect_b.vy = rect_b.vy - speed * b_dir_y
    else
        rect_a.vx = rect_a.vx + speed * a_dir_x
        rect_a.vy = rect_a.vy + speed * a_dir_y
        rect_b.vx = rect_b.vx + speed * b_dir_x
        rect_b.vy = rect_b.vy + speed * b_dir_y
    end
end

[RNavega]

Here's how it works. To keep it short.


Context

You have a potentially moving rectangle A (blue) and a potentially moving rectangle (B). I say "potentially" because if only one of them is moving while the other is still, the detection works as well.
The detection also works if the movement is restricted to one axis, like an only horizontal or only vertical movement.
So this recipe is fast enough that it can be used in all of these cases (moving vs moving, moving vs still, and also still vs still as it does check for initial overlaps).

slide_01.png (1.08 KiB) Viewed 3012 times

A key concept: these AABB / axis-aligned rectangles never rotate and their sides are always perpendicular.
This means that a certain side of rectangle A will only ever collide with the opposite side of rectangle B. It can't ever collide with any other side but that one.

So if rectangle A is moving in a certain direction where its right side and its top side are "leading" the movement (they face the direction of movement, one for the horizontal axis and the other for the vertical axis), then if the rectangles do collide at all, that can only happen with the opposite sides of those: the left side and the bottom side of rectangle B.

slide_02.png (36.2 KiB) Viewed 3012 times

This means that we can ignore one or more sides if the movement of the rectangles would never cause the sides to bump onto each other. The sides to be tested always form a pair with leading vs opposing (leading right vs opposing left, leading up vs opposing down and vice versa).


Detecting overlaps

(To simplify things, in the case below only one rectangle moves and the other is still.)

Once you find out all of the sides that are leading and opposing (by checking the signs of each X, Y component of the movement of both rectangles for that frame), you can proceed to use the "linear motion equation" from physics (p = p0 + v . t) to find at what 't' parameter that the sides will be aligned in the axis that they run for.

slide_03.png (17.13 KiB) Viewed 3012 times

The right and left sides of either rectangle run on the Y axis, so align their X coordinates and see if they will overlap on the Y axis. If the sides overlap then there will be a collision, and the moment when it happens will be the value of 't'.

slide_04.png (48.13 KiB) Viewed 3012 times

slide_05.png (26.13 KiB) Viewed 3008 times

slide_06.png (21.83 KiB) Viewed 3008 times

[RNavega]

Huh, I didn't know this before making these images -- to avoid these transparency layering artifacts like on this corner here, on Inkscape you need to group all elements and only then change the transparency for the whole group:

temp.png (19.77 KiB) Viewed 3003 times

[darkfrei]

I remember the tank shadows issue!
https://www.factorio.com/blog/post/fff-56

One of the problems I had when implementing the gates was, that when the shadows overlap, they make ugly "double shadow" areas. This is best visible on the picture of the tank. The turret needs to be drawn separately, as it can rotate independently, the resulting shadow shows the overlap of those two objects.



So I had to make a method, where the shadows of some objects can be drawn separately into one picture as 100% black shapes. Once the shadows are merged in the picture, they are drawn on the screen with 50% transparency and tadaaaa ... all the overlaps are gone.

[RNavega]

I remember the tank shadows issue!
https://www.factorio.com/blog/post/fff-56

I remember seeing that in Super Mario Sunshine too, see how the player shadow darkens the environment shadow:

_.png (2.18 MiB) Viewed 2896 times

The environment has these shadows baked in (the environment lighting in SMS is actualy vertex colors, it's literal geometry cuts onto the environment mesh), and the player shadow would then darken them further -- even though all of these shadows are from sunlight and should be merged together.
For the environment at least, if the player shadow is being projected onto that level mesh, a way to fix that would be to sample those static shadows and the real-time projected shadow in a shader, and then use the color of whichever of the two that's darker for that pixel, like using min() or max() to choose. But that's if they're two texture layers.

In the case of Factorio, from what they're writing in there, the shadows were on two two separate sprites and so they needed to render all the shadows to some framebuffer (canvas), kinda like a stencil buffer collecting all shadows, then overlaying that onto the unshadowed scene, so now it's all done in one pass to darken everything instead of repeated passes doubling the shadows. Very nice.

Edit: this blog post here by Wolfire also talks about double-shadows: http://blog.wolfire.com/2009/11/character-shadows/
The solution was "to subtract the baked shadows from the real-time shadows", whatever that means.

_2.png (736.03 KiB) Viewed 2895 times

[pgimeno]

Your posts have given me an idea to extend my collision library: first you mark multiple objects for movement giving their destination position, then you use a function that moves them all at once. But I'd be using Minkowski difference, which reduces rectangle-rectangle collisions to point-rectangle collisions, making calculations simpler because then you only have to calculate the intersection between a line segment (the point as it moves from its source position to its target position) and a rectangle.

However, I don't have a use for it at the moment, which is why I didn't continue working on it, so it will probably stay in the realm of ideas, at least for a while.

[RNavega]

But I'd be using Minkowski difference, which reduces rectangle-rectangle collisions to point-rectangle collisions, making calculations simpler because then you only have to calculate the intersection between a line segment (the point as it moves from its source position to its target position) and a rectangle.

When I was reading the source to Bump I saw that name, Minkowski sum, I think I read you talking about it in another thread too. It also uses a "Liang-Barsky" intersection between a line (segment) and a rectangle.
I didn't quite get how Bump was doing it, that is, I wasn't being able to geometrically visualize what was going on, so I tried to think of a different way to do it.

Searching for those names now there are two resources explaining their use, and with images. One of them (the first link) even explains it in the context of AABB collision detection, very useful:

• https://emanueleferonato.com/2021/10/21 ... owski-sum/ (by Emanuele Feronato)

• https://twinee.fr/2020-03-24-Liang-Barsky/ (by Alexandre Abraham)

By the way, I didn't go straight to the moving vs moving case at first, as that was too complicated.
First I tried to resolve the same case that Bump does: moving vs static. You can take some shortcuts in this case, like if rectangle A is moving to the left then you don't need to test its right side for collisions.
My find_sweep_collision() function reduces to this for the moving vs static case (note the missing velocity components of rectangle B, as it's now stationary):

(Obsolete code removed, check the OP for the latest and improved version.)

[pgimeno]

By the way, I didn't go straight to the moving vs moving case at first, as that was too complicated.

But can't that be simplified by means of a change of reference frame? When you take an object as reference frame, it is itself static and it's the other one that is moving, hence simplifying the collision type to one between a static and a moving object. Once you resolve the collision, you change the results back to the world's reference frame.

When more than two objects move, you calculate the collisions between each possible pair. The one occurring the earliest is the one to be resolved first, then you (or the user) repeat the operation from the updated positions. Hopefully many checks can be discarded a priori by means of spatial hashing and there won't be many objects at collision distance to check - otherwise you face an O(n²) complexity issue. Let's say it's not for simulating a ball pit but it's suitable for the physics of a platformer or similar.

This comment in your code blew my mind:

Code: Select all

    -- Empirically tested: if the alignment moments are both below t = 0, or if either
    -- of them have t > 1, then a sweeping collision can't happen.

I haven't given any thought to what situation can lead to that, but do you have at least some intuition on why that is?

[RNavega]

But can't that be simplified by means of a change of reference frame? When you take an object as reference frame, it is itself static and it's the other one that is moving, hence simplifying the collision type to one between a static and a moving object. Once you resolve the collision, you change the results back to the world's reference frame.

Oh lol, that simplifies a lot! I ignored that idea early on because I was thinking that the combination of the two moving rectangles would cause a curved trajectory if one was the reference frame. But no, as you said it, it's linear as well.
The change needed is literally this:

Code: Select all

    -- Frame of reference optimization: reimagine the velocity of A
    -- so that the rectangle B is considered as not moving.
    -- This allows finding the moment of collision 't', if any, using the simpler
    -- code for the "moving rectangle vs still rectangle" collision case.
    a_vx = a_vx - b_vx
    a_vy = a_vy - b_vy

...and with that, the reduced function I posted before will work for all three cases (moving/moving, moving/still, still/still), with support for tunneling etc.
I've updated the code in the OP with that, and added your name to the header, I hope that's okay.

Code: Select all

    -- Empirically tested: if the alignment moments are both below t = 0, or if either
    -- of them have t > 1, then a sweeping collision can't happen.

I haven't given any thought to what situation can lead to that, but do you have at least some intuition on why that is?

I don't think I'd be able to prove it mathematically, I'm sure there's some way.
All of this only happens because of the axis-aligned constraint.
I know that it has to do with the "leading line", that is, the line that goes out of the "leading corner" of rectangle A in the direction of movement, with the "leading corner" being the one between the two leading edges of A based on its movement direction.
Rectangle B will have an "opposing corner", formed by the two opposing edges to those of A.

slide_01.png (21.85 KiB) Viewed 2682 times

Imagine that the leading line is infinite and divides the world in two halves. Depending on the side of the leading line where the opposing corner of B lies, only one of the edges of B can be hit by A. On one side it's one edge and on the other side it's the other.

slide_02.png (16.15 KiB) Viewed 2682 times

The opposing edge of B that's a candidate for collision will always project (actually intersect, not project) with the biggest 't' onto that leading line. Since that candidate edge will always have the biggest 't', if any of the two 't' happens to be above 1 then there's no way that a collision can happen.
(I only noticed this thanks to an early demo similar to the OP, where it'd draw a lot of lines and special points etc, similar to these images. I wouldn't have noticed this without it.)