Collision response with AABBs

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
User avatar
cdArf
Prole
Posts: 6
Joined: Sun Dec 25, 2016 12:28 am

Collision response with AABBs

Post by cdArf » Mon May 08, 2017 8:46 pm

I'm making a basic library for myself for easier use of AABBs in my games. Right now, I've implemented placing AABBs in the world grid, and the ability for AABBs to get all others inside of it.
However, I''ve been pulling my hair out about collision response. It should be the easiest part, but all solutions I've tried glitch out and bug positions, so I don't really know what to do at this point.
Also, there's no velocity here, so I can't just manipulate that.

User avatar
airstruck
Party member
Posts: 650
Joined: Thu Jun 04, 2015 7:11 pm
Location: Not being time thief.

Re: Collision response with AABBs

Post by airstruck » Mon May 08, 2017 9:33 pm

No velocity means things aren't moving, doesn't it? If things aren't moving, how can they collide?

Not clear what kind of response you're looking for here, did you mean to ask a question?

User avatar
cdArf
Prole
Posts: 6
Joined: Sun Dec 25, 2016 12:28 am

Re: Collision response with AABBs

Post by cdArf » Tue May 09, 2017 7:31 am

Things are moving, but there isn't any explicit velocity values here. Just actually changing positions, and testing for collision there. Think bump.lua.
Given that, if A is intersecting B in the bottom and right sides, how do I separate A and B?

User avatar
zorg
Party member
Posts: 3044
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: Collision response with AABBs

Post by zorg » Tue May 09, 2017 9:55 am

If there are no displacement values, how can you tell how much to change the position? (Yes, i'm being deliberately dense.)
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.

User avatar
cdArf
Prole
Posts: 6
Joined: Sun Dec 25, 2016 12:28 am

Re: Collision response with AABBs

Post by cdArf » Tue May 09, 2017 10:08 am

What I want to do is to displace you depending on what side the collider was "hit". So if it was on the right side, displace by other collider's left side, if on the bottom, displace by the other collider's top, etc.
I can already get what side it was "hit" on, so that it isn't the issue.
The issue is that it wants to displace on both axes, so there's conflict in between the displacements, and it ends up on a corner.
It isn't my displacement calculations either, if I turn off displacement on one axis but not the other, it works for that axis perfectly.
Clearly, this is a naive approach to it, so I'm looking for a solution, or new method entirely, to try to fix this.

User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Collision response with AABBs

Post by kikito » Tue May 09, 2017 11:00 am

I can tell you how it's done in bump. It doesn't use the velocity vector itself, but it "remembers the previous positions of all items" before moving them. So it can use the "vector from the previous position to the one in the current frame". That is the same has having velocity, just expressed in another way (you have the direction, the space, and the time it'll take to move there).

In order to solve the problem of "corners cases" what I did was transforming the problem into a simpler one: instead of colliding two aabbs, I collapsed one of the boxes (the "moving" one) so it became a point. And conversely, I made the other box "bigger". This is called the Minkowsky Difference, and is explained in detail on this article: Collision Detection for Dummies. If you play with the widgets there, you will notice a very interesting fact about the Minkowsky difference: the MD of two AABBs is always another AABB. Which is easy and fast to calculate.

Once I had collapsed one box to a dot and made the other bigger, the problem becomes intersecting one "moving dot" (which is the same as a segment) with a box. That is a solved problem, there are several algorithms. I used a modified version of the liang-barsky one. Once I got the points in which the "dot" collided with the "expanded box" I could "undo the transformations" to get the exact points in which the collision occurs with the original two boxes.

All this is by no means straight forward and there are still corner cases to take care of (for example: what happens if two boxes are already intersecting and one of them starts moving?). I spent several months just fighting the corner cases until this was more or less functional. And I still got bug reports years later, because I had not made the algorithm tolerant enough for floating point, or I had missed this or that corner case.

And I have not even talked about how to make collision responses when both boxes are static. What direction should they move, and how? Which one should move?

With all this I just want to say that the problem you have chosen to solve is not as easy as it might seem. It's doable, but I don't think it can be solved in a couple evenings. Not if you want to make it work with a variable dt and floats everywhere.

If you are wondering how they did it in the old days, they relied heavily on the fact that their frame time was fixed (they didn't have dt like LÖVE does, all frames where assumed to be fixed - 30ms or whatever) and they didn't have floats, but integers. Once you take those two out, you don't even need AABBs. You can use "magic points" - one point at your character's feet is all you check for colliding with the ground. Another point to its left for left walls, and the same to the right, and on their "head". This is fast and easy to implement. But you don't get subpixel movement, and become tied to a 30ms/60ms clock. If you want to know more about this, here's a great article about how MC Kids was implemented.
When I write def I mean function.

User avatar
cdArf
Prole
Posts: 6
Joined: Sun Dec 25, 2016 12:28 am

Re: Collision response with AABBs

Post by cdArf » Tue May 09, 2017 11:49 am

Woah, thank you. It seems like I've dug myself into a pit. I didn't quite realize how elaborate this could get, but it seems like I had at least try.
This is some interesting stuff, and I'll be reading both articles you've linked. Definitely a head start, I'd say.
Thank you again! Have a good day.

User avatar
peterrust
Prole
Posts: 42
Joined: Thu Dec 29, 2016 8:49 pm
Location: Bellingham, WA, USA
Contact:

Re: Collision response with AABBs

Post by peterrust » Sat May 13, 2017 4:48 am

kikito wrote:
Tue May 09, 2017 11:00 am
This is called the Minkowsky Difference, and is explained in detail on this article: Collision Detection for Dummies

...

they relied heavily on the fact that their frame time was fixed and they didn't have floats, but integers
Wow. kikito, thank you so much for your contributions to the LOVE community, this is great stuff! I've been using bump, but didn't realize the math behind it was so complex.

User avatar
ivan
Party member
Posts: 1664
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Collision response with AABBs

Post by ivan » Sat May 13, 2017 11:11 am

I''ve been pulling my hair out about collision response. It should be the easiest part
It's one of the hardest parts!
cdArf wrote:
Tue May 09, 2017 7:31 am
Given that, if A is intersecting B in the bottom and right sides, how do I separate A and B?
It depends on the type of the collision system.
Discrete collisions: you always choose the shorter axis and use that to separate the two AABBs. Works good enough for most games as long as your objects don't move super fast.
Continuous collisions: you have to take the velocity into account so it's a little more complicated, as kikito explained.

User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Collision response with AABBs

Post by kikito » Sun May 14, 2017 2:02 pm

peterrust wrote:
Sat May 13, 2017 4:48 am
Wow. kikito, thank you so much for your contributions to the LOVE community, this is great stuff! I've been using bump, but didn't realize the math behind it was so complex.
Just one clarification here. The math behind bump isn't complex. I know some math, but it is not my strong suit. Math experts will probably laugh at how basic bump is, math-wise.

The real hurdle is that we humans have specialised parts in our brain which deal with throwing things, seeing things bounce, and the like. Any deviation from that and we immediately see that it is "wrong". And there are lots of ways things can be mathematically "correct", but "feel wrong". Getting those little details right is what's difficult. But it's not complex, it's just ... incredibly tedious :nyu:
When I write def I mean function.

Post Reply

Who is online

Users browsing this forum: No registered users and 57 guests