Which axis-aligned line does an AABB collide with first?

Question

I am making the collision resolution system for my 2d top-down game, and I managed to find a solution where I query which surfaces of other AABBs the current entity can collide with in the next frame.

To resolve the new location of the player however, I need to find which surface the entity collides with first.

I have a list of lines, which is LinkedList<int[4]> collidedLines. a line is {x1,y1,x2,y1}, however in this case, they are axis-aligned, so either x1==x2 or y1==y2.

I also have the entity, which has the following properties:

int posX
int posY
int speedX  // The amount to move in the
int speedY  // next step of the game.
int size  // The halfwidth of the square AABB.

How can I find the first line the entity collides with? Thanks for your help!

Answer 1

You can also achieve this with the following steps:

• 1/ Find the intersection points between the infinite lines passing though the four sides of the AABB and the infinite line passing through the entity position (pre-collision) which use the entity speed vector as slop. (You can either find a collision point or an undefined number, which corresponds to parallels or overlapping lines)

• 2/ Once you know the intersection points (if they exist) you can search for those that are into the segment bounds.

• 3/ Finally, if there is still multiple points on the list (the velocity vector can pass through multiple sides), you can search for the closest point from the entity origin using the magnitudes of the vector from the intersection to the entity origin.

---

More details:

• 1/ Find intersections

  • a / Determine the implicit lines ( Ax + Bx = D ) using their parametric forms ( P(t) = Po + tD ).

    Point origin: Po = [posX, posY]
    Direction vector: D = [speedX, speedY]
    
    A = D.y = speedY
    B = -D.x = -speedX
    D = (Po.x * D.y) - (Po.y * D.x) = (posX*speedY) - (posY*speedX)
    
    Ax + By = D <====> (speedY*x) + (-speedX*y) = (posX*speedY) - (posY*speedX)

    I used the entity point values to illustrate the method, but this is exactly the same method to determine the 4 side implicit lines (Use Po = [x1,y1] and D = [ x2-x1 ; y2-y1 ] instead).

  • b / Next, to find the intersection of two implicit lines we can solve the following system:

    A1x + B1x = D1 <== Line passing through the entity point with the speed vector as slop.
    A2x + B2x = D2 <== One of the lines passing through the AABB sides.

    which yields the following coordinates for the interception:

    Interception x = ((B2*D1) - (B1*D2)) / ((A1*B2) - (A2*B1))
    Interception y = ((A1*D2) - (A2*D1)) / ((A1*B2) - (A2*B1))

    If the denominator ((A1*B2) - (A2*B1)) equals zero, then the both lines are parallels or overlapping, otherwise you should find an intersection.

• 2/ Test for the segment bounds. As this is straightforward to verify, there is no needs for more details.

• 3/ Search for the closest point. If there is still multiple points on the list, we can find which side is the closest to the entity origin point.

  • a / Determine the vector going from the intersection point to the entity origin point

    V = Po - Int = [Po.x - Int.x ; Po.y - Int.y ]

  • b / Compute the vector magnitude

    ||V|| = sqrt( V.x² + V.y² )

  • c / find the smallest one.

---

Note: this is probably not the most efficient way to do it, but as it still can helps some people i think it worth to be added.

Answer 2

Since all the collision objects in your universe are axis-aligned, it might be easier to have separate lists of vertical lines and horizontal lines. And keep both lists sorted. Then it's relatively straightforward to figure out the first horizontal line that the actor actually hits; similarly for the first vertical line, and then all you have to worry about is which one of these two is actually first.