Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this community
I am currently trying to resolve collision between two AABBs. I already have a function that can detect if the the two boxes are colliding and returns true if the two boxes are colliding.
The problem is that I do not know what to do next. All I want to do is make sure the boxes do not penetrate each other. Where do I start?
I am really confused about how to start and any help would be great. I also cannot use any libraries as this is an assignment
There are continuous and discrete physics/mechanics. I do not know which one you are doing. Their main difference is in the detection, which you already have done. Thus, I will skip finding candidate pairs, and skim over the detection process, and then explain the response part.
With that said, the response has two parts:
And resolving collisions in the same thing, regardless of the approach.
Addenum: I will be explaining this for 2D... for 3D replace in your mind "segment" with "plane" and remember there is one more axis (thus, when I mention vertical and horizontal, there is also ern... one more). It is the same deal.
For abstract these are the two approaches:
Continuous mechanics will try to collide the area that the objects traversed between updates. It can have false positives in the detection, thus we will be doing a double check after finding the collision instant.
Discrete mechanics will collide the objects a fixed number of intervals along their path (once or more per update). It can have false negatives (tunneling). I will explain the bulk of the process it in the continuous approach, and then what are the variation for the discrete one.
Both can be done with AABB. And as I said above, resolving the collision is the same thing in both cases.
Detection
For both objects the candidate pair, get the smaller AABB that contains both the start and end position of the object. Collide those. If the AABB overlap, it means we have a possible collision (we still need to make sure, thus, we will double check on the resolve part).
Finding the collision instant
Consider the AABB of each object at the previous update. Consider each one of the four line segments that form it. Consider that those line segments moved according to the speed of the object from the last update to the current one.
We need to find at what instant one the segments of the first object passed over one of the segments of the second object. We only need to consider vertical segments against vertical segments, and horizontal segments against horizontal segments.
Furthermore, we only need to consider one horizontal segment and one vertical segment of each object.
To figure out which… for the first object: take the difference of the movement speed of the first object minus the movement speed of the second object. If the difference is positive on the x axis, you want the segment with higher value on the x axis, similarly for the y axis. For the second object, flip the operation.
Now, on the x axis, we need to solve a_x + (a_speed_x * time) = b_x + (b_speed_x * time):
a_x + (a_speed_x * time) = b_x + (b_speed_x * time)
(a_speed_x * time) = b_x – a_x + (b_speed_x * time)
(a_speed_x * time) – (b_speed_x * time) = b_x – a_x
(a_speed_x – b_speed_x) * time = b_x – a_x
time = (b_x – a_x) / (a_speed_x – b_speed_x)
The same deal for the y axis.
We now have two instants at which the objects are meant to collide. Discard any negative ones, discard any time bigger than the time from the last update. We pick the smaller one.
We can now compute the position of the objects that time.
Note: If we are working in the continuous approach, we want to verify if it was indeed a collision. W do this by checking the collided segment along the other axis. In the continuous approach we can find false positives in the detection (these are near misses), and we should discard them at this step. Errata: do not discard the candidate pair, discard the collision time, if there are multiple possible instants at witch the collision could have occured, try each one.
Detection
If you are following the discrete approach, you collide the AABBs at least at their final position. You may also want to collide them at intervals from the last update. This is useful to prevent objects tunneling through each other (those are false negatives, a problem that the continuous approach does not have).
Thus, you will be checking the objects for collision once or more times in the interval of time from the last update. How many to do? Perhaps your game does not need too much precision on the collision, perhaps it runs on slow hardware and is better off fudging a little… or a lot, test.
There is an opportunity for optimization here: you can do a detection as the one described in the continuous approach, and then only check at intervals if that collision is positive.
Finding the collision instant
This is the same deal as in the continuous approach. Except, remember that if you are doing multiple checks, you need to add the time of the check to the time you get from that computation.
Here you have another thing to tweak for performance… if you are doing many discrete tests, then the interval between them is small. If it is small enough, you may skip computing the collision instant as I describe it for the continuous approach and just use the time of the first check that yielded positive. This means more iterations but simpler code. This is optimization is not appropriate for every game and every platform, test.
I remind you that I described the computation in terms of the starting position. It also possible to work with the final position and compute how much time ago the collision happened. It leave this for you to figure out, if you want to try it.
The simplest form of resolution is to simply put the objects at the position we found. This is enough to prevent them to appear overlapped.
However, just doing that will mean that is some lost time. For instance, if the update took 16 milliseconds, but we find that they objects collided at 10 milliseconds from the last update, we have lost 6 milliseconds worth of simulation.
We can simulate that remaining time, for instance, if the objects are meant to bounce, we can flip the speeds along the colliding axis and compute where the objects end up after the remaining time.
Note on constraints
Resolution can be more complex if we have to deal with complex constraints or degrees of freedom. Collisions and unmovable objects are just the simplest constraints. You could, for example, have objects that must remain at a given distance from another. What you do, is check if the constraint is violated, find out when, and then from that point figure out what should happen that respects the constraint.
It is also possible that as a result you find a situation that violates another constraint. For example, you bounce the object, and the resulting path makes it collide with another object on the same update. You can then repeat the process for the other constraint.
Eventually, the system would find a solution that satisfies all the constraints… but we do not have “eventually”, the update should be fast as to not stagger the game, thus, you probably want to set a maximum number of resolutions you do… it can be just one, and it can be simply placing the objects at the last position that violates no constraints, and you may be able to life with the simulation losing a few milliseconds here and there… how many to do? Test.
