Hi,

I've been looking at how to use the Seperating Axis Theorm to deal with convex polygon-polygon collision detection and response but I've hit a wall on how to deal with multiple colllisions at the same time. For example the polygon representing the player character could be moved using a vector which would cause it to collide with 2 other polygons at the same time, from examples such as this: SAT Tutorial, only one of the collisions is delt with and the polygon will intrude into the other polygons. (You have to modify the example to have some more polygons in it to see this happen.) Does anyone know how to over come this problem?

The IndivisbleMan

I would say to just loop over all the near polygons and do what the SAT tutorial says.
This would handle all possible collisions and only do it against all close polygons and not every polygon in the scene.
Probably best dealt with a broad phase collision system.

You need to not action the collision data as you get it, rather batch it all up. I use a collision list and once I have collected all collision data for that frame in it, action them in turn.

Hi,

@csharp1024 I agree that I shouldn't loop over every polygon in the scene, I was planning on using a grid based system to pick which polygons to check against.

The problem with just following the tutorial is that it doesn't solve the problem I encountered. This image should demostrate what I mean:



If the polygon C follows the vector path at some point it will collide with both A and B. The tutorial shows how to deal with one collision by moving C the shortest distance away from the polygon it is colliding with, but this will push it into the other polygon. If the example program from the tutorial is modified to look like the image I have posted then polygon C will move between A and B.

Also A and B are both stationary polygons, they should remain where they are, at the moment I am only considering how to move C in response to the collisions.

If you use a similar physics movement method that I used in this post, then you can set the mass for A and B to 0 (imoveable objects) and then use a collision nomal along with a restitution value to alter C's velocity. If you batch the collisions up then C's velocity will b adjusted twice, if it hits at exactly the same time then they should (if not totaly) cancel each other out.

I tried modifying the code from the tutorial directly, I added:

            p = new Polygon();
            p.Points.Add(new Vector(50, 50));
            p.Points.Add(new Vector(100, 0));
            p.Points.Add(new Vector(150, 150));
            p.Offset(350, 430);

            polygons.Add(p);

            p = new Polygon();
            p.Points.Add(new Vector(0, 0));
            p.Points.Add(new Vector(0, 50));
            p.Points.Add(new Vector(50, 50));
            p.Points.Add(new Vector(50, 0));
            p.Offset(290, 290);

            polygons.Add(p);

To the constructor, where the other poylgons are added. Then I've tried various alterations to the Form1_KeyDown method, making it loop through all the polygons and summing the returned MinimumTranslationVector and then applying that. Also I tried taking the average MinimumTranslationVector by summing and dividing by the number of collisions. None of the things I've tried worked. I'm thinking the MinimumTranslationVector is the wrong thing to be using and that I need to alter what is returned from the PolygonCollision method.

I can see how to apply the physics from the last post to make the player polygons velocity change before doing the collision detection, as this then works on the players polygon and vector/velocity. And this is deffinately the next area to work on/combine with the collision detection and response methods.

I haven't seen any tutorials that show how to deal with multiple simultanious polygon collisions, if there are any anyone knows of I'd like to see them.

ps. Sorry for calling you Chris... Sometimes I get names mixed up.

No worries :)

That sounds awesome, but I've found a set of demos (in C++, using GLUT) which I think I can use to make a C#/XNA version and then eventually my own game. If you want to see them I found them at: http://www.gamedev.net/community/forums/topic.asp?topic_id=251638

If you want to finish the tutorials for none programmers first, I have enough to keep myself busy with. Don't over work yourself on my behalf.

Cool! I'll have a look at that.

IndivisibleMan:

Hi,

I've been looking at how to use the Seperating Axis Theorm to deal with convex polygon-polygon collision detection and response but I've hit a wall on how to deal with multiple colllisions at the same time. For example the polygon representing the player character could be moved using a vector which would cause it to collide with 2 other polygons at the same time, from examples such as this: SAT Tutorial, only one of the collisions is delt with and the polygon will intrude into the other polygons. (You have to modify the example to have some more polygons in it to see this happen.) Does anyone know how to over come this problem?

The IndivisbleMan

Try wrapping the individual polygons with one larger convex bounding polygon, and resolving collisions using that one once you detect a collision?

IndivisibleMan, have you gotten any further with this? I initially checked out the tutorial you started out with and encountered the same problem with multiple polygons. I also checked out the C++ tutorial you linked to here because it was listed as a reference for the first tutorial. It looks spectacular, but it's C++ and the source code looks too advanced for me. Even if I manage to convert it to C# there's no way I'll understand what's going on there.

I'm currently messing around with the pogopixels tutorial trying to get it to work with multiple polygons. I have rewritten it quite a bit to make it more understandable for me (Mainly because I don't understand structs etc. yet :)), but it still doesn't work with multiple polygons and I don't understand why it fails. I have removed all the breaks and similar and it loops through every polygons all the time so I don't understand how it can allow itself to pass right through a polygon if it's already colliding with another polygon. By looking at the code I would think there's no difference between colliding with 1 or multiple polygons.

I will let you know if I manage to make it work.

What Charles said about batching up the collisions and then acting on them did the trick. The only problem now is that I'm doing it wrong. :)

I'm just going through all the collisions for all the polygons and adding the vectors together and then offsetting my player by that new vector. If my player for example collide with 2 polygons which push him out in the same direction he gets pushed twice as far as he should which doesn't look good. I know what the problem is I'm just to dumb to fix it. :)

Here's what I have now: PolyColli.zip (54kb)

Here's what my update method looks like:

I've based it on the tutorial on pogopixels, but I've modified it to use XNA's Vector2 instead of the Vector class he implemented in the tutorial as well as use the PrimitiveBatch for drawing the polygons. The code is a bit messy and I've made changes all around, some of them may be stupid and unnecessary, but oh well. :)

The BoundingRectangles are definately unnecessary, but I just left them in there because I spent so much time setting them up. :P

My math skills have taken a considerable hit over the years so now I'm sitting here with a few math and physics books, but I'm still unable to fix the problem at the moment. Maybe someone can take a look and help me out? :)

By using a HashSet I kept it from adding the same Vector 2 or more times each frame if I was colliding with many polygons which were all pushing me in the same direction thus fixing that bug:


If I can just implement a broad phase collision detection now I have something I think can work. :)

I've been using that PolyColly resource for a while now. It's pretty great. I've been using it for my game, and it gets pretty thorough. I'd recommend it to anyone looking at 2d Physics.

You need to calculate the penetration depth and move the object that distance away from the collision along the contact normal. Glad the collision batching helped move you along though :)