next »

[Eiffer]

Ok I'm spent a ton of time in the last couple days figuring out collision using SAT (Separating Axis Theorum). It took some work as a lot of Vector math is new to me, but I now have it working wonderfully.... except for one little glitch.

Right now if I move my little "ship" square up next to one of the collision blocks I have set up for testing and keep holding the stick towards the block the "ship" sort of jitters back and forth. It looks like it's basically detecting the collision one frame, then not detecting it the next and moving the ship into the block by the max speed, then it catches the collision and moves it back out. I have the ship change color based on if a collision is detected, so I can tell that it is definitely catching the collision one frame then missing it the next.

my ship update goes as follows (psuedocode):

Code:

- calculate the ship's current speed (vector to add to position)
- determine collision at current position as well as next position and adjust speed to avoid collision.
- move ship to next position (add speed vector to position vector)

Here's my speed calculation:

Code:

internal void MovePlayer(Vector2 theThrust)
{
    speed = momentum + theThrust;
    if ( speed.Length() > maxSpeed)
    {
        speed.Normalize();
        speed *= maxSpeed;
    }
    if((momentum.Length() < 0.01) && (theThrust == Vector2.Zero))
        momentum = Vector2.Zero;
    else
        momentum = speed;
    momentum -= momentum * 0.05f;
}

And Here's the collision code:

Code:

public PolyCollisionResult PolygonCollision( CollisionPolygon polygonA, 
        CollisionPolygon polygonB, Vector2 velocity)
{
    PolyCollisionResult result = new PolyCollisionResult();
    result.WillIntersect = false;
    result.Intersect = true;
    result.MinTranslationVector = Vector2.Zero;
    float IntervalDist = 0;
    float minIntervalDist = float.PositiveInfinity;
    Vector2 minTransVector = Vector2.Zero;
    int lastVert;
    int edgeCount;
    Vector2 axis; //the axis we want to project the polygons onto;
    Vector2 edge;
    //How many edges do we have in total
    edgeCount = polygonA.Vertices.Count + polygonB.Vertices.Count;

    for (int edgeIndex = 0; edgeIndex < edgeCount; edgeIndex++)
    {
        if (edgeIndex < polygonA.Vertices.Count)
        {
            lastVert = edgeIndex - 1;
            if (lastVert < 0) lastVert = polyA.Vertices.Count - 1;
            edge = polyA.Vertices[edgeIndex] - polyA.Vertices[lastVert];
        }
        else
        {
            lastVert = edgeIndex - 1;
            if (lastVert < polyA.Vertices.Count) lastVert = edgeCount - 1;
            edge = polyB.Vertices[edgeIndex - polyA.Vertices.Count] -      
                   polyB.Vertices[lastVert - polyA.Vertices.Count];
        }
                
        axis = new Vector2(-edge.Y, edge.X);//normal of the edge
        axis.Normalize();
        float minA = 0; float maxA = 0; float minB = 0; float maxB = 0;
        ProjectPolygon(axis, polygonA, ref minA, ref maxA);
        ProjectPolygon(axis, polygonB, ref minB, ref maxB);
        IntervalDist = IntervalDistance(minA, maxA, minB, maxB);
        if (IntervalDist > 0)
        {
            result.Intersect = false;
        }

//-----------------Now we see if the polys WILL intersect----------------------
        float VelocityProjection = (axis.X * velocity.X + axis.Y * velocity.Y);
        //Get the projection of poly A during movement
        if (VelocityProjection < 0)
            minA += VelocityProjection;
        else
            maxA += VelocityProjection;

        //Test for intersection
        IntervalDist = IntervalDistance(minA, maxA, minB, maxB);
        if (IntervalDist > 0)
            result.WillIntersect = false;

        //if the poly are not and will not intersect, exit the loop
        if (!result.WillIntersect && !result.Intersect)
            break;

        IntervalDist = Math.Abs(IntervalDist);
        if (IntervalDist < minIntervalDist)
        {
            minIntervalDist = IntervalDist;
            minTransVector = axis * minIntervalDist;
            Vector2 d = polyA.Center - polyB.Center;
            if ((d.X * minTransVector.X + d.Y * minTransVector.Y) < 0)
                minTransVector *= -1;
        }        
    }
    if (result.Intersect)
        result.MinTranslationVector = minTransVector;
    return result;
}

The ProjectPolygon() and IntervalDistance() methods are almost verbatim from here:
http://pogopixels.com/blog/2d-polygon-collision-detection/

If any code gurus can help out a noob and tell me what I'm doing wrong I would be eternally thankful. My head hurts from thinking about this and it's almost 12:00 here, so I'm off to bed.

[Triplefox]

Nothing particularly sticks out to me in the code, but offhand, I'd suggest debugging by using smaller test cases. Collision's complexity is extremely easy to underestimate and I can cheerfully say that I have underestimated it every single time I've implemented it.

The in-game integration is the last step and should come after you've put the system through abusive testing in a controlled environment, where the result doesn't appear in real-time but can be stepped through carefully with lots of debug data and visual indicators of what's going on. You may have missed something at an early stage that wouldn't show up without doing that kind of thorough test, and the "one little glitch" might turn out to be buried quite deep.

Once you're completely confident about the system, the integration can be done without tearing your hair out, because even if there are strange corner cases, you'll know what they are.

[Eiffer]

Well I'm not really at an implementation stage right now anyhow. I've just got some squares on the screen and I can move one of them with the joystick. I'm just trying to figure out collision detection with this program. I'll try to put in more debug data and see if I can modify the code to step through or create an output file with a log of the collision.

I have a feeling that the problem lies in how I'm calculating the speed vector, or to do with adding the momentum to the ship's movement. Perhaps I'll try simplifying the movement stuff down to just a unit vector in the direction of the joystick and see if it still happens.

[st33d]

Rather than resolving the collision, get the resolver to draw where it wants to send the ship to. That'll make it much easier to debug.

And make sure you're updating the graphics after resolving the collision, otherwise it will definitely jitter because it's showing what's happening during resolution.

[Alex May]

How are you adding the speed to the position?

[Eiffer]

How are you adding the speed to the position?

First I determine the speed vector based on gamepad input and the momentum of the ship.
Then I Determine if the ship will collide with anything at it's current position plus the speed. If there will be a collision I adjust the speed vector to where it won't collide. After that I just add the speed vector to the position vector of the player.

[Eiffer]

Rather than resolving the collision, get the resolver to draw where it wants to send the ship to. That'll make it much easier to debug.

And make sure you're updating the graphics after resolving the collision, otherwise it will definitely jitter because it's showing what's happening during resolution.

Thanks, I'll see if I can change the draw method as you suggested.

Also I'm definitely updating the graphics after resolving the collision. I'm using XNA, which by default calls an update method to update positions, collision etc, then calls the draw method.

[Alex May]

It doesn't sound like you have any glaring problems in your pseudocode, so maybe it's a problem with the implementation - care to post the salient parts of your update code?

[Eiffer]

Well the player object updates as follows:

Code:

        public override void Update(GameTime gameTime)
        {          
            position += speed;
            //rotate the collision poly

            elapsedTime += gameTime.ElapsedGameTime;
            if (elapsedTime > TimeSpan.FromMilliseconds(frameDelay))
            {
                currentFrame++;
                if (currentFrame >= frames.Count)
                {
                    currentFrame = 0;
                }
                elapsedTime -= TimeSpan.FromMilliseconds(frameDelay);
            }
            base.Update(gameTime);
        }

And the other update method that might effect things is:

Code:

if (activeScene == ActionScene)
            {
                lastRotation = ActionScene.Player.Rotation;
                LXDistance = gamePad.ThumbSticks.Left.X;
                LYDistance = gamePad.ThumbSticks.Left.Y;

                //Update player rotation
                if((LXDistance != 0) || (LYDistance != 0))
                {
                    ActionScene.Player.Rotation = ((float)Math.Atan2(LXDistance, LYDistance) - MathHelper.ToRadians(90));
                    if (ActionScene.Player.Rotation != lastRotation)
                    {
                        ActionScene.Player.CollisionPoly.Rotate(ActionScene.Player.Rotation);
                    }
                }
                else
                    ActionScene.Player.Rotation = lastRotation;
                //Next we need to check that next position for collision, and if there is a collision, we move the player
                //back to a safe position
                
                
                //Movement handled with acceleration
                ActionScene.Player.MovePlayer(new Vector2(LXDistance, -LYDistance));
                ActionScene.Player.SolidCollision(ActionScene.Blocks);
                //everything above determines where the player will be on the next frame if nothing is in his way
                //Next we need to check that next position for collision, and if there is a collision, we move the player
                //back to a safe position
                

                //Shots
                RXDistance = gamePad.ThumbSticks.Right.X;
                RYDistance = gamePad.ThumbSticks.Right.Y;
                if ((RXDistance != 0) || (RYDistance != 0))
                    ActionScene.ShotManager.CreateShot(ActionScene.Player.Position, new Vector2(RXDistance, -RYDistance));
          
            }

            //The we store the old gamepad and keyboard states
            oldKeyboard = keyboard;
            oldGamePad = gamePad;

            //upadate all the Enabled game scenes
            for (int i = 0; i < gameScenes.Count; i++)
            {
                if (gameScenes[i].Enabled)
                    gameScenes[i].Update(gameTime);
            }

This is the part of the update method from the scene manager that is running while the "action scene" is running. In this small program the action scene is the only scene.

I've been messing around with things and discovered that the jitter only happens when the rotation of the ship changes. If I'm holding the joystick steady at one angle, the ship doesn't jitter. I'm guessing it has something to do with the rotated positions of the collision polygon vertices being calculated too late or something so that the rotation isn't properly taken into account... I'm gonna dig into this some more.

****Edit****

So the more I think about it and look at my code, the more I realize that the rotation angle is the problem. I think the issue is that I am calculating the rotated vertices without any regard to if the new position will cause a collision. I thought that this would be corrected for when the collision routine calculates the translation vector needed to get the ship out of collision, but it would seem that's not the case. So now I need to figure out how to make sure that I can't rotate the corners into the box that I am colliding with.

I'm going to have to re-write some of this code, or a lot of it, to make this work correctly. But then again, that's why I'm messing with this little test program before starting in on the whole game.

[Eiffer]

Ok sorry for all the posts, but this has me stumped. I added in the ability to just rotate the ship without moving it, and if I move up next to a block and rotate, the rotation properly pushes the ship away. So it has something to do with the combination of moving while rotating.

Again sorry for posting all these stupid little thoughts, but if nothing else, writing out the issues is helping me think through it.

[Eiffer]

Ok. Well I feel like a total idiot. The whole problem was actually really simple. I originally only wrote code for checking if polygons were currently intersecting and then once I was sure that was working, I added the code to see if they would intersect on the next frame. Problem is that I forgot to change the condition which adjusted to speed of the ship if there was a collision. It was only checking to see if the "Intersect" bool was true, when it should check "WillIntersect" as well.

This is why I love programming.... 

Thankyou so much to everyone who tried to help out. You suggestions did force me to re-examine my code in detail and actually helped me catch some stuff that might have lead to problems down the road, or at least made my code messier than it needed to be.

Well now that the collision is working I think I need to clean up my code and rethink a couple of my game objects. Then it's time to figure out a map format that will work. But that's another topic.

Thanks again everyone. TIGSourcers (TIGSourcerors?) are some of the most helpful people I've met on the intertrons.

PS:

If there is a way to mark a topic as SOLVED or anything I don't know how to do it. If any Moderator wants to do so that would be great. If anyone thinks it's necessary that is.

[Parthon]

Great that you got it working, it's always something so simple.

If you can, put [Solved] in the title, I think you can edit the title.

[Alex May]

Yep just edit the title of the first post.