2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Hello, welcomte to the site, please take our tour. \$\endgroup\$ – Theraot Oct 24 '18 at 10:59
5
\$\begingroup\$

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:

  • Find the collision instant
  • Resolve the collision

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.


Continuous

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.


Discrete

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.


Resolution

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.