Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm writing a simple non-physical one-circle-to-many-rectangles collision detector/resolver.

For collision detection, I'm using a very common algorithm, and it's working pretty well.

For collision resolving, once a collision is detected, I calculate the penetration vector, and reactively move the circle in the opposite direction. Once again, it is working pretty well.

However, when there are two adjacent colliders, and the circle is moving right in the place where the two colliders meet, the situation is more complex. This is a screenshot of the situation:

Collision

The white rectangles are the rectangle colliders (walls), the yellow circle is the circle collider (player), and the magenta lines are the vectors from the center of the circle to the closest point in each collider.

The problem happens when I get a collision on more than one rectangle. As you can see in the picture above, the top rectangle will have a penetration vector which is not in the direction of the normal of the entire surface, and as such will create artifacts as the circle slides through the wall, depending on how I handle it.

There are many solutions I have tried, but they all create artifacts. In particular, using any algorithm to pick only one collision and solving only for that one, may yield different solutions depending on the order in which they are evaluated, especially on cases where both collisions must clearly be chosen, like the following one:

Naughty collision

Just for reference, these diagrams are meant to show a top-down, not a side view of the playing field.

Is there a known way to resolve such a collision correctly?

share|improve this question
    
In your example image, why diagonal vector used to compensate penetration? It is directed towards non-colliding rectangle. This is rather confusing. Can you show example with 2 actual collisions? And perhaps with good zoom. And ideally also with mentioned artifact. –  Shadows In Rain Jul 7 at 10:12
    
@ShadowsInRain: As I said, "the magenta lines are the vectors from the center of the circle to the closest point in each collider". When there is only one rectangle and the collision is with its corner, the vector will be diagonal. Artifacts related to incorrect resolutions are not visible but felt as a bump in the place where the rectangles meet, and therefore cannot be meaningfully shown with an image –  Panda Pajama Jul 7 at 10:16
    
@ShadowsInRain: I only take a vector into consideration for collision resolving, when its magnitude is smaller than the circle's radius (i.e. when there -is- a collision). Right where the rectangles meet, it is possible for the circle to have penetrated both rectangles, and I should consider both penetration vectors to resolve the collision, but I do not know how –  Panda Pajama Jul 7 at 10:21
    
Now this is clear. As answer already suggested, you may try to handle first collision only, and then re-detect colliding pairs again. I would recommend picking collision with shortest penetration vector (closest object). And of course you need to limit number of restarts, otherwise stuck object will hang you collision routine. –  Shadows In Rain Jul 7 at 10:30
    
@ShadowsInRain: Arbitrarily choosing one is not correct. Also choosing the smallest one is not correct. If my choice is the top (diagonal) collision, which is most likely the shortest one, as the circle moves up, it will get pushed down, and it should only be pushed outside. –  Panda Pajama Jul 7 at 10:34

2 Answers 2

up vote 3 down vote accepted

Figuring out the correct solution to multiple collisions between overlapping (or perfectly aligned rectangles) is not trivial, and most solutions will have problems. I'm not even sure if there is an actual correct solution.

Reading this question made me think that the problem could be solved by not letting the problem exist in the first place! "The problem" being "two parallel overlapping collisions occur at the same time".

It turns out that a line segment is a special case of a rectangle, whose width happens to be 0. This means that if I have a rectangle collider, I also get a line segment collider for free (certainly, a collider optimized for line segments can be written too)

So instead of modeling the colliders as two almost overlapping rectangles, I model it as six line segments, where this problem does not even exist!

Solved out of the box!

With line segment colliders, I also get arbitrary polygon collisions for free!

For non-overlapping rectangles, as in the second image in my question, my current solver, which iteratively calculates weighted averages of all the collisions works just fine.

share|improve this answer

I admit I've never successfully written a collision resolver, but I have a suggestion.

Your problem is that you have two valid contacts that resolve a collision between the circle and a rectangle. On their own, each contact will solve the collision, but when there are two contact occurring in the same cycle you will have to pick one. You can't apply both because that would result in the circle popping away from the surface, and picking one arbitrarily (such as the first contact to be processed) will give unexpected results.

In this situation, one of the contact vectors will remove the circle from both rectangles while the other will not. The corner contact will push the circle out of the top rectangle but will leave a small overlap with the bottom rectangle.

What you need is a contact selection / combination system. The only idea that comes to mind would be to try each contact resolution and re-check with the objects that were collided with. If one of the contacts solves the collision better than the other, then you use that contact.

I can also imagine, if for example the circle was crushed between two rectangles, that the best resolution would be to somehow combine the two vectors by weighting them relative to their penetration distance. This would most likely apply when more than one contact ties for solving the problem. That is, if the first contact resolves collision on one object but continues collision with the other object and the second contact does the opposite, you can see that both contacts leave one collision and thus tie for first place.

These are just my thoughts, there may be articles that have better solutions but I figured I'd try to help.

share|improve this answer
    
It sounds good to try to use only one contact to resolve the collision instead of trying to combine all of them. However, if I moved the upper rectangle in the screenshot just a tiny bit upwards, I guess I would have to consider both vectors, wouldn't I? –  Panda Pajama Jul 7 at 10:24
    
I think that actually falls under the two contacts tie for first scenario. Both contacts would most likely resolve the collision with both rectangles, so you would then combine them relative to their penetration distance. –  mortusnegati Jul 7 at 10:28
    
@PandaPajama I think if we are modeling infinitely solid objects, double collision like this is impossible, because given edges are colinear and not intersecting, so it is not possible to touch both of them with circle. Thus it makes sense to solve only one collision, then check again. –  Shadows In Rain Jul 7 at 10:36
    
Actually considering it a bit more, I don't think you average when two contacts tie, you might add. For example if two overlapping rectangles form a corner and your circle is moving diagonally into that corner. Which is an example of a situation in which two collisions are possible at the same time with infinitely solid objects. Though I would argue that this is a simulation so you have to solve problems that don't happen in reality. –  mortusnegati Jul 7 at 10:37
1  
In this collision, where the circle is trying to move to the left, the order in which the collisions are resolved will most likely yield different solutions. –  Panda Pajama Jul 7 at 10:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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