• Advertisement
Sign in to follow this  

Handling collisions with multiple bodies and unwanted collision with internal edges

This topic is 1084 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello. I am trying to implement my collision engine for a 2d platformer. I want it to support vector geometry, such as polygons and slopes of different angles and shapes. For a pair of two polygons i use Separating axis theorem to find the minimum translation vector that is needed to be added to the body position to separate them. However, i've ran into following problems:

At first, i dont know how to handle collisions with multiple bodies. If i translete the moving body by every minimum translation vector i found by colliding it with each static polygon, the total translation result may appear to be too long or too short.

 

The second problem appears in some situations when i alter the velocity of the moving body accordingly to the collision data. For example, in such situations, as shown in the picture below.

GYQnORE.png

The body (blue rectangle) is moving with velocity V and penertates into a wall composed out of two red rectangles. While processing collision with the leftmost red rectangle, the normal is found by smallest penetration axis, it points up. I subtract the normal, multipled by the dot product of normal end velocity, from the body velocity vector. This is OK. However, in the case of rightmost red rectangle, the horisontal penetration (X) appears to be smaller than vertical penetration (Y) and the collision normal is considered to be horisontal. It makes the body to stop, while it had to slide along the wall.

 

I found several solutions to this problem, such as:

- Make the world out of line segment loops without inner edges.

- Make the corners of the moving bodies, static obstacles or both, smooth and round.

 

I also tried continuous collision detection, but ran into a similar problem where bodies were colliding with the corners of static obstacles.

 

Although i can solve this problem by rounding the moving shapes, i still wonder how the similar problem is solved in modern 3D physics engines and other 2D games.

 

I also still dont know, how to move the body out to solve its penetration into multiple obstacles.

 

Thank you if you can help.

Share this post


Link to post
Share on other sites
Advertisement

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

Edited by PunCrathod

Share this post


Link to post
Share on other sites

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

Calculating how far to push body along its velocity is not that simple, as finding its minimal separation vector, but is almost the same as finding exact collision time in continuous collision algorithm. As i already said, continuos collisions involve more problems like corner-corner collisions, which i also dont know how to solve.

Your second advice, probably, will not work correct in any collision conditions. For example, it would work very ugly, if there was no left red rectangle and the blue one penetrated more on vertical axis. Also notice, that if there was no right red rectangle, resolving the collision on the horisontal axis would be fine. So, i think, i must somehow consider all the collisions at one time, but must not resolve them pairwise.

Edited by neonsoup

Share this post


Link to post
Share on other sites

Maybe i should use a completely different collision resolving approach, but i know only those two (continuos collison and penetration - based). Maybe i also could use continuous collision with kind of fix for corner-corner collisions. I dont know how to fix it.

Edited by neonsoup

Share this post


Link to post
Share on other sites

 

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

Calculating how far to push body along its velocity is not that simple, as finding its minimal separation vector, but is almost the same as finding exact collision time in continuous collision algorithm. As i already said, continuos collisions involve more problems like corner-corner collisions, which i also dont know how to solve.

It is relativily simple. Just rotate both velocity and surfacepenetration the same amount so that the surface vector is upright(x==0). Then multiply the original velocity vector by vel.y/surface.y and thats it. I assume you already have the distance blue has penetrated along the surface normal. And you may need to use vel.y/-surface.y if your surfacepenetration vector goes from surface to inside instead of from inside to surface. Also if you store the percentages of velocity used(the vel.y/surface.y part) you can then after the last collision has been processed move the character again by velocity*(-sumofstoredvalues) as to make it move more physically accurately.

 

As for the second approach. It is actually quite common in platformers as it makes characters able to climb stairs and slopes and run over small gaps without having to make complicated code to detect those special cases.

Share this post


Link to post
Share on other sites

 

 

You could try to just move the blue backwards along its velocity until it no longer collides with anything like you are doing now but only alter the blue velocity in the last collision. you also could define a minimum Y penetration(could even be a variable inside blue) so that if the Y penetration is smaller than that then even if X penetration is smaller than Y you still take the Y one. You should get pretty satisfactory results if you do both of these.

Calculating how far to push body along its velocity is not that simple, as finding its minimal separation vector, but is almost the same as finding exact collision time in continuous collision algorithm. As i already said, continuos collisions involve more problems like corner-corner collisions, which i also dont know how to solve.

It is relativily simple. Just rotate both velocity and surfacepenetration the same amount so that the surface vector is upright(x==0). Then multiply the original velocity vector by vel.y/surface.y and thats it. I assume you already have the distance blue has penetrated along the surface normal. And you may need to use vel.y/-surface.y if your surfacepenetration vector goes from surface to inside instead of from inside to surface. Also if you store the percentages of velocity used(the vel.y/surface.y part) you can then after the last collision has been processed move the character again by velocity*(-sumofstoredvalues) as to make it move more physically accurately.

 

As for the second approach. It is actually quite common in platformers as it makes characters able to climb stairs and slopes and run over small gaps without having to make complicated code to detect those special cases.

 

I cant understand properly your solution. Could you explain it better or give a pseudocode example, please? Also, notice that im using different polygons in my engine, not only AABBs.

Share this post


Link to post
Share on other sites

I cant understand properly your solution. Could you explain it better or give a pseudocode example, please? Also, notice that im using different polygons in my engine, not only AABBs.

 

 

Ok let me try.

All of this should work with any size and shape polygons and the image has axis aligned rectangles only because I was using mspaint.

[attachment=26235:figurea.png]

First we need to find a corner from blue polygon that is inside red polygon and call it corner A. Then find the surface in red wich is the closest one to corner A that is between corner A and an adjacent corner from blue and call it surface B.

In order to move the blue outside of the red polygon we need a vector from corner A to surface B and call it surfacepenetration.

Then we calculate the angle between surfacepenetration and a vector(0,1) and call it surfacenormalrotation.

Then make a new vector called rotatedvelocity by copying and rotating the original velocity by surfacenormalrotation.

Now we take the length of surfacepenetration  and divide it by the Y component of rotatedvelocity.

This gives us a float t between 0 and 1. This is the precentage of velocity you need to move blue one backwards to make corner A be outside of red polygon.

 

Here is a pseudocode for the moving blue backwards part.

float angle=findangle(surfacepenetration,upvector)
vector2d rotatedvelocity=blue.velocity.copy
rotatevector(rotatedvelocity,angle)
float t=abs(surfacepenetration.length/rotatedvelocity.y)
blue.pos-=blue.velocity*t

.

 

When we enter the collision handling we repeat this until blue is not inside any red polygons. Then we process what happens to blue based only on the last collision that was detected this way as that is collision would have happened first if your simulation steps were small enough. In your first example picture it would always be the collision with the left red rectangle and the blue stops because of hitting the right red rectangle horizontally never happens.

 

Also if we store the percentages of velocity we moved blue backwards we know how many percent of "frametime" blue actually moved and we can then move blue again with the remaining percent after the collision has been resolved and blues velocity has been updated. This way no "frametime" is lost when collisions happen and the simulation looks smoother.

 

In a case where red corner is inside blue polygon you can use the same method. Corner A just comes from red and surface B comes from blue.

 

 

We still need to solve the case where the right red polygon is a tiny bit higher than the left and blue moves along the surface from left to right. When it hits the right polygon its going to hit it horizontally again and again and never get past it. That is why we need a variable to override the behaviour. When we search the closest surface if we find a surface that is less than minypenetration away and the resulting surfacepenetration vector would be mostly vertical we need to choose that one. And in this case we also don't move blue backwards but upwards instead to avoid getting stuck. If you don't do this then your seams must be perfect or you get "wierd stops" when you hit the seams from the lower side.

 

Edit: Ohsnap I had the vectors in the calculation of t wrong way around.

Edited by PunCrathod

Share this post


Link to post
Share on other sites

 

I found several solutions to this problem, such as:

- Make the world out of line segment loops without inner edges.

I think too that you should detect edges of surfaces that cannot be penetrated. Collect all your edges penetrations without considering unsurfaced edges, find out paralel edges (if you detect penetration vector length it should be trivial for you as well), filter from penetration collection the "unreachable" edge's penetrators, and consider what you have left only, ordered by size as well. Should work like a charm as I think of it

Share this post


Link to post
Share on other sites

I cant understand properly your solution. Could you explain it better or give a pseudocode example, please? Also, notice that im using different polygons in my engine, not only AABBs.


Ok let me try.
All of this should work with any size and shape polygons and the image has axis aligned rectangles only because I was using mspaint.
attachicon.giffigurea.png
First we need to find a corner from blue polygon that is inside red polygon and call it corner A. Then find the surface in red wich is the closest one to corner A that is between corner A and an adjacent corner from blue and call it surface B.
In order to move the blue outside of the red polygon we need a vector from corner A to surface B and call it surfacepenetration.
Then we calculate the angle between surfacepenetration and a vector(0,1) and call it surfacenormalrotation.
Then make a new vector called rotatedvelocity by copying and rotating the original velocity by surfacenormalrotation.
Now we take the Y component of rotatedvelocity and divide it by the length of surfacepenetration vector.
This gives us a float t between 0 and 1. This is the precentage of velocity you need to move blue one backwards to make corner A be outside of red polygon.

Here is a pseudocode for the moving blue backwards part.
float angle=findangle(surfacepenetration,upvector)vector2d rotatedvelocity=blue.velocity.copyrotatevector(rotatedvelocity,angle)float t=abs(rotatedvelocity.y/surfacepenetration.length)blue.pos-=blue.velocity*t
.

When we enter the collision handling we repeat this until blue is not inside any red polygons. Then we process what happens to blue based only on the last collision that was detected this way as that is collision would have happened first if your simulation steps were small enough. In your first example picture it would always be the collision with the left red rectangle and the blue stops because of hitting the right red rectangle horizontally never happens.

Also if we store the percentages of velocity we moved blue backwards we know how many percent of "frametime" blue actually moved and we can then move blue again with the remaining percent after the collision has been resolved and blues velocity has been updated. This way no "frametime" is lost when collisions happen and the simulation looks smoother.

In a case where red corner is inside blue polygon you can use the same method. Corner A just comes from red and surface B comes from blue.


We still need to solve the case where the right red polygon is a tiny bit higher than the left and blue moves along the surface from left to right. When it hits the right polygon its going to hit it horizontally again and again and never get past it. That is why we need a variable to override the behaviour. When we search the closest surface if we find a surface that is less than minypenetration away and the resulting surfacepenetration vector would be mostly vertical we need to choose that one. And in this case we also don't move blue backwards but upwards instead to avoid getting stuck. If you don't do this then your seams must be perfect or you get "wierd stops" when you hit the seams from the lower side.
Thank you a lot, but how and why did you chose the vector(0, 1)? Should i change it, if we are sliding along the vertical or any other angle wall? Do i need a way to determine this vector for every collision?

Share this post


Link to post
Share on other sites

Oh, i think i get it. We can determine the t as the dot prosuct of velocy and penetration vector devided by penetration vector length. Yeah, that must work if the body do not penetrate too deep so the minimum transaltion vector is calculated on the right (first intersected) edge. Also, i think it will not work for circles. Anyway, thank you!

Edited by neonsoup

Share this post


Link to post
Share on other sites

Sorry I made a mistake in the calculation of t. The length of the penetration vector was supposed to be divided by the y component of rotatedvelocity.

 

Also I chose the vector (0,1) for the surfacenormalrotation so we can use the y component of the rotatedvelocity. You can use vector (1,0) if you want but then you need to use x component from the rotatedvelocity. This rotation is done so we can treat the surfacepenetration as an axis aligned vector so we can compare a single component from velocity vector to the length of the surfacepenetration.

 

Also in the unlikely event where t happens to be larger than 1 or rotatedvelocity.y is 0 then the chosen surface was invalid and you need to choose a new one. This can happen if we approach from an angle that is too steep compared to the penetrationvector wich means that blue could not have come from that direction in the firstplace. If you can't find a surface that results with t between 1 and 0 then blue was already inside red before it even moved.

 

Please note that the only valid surfaces are those that are between two adjacent corners of blue or two adjacent corners of red if we are evaluating surfaces of blue. It must be done both ways or otherwise you miss the collisions where a corner of red is inside blue

 

 

i think it will not work for circles

 

This does work on circles. Altough it can require multiple iterations(solve t and move blue backwards a lot of times until it finally is outside) and could take a long time but it will eventually get there.

 

 

But what if the blue body moves straight from up to down?

 

This shouldn't require any special handling.

 

Oh and because floats and doubles(64bit floats) can be a bit inaccurate at times you may need to modify the calculation of t by adding a little padding.

float t=0.001+abs(surfacepenetration.length/rotatedvelocity.y)

.

 

Another thing that comes to mind is that when choosing the surface you could try to optimize it by choosing a surface where the angle between the surfacepenetration and velocity is closest to pi radians or 180 degrees instead of the shortest one. In most cases they are the same but there are some cases where t will be over 1 if you use the smallest penetration length and in these cases choosing a surface where the angle between surfacepenetration and velocity was closest to 180 degrees would have been the correct one.

 

Also instead of checking if a surface is between two adjacent corners you can just check if the angle between the surfacepenetration and velocity is over pi/2 radians or 90 degrees as that indicates that blue is approaching the surface from the wrong side.

 

Checking the angle instead of penetrationlenth also fixes this.

 

that must work if the body do not penetrate too deep so the minimum transaltion vector is calculated on the right (first intersected) edge

 

Edit: Noticed that choosing the surface with the angle would make incorrect choises in some cases. But checking if the angle between surfacepenetration and velocity is between 1/2pi and 3/2pi radians or 90 and 270 degrees does fix the case where blue made it deep enough to make the penetration to the otherside be smaller than the side it came from.

Edited by PunCrathod

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement