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.
Collision response with AABBs
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
Re: Collision response with AABBs
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?
Not clear what kind of response you're looking for here, did you mean to ask a question?
Re: Collision response with AABBs
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?
Given that, if A is intersecting B in the bottom and right sides, how do I separate A and B?
-
zorg
- Party member
- Posts: 3465
- Joined: Thu Dec 13, 2012 2:55 pm
- Location: Absurdistan, Hungary
- Contact:
Re: Collision response with AABBs
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 
True 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.
True 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.Re: Collision response with AABBs
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.
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.
-
kikito
- Inner party member
- Posts: 3153
- Joined: Sat Oct 03, 2009 5:22 pm
- Location: Madrid, Spain
- Contact:
Re: Collision response with AABBs
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.
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.
Re: Collision response with AABBs
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.
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.
Re: Collision response with AABBs
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.kikito wrote: ↑Tue May 09, 2017 11:00 amThis 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
Re: Collision response with AABBs
It's one of the hardest parts!I''ve been pulling my hair out about collision response. It should be the easiest part
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.
-
kikito
- Inner party member
- Posts: 3153
- Joined: Sat Oct 03, 2009 5:22 pm
- Location: Madrid, Spain
- Contact:
Re: Collision response with AABBs
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
When I write def I mean function.
Who is online
Users browsing this forum: Amazon [Bot], Bing [Bot], slime and 2 guests