Arbitrary Rectangle Collision Detection & Resolution - Complete!

In this video I once and for all solve axis aligned rectangle collision detection, demonstrating algorithms to handle arbitrary size rectangle vs rectangle collisions and collision resolution, applicable to "rectangle soups" or tile map based interactions.

[MichaelRichardson-bwxh]

**looks at title** this will be good
**looks at duration** this will be GREAT

[Tsanislav]

188 Times or 3.4 rectangles per minute

[thevexxedcoder]

Drinking game : drink whenever Javid says rectangle.

[saantonandre]

Hi! I've found a logic bug in the "bonus side effect" you mention at 42:50

It's correct that you don't alter the velocity in the opposing axis of the one you collided with, BUT here you are altering the velocities direction!!! And if in that direction there are colliders you have excluded out (not resolving because they werent in your direction before) you are gonna clip with/ totally miss them in case of diagonal collisions with a close rectangle.

Thanks a lot for your tutorial, I managed to code my own javascript implementation of your code, and my (really) ugly fix was to run the whole collision check recursively when all these conditions are met:
-the object was initially moving in BOTH axes
-at least one collision resolve happened

This means it can run up to 3 times (per frame) when close to corners in a diagonal vel direction:
First time: resolves the direction to not meet one of the axes of hypotetical corner
Second time: meets the other axis of the corner, resolves
Third time: still in a diagonal velocity towards corner, but since both velocities have been cut by previous adjustments, no collision is found at broad phase.

There are many more efficient ways than mine to resolve this slide-clip behaviour, but I think I made a point:
if you change the direction, expect eventual colliders which were still part of the group of the first broad phase cut (when you add the initial velocities to your size and simple check with everything), but were cutted out from resolving because they werent in your direction during line vs rect.

Had to debug running the game loop at 2 fps to follow up what was going on with the diagonal collision at moderate/high speed and isolate the bug to get a grip of the occasional clipping.

[Selexo]

So this is how the old Super Mario speed runs happen. When they get so good they frame-time, clip, and run through solid objects. So cool. Awesome tutorial, and it's practical for every engine.

[OllAxe]

This is a fantastic video! Thank you so much for it!

Something I'd like to add is that, if you want to convert the DynamicRectVsRect to a DynamicRectVsDynamicRect you can simply take the velocity of the second rectangle and subtract it from the first one, then use that difference as the direction vector of the ray in the collision detection. Properly solving dynamic collisions however would require some soft of recursive algorithm to get it to work between more than two rectangles at a time, to solve each collision in the order in which they occur.

Edit: Having now implemented the code demonstrated in this video, it works quite well, though I did stumble upon a couple of small issues that I managed to fix.

First of all, tNear can sometimes become way less than 0 when moving slowly in the opposite direction due to floating point errors, in which case the player (or any object using this same collision check, I'll just say 'player' from now on for simplicity) can be snapped backwards through a wall. The solution is to say it's not a collision if tNear is less than 0, or in reality less than a small negative value, otherwise we get more floating point errors that cause some collisions to get missed instead. Ugh, floating point numbers...

The second thing is the fact that the literal edge case of colliding into a corner is not handled in your code, meaning it's possible to clip through walls when you hit a corner. In your implementation, this is masked not only by the fact that it's a rare occurance but also by the fact that tNear is allowed to be negative, so if the player clips into a wall one frame then they're likely to be clipped back out the next. However, that's not the case if you don't count negative tNear values as collisions. In that case you need to handle corner collisions, -otherwise the player will be able to wall clip- (edit: I realized it wouldn't enable them to wall clip, just that the normals wouldn't be handled correctly). You could choose to make it collide in both axes if you collide with a corner depending on what you're doing, but in my case since I'm making a platformer that would just make the player get stuck on corners momentarily in case such a collision occurs, so I've chosen to handle it as vertical collision in my implementation which works better for that use case.

Sorry for the huge wall of text. And again, huge thank you for making this video! It's great to finally be able to escape Unity's own collision system for simple 2D games.

[zerdagdir]

I would normally find hi and hello boring and bland. But this man says it so simple yet so enjoyable

[detri-codes]

I deleted my old comments because I finally figured out everything I was doing wrong. This video helped me figure out my AABB collisions, thank you so much!

[predikit]

Brings a whole new meaning to the phrase "GetRect()"

[jestarray]

TIMESTAMPS:
03:14 PointVsRect
06:19 RectVsRect
08:25 Tile Based Collision review
12:10 Tile based limitations
14:45 Tunneling
16:05 Swept AABB Intro
16:40 RayVsRect
18:40 Find t in RayVsRect
20:00 Finding near&far x&y
21:28 Sorting multiple ray hits
27:20 RayVsRect Code
33:33 Swept AABB theory
35:33 DynamicRectVsRect moving
37:40 Multiple Rectangle tests
39:39 Testing Collision and Seperation
40:48 Collision Resolution
43:45 Playing around with more rects
44:35 Sliding bug
48:28 Broadphase naive sort
50:30 Mouse release snag bug

[cotty]

Honestly, thank you very much for all of the effort you put into your videos. I can't stress how valuable and amazing your content are. From the bottom of my heart, thank you! thank you! thank

[poopingnuts]

what a coincidence. I was just literally programming collision methods for my project and you uploaded this video.

[jsflood]

Wow. Got some answers to questions I did not knew I had. Great video. Thank you!

[ecupak]

Thank you so much for making this video! I'm working on my first project of the year at uni and implemented your system. I was struggling with all the issues you listed in the beginning too, so it was great to see you also cover them.

[wikedawsom]

I've been working on a game, and I was looking for a good way to detect and found my way to the case where the object is moving too fast. The vector intersection projection is exactly what I need, and you are a saint for making it so digestible.

[bzen]

The fun thing is, the swept AABB collision can be extended quite easily (well, more maths, but same vector artihmetics) to any convex polygon vs convex polygon collisions, no matter the orientation. Then you can add spheres into the mix, or more complex convex geometry (capsules, ect).
If you want slopes, roughly shaped terrain, triangles, it's a great way to do it.
Technically, it's all based on the the SAT (separating axis theorem), the case between two AABBs is just a special case of the more general algorithm. Similarly, the 2D case is a special case of the 3D algorithm, so extended to 3D is also trivial, you just have many more 'axes of overlap' to check (face normals, and edge cross products).

And if you want to deal with intersections, you can also use the same SAT checks for free to work out the potential intersection vectors (the vector you need to use to push the objects away from each other a minimum amount to resolve an intersection), like you did at the start with the 'non-swept' intersection detection.

What I find hard, is the problem you highlighted, resolving for the best response when you encounter multiple simultaneous collisions and intersections. Algorithmically that's can get real ugly real fast, which means, nasty unpredictable bugs and weird behaviours.

[luizpestana]

3 years and still very useful, thanks!

[teucay]

It always amaze me how much I can learn about a topic I thought had no more complexity. You are great!

[DMSG]

I like your videos. Always interesting topics.
I implemented it in Java and learnt a lot.
However, I found a bug that drove me nuts. In principle, it worked, but sometimes my rectangle would jump around.
E.g. my rect touches the horizontal border of the other rect then in some cases, the program would reposition my rect to horizontally align with the left border and then the right border of the other rect in quick successions, even though they are totally irrelevant at this point.
Turns out, the algorithm got tripped up by a *𝙽𝚘𝚝-𝚊-𝙽𝚞𝚖𝚋𝚎𝚛* value, e.g. in case *( 𝚛𝚎𝚌𝚝.𝚢 + 𝚛𝚎𝚌𝚝.𝚑 - 𝚙𝚘𝚒𝚗𝚝.𝚢 ) == 𝟶* and *𝚟𝚢 == 𝟶* then *𝚝_𝚏𝚊𝚛_𝚢* would be zero divided by zero, and we get *𝙽𝚘𝚝-𝚊-𝙽𝚞𝚖𝚋𝚎𝚛* instead, because the computer cannot determine the sign. I needed to handle that manually:
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 - 𝚙𝚡) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚡 = 𝚟𝚡 != 𝟶 ? ( 𝚡 + 𝚠 - 𝚙𝚡 ) / 𝚟𝚡 : ( 𝚡 + 𝚠 - 𝚙𝚡) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚗𝚎𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 - 𝚙𝚢) >= 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;
𝚏𝚕𝚘𝚊𝚝 𝚝_𝚏𝚊𝚛_𝚢 = 𝚟𝚢 != 𝟶 ? ( 𝚢 + 𝚑 - 𝚙𝚢 ) / 𝚟𝚢 : ( 𝚢 + 𝚑 - 𝚙𝚢) > 𝟶 ? 𝙵𝚕𝚘𝚊𝚝.𝙿𝙾𝚂𝙸𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈 : 𝙵𝚕𝚘𝚊𝚝.𝙽𝙴𝙶𝙰𝚃𝙸𝚅𝙴_𝙸𝙽𝙵𝙸𝙽𝙸𝚃𝚈;

[GuilhermeTeres]

Me seeing this vídeo late in thr night: Oh, it's an hour long and I'm falling asleep, no way that I'll watch it today...

Me an hour in later: Oh... that's so good!