Collision detection(SAT): Colliding with several tiles at once

Started by
6 comments, last by hallgeir 14 years ago
Hi, I've been fiddling with my collision detection for quite some time now, and I've run into some problems. First off let me explain my thinking. My main game loop runs like this: - Take input - Perform collision tests (check if / when during the NEXT frame a collision will happen, and if so, run the object's collision handler) - Update all object's positions by their velocity (basically position += velocity) - Add the accelleration vector to the velocity - Loop and go again Now... the collision detection is a continuous SAT implementation which tests a bounding box (the object) against line segments (which represents tile surfaces), and passes a vector to the object if a collision occurs. The vector is the vector from the collision point (in the future) to the object, if the object will collide during the next frame. If the object already overlap with the line segment, the vector is opposite to the velocity. I have a problem: The object may collide with two line segments at once (for instance, two neighboring ground tiles), and thus its collision handler is run twice. This poses a problem when I add the collision vector to the position to prevent the object from falling through the tile edge the next update, because then of course it's added to the position twice. I was then thinking of only running the collision handler when colliding with the CLOSEST edge, which solved the previous problem but of course introduced a new one: Sometimes we collide with two line segments, and do want the collision handler to handle both collisions (like when walking into a corner - we want to not fall through the floor due to gravity, and we want to not walk through the wall). Do anyone have any bright ideas here on how to solve this problem? It would be greatly appreciated! I'll post the code for my collision detection here, if that is of any help at all. Thanks in advance!

public static void TestCollision(ICollidable o, List<Edge> edges, double frameTime)
{
	//Applying Separating Axis theorem
	//First find all the axis
	List<Vector> axis = new List<Vector>();
	axis.Add(new Vector(1,0)); // Bounding box axis 1
	axis.Add(new Vector(0,1)); // Bounding box axis 2
	axis.Add(new Vector());    //Line segment axis 1
	axis.Add(new Vector());	   //Line segment axis 2
	
	double minimumCollisionTime = double.PositiveInfinity;
	Edge firstCollisionEdge = null;
	CollisionResult finalResult = new CollisionResult();
	
	Vector velocity = o.Velocity * frameTime;
	finalResult.MinimumTranslationVector = o.Velocity * frameTime;
	finalResult.FrameTime = frameTime;
	
	foreach (Edge e in edges)
	{
		CollisionResult result = new CollisionResult();
		result.IsIntersecting = true;
		result.WillIntersect = true;
		double collisionTime = double.NegativeInfinity;
		
		Vector translationAxis = new Vector();
		
		//Ignore edges facing the same way as we move
		if (e.Normal.DotProduct(velocity) > 0) continue;
		
		//Calculate the axis of the edge
		Vector v = (e.P2-e.P1).Normalize();
		axis[2] = v;
		axis[3] = new Vector(-v.Y, v.X);
		
		foreach (Vector a in axis)
		{
			//Project line and box
			Projection prj1 = ProjectBox(o.BoundingBox, a);
			Projection prj2 = ProjectLine(e.P1, e.P2, a);

			//Check if projections overlap in the first place
			double distance = prj1.GetDistance(prj2);
			if (distance > 0)
				result.IsIntersecting = false;

			if (distance >= 0)
			{
				//Find the velocity along the axis and see if we'll ever intersect
				double velAxis = a.DotProduct(velocity);
				if (velAxis == 0 && distance > 0)
					result.WillIntersect = false;

				//Calculate the time it takes to travel the distance
				if (result.WillIntersect)
				{
					double t = (prj2.Max - prj1.Min) / velAxis;
					
					if (t > collisionTime) collisionTime = t;
					
					//If it takes more than 1 frame (or less than 0) to collide, it won't happen
					if (collisionTime > 1 || collisionTime < 0)
						result.WillIntersect = false;
				}
			}
			
			if (!result.IsIntersecting && !result.WillIntersect) break;
		}
		
		if (collisionTime > 1 || collisionTime < 0)
			result.WillIntersect = false;
		
		//Already intersected
		if (result.IsIntersecting && !result.WillIntersect)
		{
			result.MinimumTranslationVector = -velocity;
			finalResult = result;
			firstCollisionEdge = e;
		}
		//Intersection happens during the next frame
		else if (result.WillIntersect)
		{
			result.MinimumTranslationVector = velocity * collisionTime;
			
			if (result.MinimumTranslationVector.Length < finalResult.MinimumTranslationVector.Length)
				{
					finalResult = result;
					firstCollisionEdge = e;
				}
		} 
	}
	
	if (firstCollisionEdge != null)
		collisionEvents.Add(new CollisionEvent(o, firstCollisionEdge, finalResult));
}

Advertisement
Hi,

You should modify loop logic a bit:

- Take input
- Test for collision
* Get the closest intersections that happened at the same time
* Calculate new object center and new velocity vector ( it is one center and one velocity because you are colliding at the same time )
* Send this to response phase( your collision handler )
- repeat test for collision with this new information until your spend your velocity vector

- repeat all

This way it doesnt matter if you collide with multiple edges as long as they happen at the same time because you will get same new center and velocity for collision at that time.

Hope this helps
Sorry my English
You're effectively running a pushout algorithm: working out where the object would be, and then working out how far back along its velocity vector it needs to be pushed to no longer be colliding with that tile. What you need to do is ensure that it's pushed enough to not be colliding with any tile. As such, instead of going:

1: Find first tile there's a collision with
2: Alter the position to ensure it's not colliding
3: Find next tile there's a collision with
4: ???

you could go

1: Find first tile there's a collision with
2: Store distance required to push back along velocity vector
3: Find next tile there's a collision with
4: Calculate distance required to push back
5: If this new distance is longer, replace the original one, else throw it away
6: Goto 3 until there are no more collisions
7: THEN apply the pushout based on the longest distance required to ensure it's not colliding
Thanks, both of you. This is something like what I'm looking for.

Seol, a question: I expect that I need to check X and Y distances separately? Because let's say I'm moving with velocity (1, -1) (that is, down to the right) into a corner where we have a horizontal tile and a vertical one. If I'm equally far away from both tiles, then the distances is the same and only one of these collisions are handled, and as such I'd fall through either the floor or the wall.
If you are equally far away from both tiles, then the distances are the same and only one of these collisions are handled...This is true because no matter which one you handled, you should not be passing trough either of the tiles (IF the distances are the same). If you fall through one of them it means they were not at same distances and collision did not happen at the same time with both of them ( you were already inside one tile). So check that you are calling collision handler only for one of the CLOSEST intersections. After that you should have new modified position of your object and new direction/velocity vector. Then feed your collision test with this new information ( repeat all until you spend all the velocity )
One more thing...you should build ellipsoid around your objects bounding box. It is much easier and accurate to test with ellipsoid than with BB. Then use length of the ellipsoids radius vector to test distances to tiles.
Quote:Original post by hallgeir
Thanks, both of you. This is something like what I'm looking for.

Seol, a question: I expect that I need to check X and Y distances separately? Because let's say I'm moving with velocity (1, -1) (that is, down to the right) into a corner where we have a horizontal tile and a vertical one. If I'm equally far away from both tiles, then the distances is the same and only one of these collisions are handled, and as such I'd fall through either the floor or the wall.
No, both collisions are "handled" - it's just that handling a collision here, using this methodology, means ensuring you don't overlap with a tile. This way, you'll effectively find out how far you can move until you collide with each tile, and the shortest distance of those will be how far you move: this also means you don't need to work out which is the closest edge prior to "resolving" collisions.
Thanks, I understand now what you're saying. I'll try it out and see how it works out. :)
Thanks for your help, folks!

This topic is closed to new replies.

Advertisement