20 replies to this topic

[prushik]

Basically, its the same project I'm working on, 2D driving game. I have 2 (or more, but 2 for now) vehicles using rigid body based physics, all in 2D. right now there are no other obsticles to collide with, just the 2 vehicles.

I think I can detect collisions perfectly (based on bounding boxes only), and those same collision detection functions return the point of contact relative to both vehicles. I can easily determine the velocity of those points on each vehicle.

So, what I did was take the difference of those 2 speeds, and multiply that by the other vehicle's mass to get the force, and then apply that to the vehicle at the point of contact, do that for both vehicles. The result looks ok for stuff like head on collisions, or high speed collisions, if one vehicle is stationary, etc... probably not too realistic, but doesn't need to be perfect, just not too absurd.

However, the real problem occurs when I try to push another vehicle with the players vehicle, the result isn't bad for the first few frames, but then the player starts to push its way into the NPC vehicle, so the images overlap.

So, what is the problem here? I'm a bit confused about how this is happening, at this point, the vehicles are even the same mass, so if I mix up which vehicle's mass I am multiplying, the result should be the same.

This seems like something that should have a well known solution, I'm just too dumb to figure it out on my own.

[jellyfishchris]

Short answer: Big math equations.

Long answer: You need to look up impulse equations for rigid bodies, try the link below.

 

http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-07-dynamics-fall-2009/lecture-notes/MIT16_07F09_Lec23.pdf

[StratfordCanning]

I made a multi-rigid-body game (a load of boxes falling about) in javascript and found that trying to solve the explicit impulse equations is basically a total nightmare when there are multiple collisions and bodies in contact with each other.

 

My approach was to let them overlap a bit and then say that the reactive force is some suitable function of the overlap.  The reactive force acts in equal and opposite directions on each body (Newton three), this is crucial and means that the momentum and angular momentum work out right.  You need the function to have a hysterisis so that energy gets swallowed up in each collision or your objects go haywire.  Basically, the force function must make the force smaller as the bodies push apart but the exact details are not so important.

 

I have let the overlap effect be quite noticeable to show what is going on, but you could reduce it by making the bodies more rigid and also having a bit of a buffer around each object.

 

Realistic friction is a whole other question though.

 

Feel free to grab and modify the javascript.  I'm learning about websites and things and have put up a site as a project and some of my silly javascript games are on it.  The site works in Mozilla but looks poo in IE8 and the Canvas object the game uses needs at least IE9 anyway.

 

Go here:

 

http://www.moonsch.com/

 

Go to 'Games Links' and look at 'Boxes and Cat'.  Double click the boxes to make them vanish.  Reply if you have trouble, I'll try to respond to any questions.

[prushik]

I made a multi-rigid-body game (a load of boxes falling about) in javascript and found that trying to solve the explicit impulse equations is basically a total nightmare when there are multiple collisions and bodies in contact with each other.

 

My approach was to let them overlap a bit and then say that the reactive force is some suitable function of the overlap.  The reactive force acts in equal and opposite directions on each body (Newton three), this is crucial and means that the momentum and angular momentum work out right.  You need the function to have a hysterisis so that energy gets swallowed up in each collision or your objects go haywire.  Basically, the force function must make the force smaller as the bodies push apart but the exact details are not so important.

 

I have let the overlap effect be quite noticeable to show what is going on, but you could reduce it by making the bodies more rigid and also having a bit of a buffer around each object.

 

Realistic friction is a whole other question though.

 

Feel free to grab and modify the javascript.  I'm learning about websites and things and have put up a site as a project and some of my silly javascript games are on it.  The site works in Mozilla but looks poo in IE8 and the Canvas object the game uses needs at least IE9 anyway.

 

Go here:

 

http://www.moonsch.com/

 

Go to 'Games Links' and look at 'Boxes and Cat'.  Double click the boxes to make them vanish.  Reply if you have trouble, I'll try to respond to any questions.

 

Cool, thanks. Awesome game, I played it far too many times before even looking at the code.

Actually, still haven't gotten around to looking at it really, although I at least opened it. I don't care too much about realistic friction, your game reminds me a lot of the physics in FreeGish, which I also played an embarrassing number of times. I don't know if it will work for my game or not, but I'll check it out and see.

 

 

Short answer: Big math equations.

Long answer: You need to look up impulse equations for rigid bodies, try the link below.

 

http://ocw.mit.edu/courses/aeronautics-and-astronautics/16-07-dynamics-fall-2009/lecture-notes/MIT16_07F09_Lec23.pdf

 

Yes, I have been reading about impulse. Whenever I see a site with all those big equations my mind just goes blank and I can't focus enough to make it make sense, if they would just write it all on one line like an equation in C I could understand it no problem, but instead they gotta be all mathy.

 

I found this site: http://hyperphysics.phy-astr.gsu.edu/hbase/truckc.html

Which talks about impulse here: http://hyperphysics.phy-astr.gsu.edu/hbase/impulse.html

Which seems to tell me what I want, but I think I am only thinking of the head on collision which is basically 1D, and 2D collisions are more complicated than that.

I looked at the one you linked to also. Scary stuff. But thanks, I gotta sit down and work all that out and figure out how to do it in my code.

[prushik]

There is one thing that I am really really confused about.

Force = Mass * Acceleration

Right? This is basic stuff. If a vehicle collides with a brick wall, I can use this equation to figure out how much force gets applied to the vehicle to make it stop moving. However, in a collision, there are TWO objects colliding. In the F=ma , which object's mass do I use? If every action has an equal and opposite reaction, it must be the same amount of force in both directions.

Ok. I guess I am starting to see my problem. acceleration is not known, right? If I use the velocity of the player it applies enough force to stop the player, which won't be the case if the vehicles have different masses.

 

So the answer is much more compicated than I thought, I see now. However, since the vehicles that I am testing with DO have the same mass, shouldn't what I am doing (difference of velocity times mass (of either vehicle, since they are the same)) work correctly?

 

 

Ok, also confused about impulse. I understand what it is, however, in my simulation, it shouldn't apply because the collision takes place instantly instead of over a period of time. So I only need to calculate force, right? If the collision is continuous, then it will count as multiple collisions, isn't that sufficient?

[StratfordCanning]

I hope I'm not teaching you to suck eggs but I would seriously recommend simplifying everything down to one object moving under gravity and getting that going first.

 

I haven't used impulses at all, just forces.  I am just playing around with things myself with no ambition beyond my own amusement so I've no idea if there's a standard way of laying these things out.   Obviously this won't compile and the numbers are made up, but the sort of framework I've used is:

 

Object MyThing = new Object();

double MyThing.mass=5;

double MyThing.x_position=100;

double MyThing.y_position=100;

double MyThing.x_velocity=0;

double MyThing.y_velocity=0;

double MyThing.x_force=0;

double MyThing.y_force=0;

 

controlLoop(RunMeEvery TimeInterval)

{

 

   GetBulkForces(MyThing);

   GetCollisionForces(MyThing,YourThing);

  

   //velocity is change in postion per unit time

   MyThing.x_position += MyThing.x_velocity;

   MyThing.y_position += MyThing.y_velocity;

 

   //acceleration is change in velocity per unit time (F=ma, rearranged into a=F/m)

   MyThing.x_velocity += (MyThing.x_force/MyThing.mass);

   MyThing.y_velocity += (MyThing.y_force/MyThing.mass);

 

  DrawOnScreen(MyThing);

}

 

GetBulkForces(Thing)

{

   //Let's just have it falling under gravity, F=m*g, on a planet where gravity is -0.1 in some units

   double g=-0.1;

   Thing.yforce = Thing.mass*g;

}

 

GetCollisionForces(Thing1,Thing2)

{

   if(CollisionHappened(Thing1,Thing2))

   {

      double x_force=ForceOfTheCollision(Thing1,Thing2,"X");

      Thing1.x_force += x_force;

      Thing2.x_force -= x_force; //i.e. opposite to Thing1!

 

      double y_force=ForceOfTheCollision(Thing1,Thing2,"Y");

      Thing1.y_force += y_force;

      Thing2.y_force -= y_force; //i.e. opposite to Thing1!

   }

}

 

ForceOfTheCollision(Thing1,Thing2,XYdirection)

{

  //Lots of trig and geometry to work out how far the Things overlapped and in what direction the collision should rebound

}

 

CollisionHappened(Thing1,Thing2)

{

   //Did a collision happen?

}

[EWClay]

In a collision, you can treat the change in velocity as instantaneous. In that case, you will not be considering forces and accelerations but impulses.

An impulse is a change in momentum. Momentum is mass times velocity. The equations are not that complicated. For an impulse I, the new momentum is

m v + I = m v'

and the change in velocity is

dv = v'- v = I/m

So if you have two bodies receiving equal and opposite impulses in a collision, the change in relative velocity is

dv = I(1/m1 + 1/m2)

dv in an inelastic collision is the relative velocity, because the objects stick together. So the impulse would be

I = (v2 - v1)/(1/m1 + 1/m2)

If the second object is stationary with infinite mass (a wall), you can see that this reduces to

I = - v1 m1

Comparing the two, you can consider the two body system to have an effective mass of

1/(1/m1 + 1/m2) = m1 m2 / (m1 + m2)

Which should answer the question of which mass to use in the calculations.

Collisions in 2D are the same except that velocity is a vector. For collisions with rotation, the effective mass gets a couple of extra terms from the moments of inertia. the derivation is similar.

[StratfordCanning]

I started out trying the impulse approach as in the mechanics textbooks, but a problem arises when you want the objects to eventually calm down and rest against each other in equilibrium; there is no velocity, so no collisions, so nothing stopping one falling through the other.  Also with more than two bodies you can get weird jittery effects.  I ended up just thinking about forces which I think are a more fundamental quantity.

 

How do you use impulses in a many-bodied system and in such a way as you don't need a special case to show one thing coming to rest on top of another?  I couldn't work it out!

[EWClay]

It's possible to resolve overlaps using impulses.

The simplest way is a penalty method; add a small factor to the required separation velocity proportional to the overlap distance.

But that can add energy to the system and potentially become unstable. So another way is split impulses, where you accumulate the penalty impulses separately, and apply to the positions directly.

The key to handling simultaneous collisions is to iterate.

[prushik]

In a collision, you can treat the change in velocity as instantaneous. In that case, you will not be considering forces and accelerations but impulses.

An impulse is a change in momentum. Momentum is mass times velocity. The equations are not that complicated. For an impulse I, the new momentum is

m v + I = m v'

and the change in velocity is

dv = v'- v = I/m

So if you have two bodies receiving equal and opposite impulses in a collision, the change in relative velocity is

dv = I(1/m1 + 1/m2)

dv in an inelastic collision is the relative velocity, because the objects stick together. So the impulse would be

I = (v2 - v1)/(1/m1 + 1/m2)

If the second object is stationary with infinite mass (a wall), you can see that this reduces to

I = - v1 m1

Comparing the two, you can consider the two body system to have an effective mass of

1/(1/m1 + 1/m2) = m1 m2 / (m1 + m2)

Which should answer the question of which mass to use in the calculations.

Collisions in 2D are the same except that velocity is a vector. For collisions with rotation, the effective mass gets a couple of extra terms from the moments of inertia. the derivation is similar.

 

Wow, thats great. I think it answers all my questions about impulse. Except for 1 thing, my game deals with vehicles colliding with each other, now vehicles do compress somewhat on collisions to protect the driver, so the collisions will be almost inelastic, right? However, do I want a totally inelastic collision for my game? For a wall an inelastic collision is great, I never saw a car bounce off a wall before, but in a vehicle/vehicle collision should there be some elasticity? I'm not sure. an inelastic collision could result in problems because my collision detection actually checks if they are overlapping, I figured that would be sufficient, but maybe it isn't good enough, would it be better to check if the vehicles will overlap in the next step?

 

I started out trying the impulse approach as in the mechanics textbooks, but a problem arises when you want the objects to eventually calm down and rest against each other in equilibrium; there is no velocity, so no collisions, so nothing stopping one falling through the other.  Also with more than two bodies you can get weird jittery effects.  I ended up just thinking about forces which I think are a more fundamental quantity.

 

How do you use impulses in a many-bodied system and in such a way as you don't need a special case to show one thing coming to rest on top of another?  I couldn't work it out!

My game is top down, like blimp view, so I won't need to worry about gravity in this one. The cases that I am worried about are 1. One car constantly pushing against another. Which I am afraid the AI that I am going to write will do often... 2. cars at similar speeds and directions making contact with each other.

 

 

It's possible to resolve overlaps using impulses.

The simplest way is a penalty method; add a small factor to the required separation velocity proportional to the overlap distance.

But that can add energy to the system and potentially become unstable. So another way is split impulses, where you accumulate the penalty impulses separately, and apply to the positions directly.

The key to handling simultaneous collisions is to iterate.

I think I may need to do something like this too, since my collision detection allows them to overlap before it detects.

[EWClay]

For some degree of bounce, you would increase dv to allow for a separation velocity,

Vseparation = - Vapproach x restitution

Where restitution is between zero and one.

In most cases, waiting for overlap before processing collisions is sufficient. The exception would be when the objects can move far enough in a frame that the overlap is unmanageable, or even missed entirely.

A cheap way of looking ahead is to find the closest points (which you probably get anyway from the collision test) and the approach velocity, and see if they predict an overlap in the next frame. It can give some false positives, but it's usually not noticeable.

[StratfordCanning]

Would you mind posting back with how you get on with this?  Maybe with a link?  If you do it in JavaScript I'll even host it for you!

[prushik]

Would you mind posting back with how you get on with this?  Maybe with a link?  If you do it in JavaScript I'll even host it for you!

 

Its all in C using SDL2 for graphics. You can checkout my code with subversion

svn co https://subversion.assembla.com/svn/highwayman/

 

If you do so, promise not to laugh at any bad code you might find, I know its not perfect. I have some comments in the code that say "//HACK" thats where most of my really bad code is. And last time I tried, it had some problems on Windows, however, I have fixed a lot of bugs, so maybe it works now. If you run Linux, then it should work well.

I didn't fix the collision resolution stuff yet, I've been really lazy this weekend and today I helped my friend move to a new apartment.

The code it licensed under the Beerware license, so you can do whatever you want with it.

[prushik]

Would you mind posting back with how you get on with this?  Maybe with a link?  If you do it in JavaScript I'll even host it for you!

I finally got around to implementing essentially exactly what you said. although I did not add any extra velocity for separation, which remains a problem. I think really the problem is the separation. Basically it behaves about the same as it always did now that I implemented that.

Sorry, I just lied: It does indeed behave much better, now that I understand what I need to use for the mass, I have collisions working both ways. So the code fixes TWO HUGE problems that I had before, collisions of two objects with greatly differing mass (1), and handling collisions when the the NPC collides with the player as opposed to the player colliding with the NPC (2).

 

For some degree of bounce, you would increase dv to allow for a separation velocity,

Vseparation = - Vapproach x restitution

Where restitution is between zero and one.

In most cases, waiting for overlap before processing collisions is sufficient. The exception would be when the objects can move far enough in a frame that the overlap is unmanageable, or even missed entirely.

A cheap way of looking ahead is to find the closest points (which you probably get anyway from the collision test) and the approach velocity, and see if they predict an overlap in the next frame. It can give some false positives, but it's usually not noticeable.

This is the remaining problem. My collision detection algorithm is not flawless, but it works well and I think should be fairly cheap CPU-wise. It would suffer from the problem you describe, but vehicles would have to be moving at absurdly high speeds for that to happen, and vehicles will reach a max velocity which should be far less than that. Also given that I don't intend this to be a game about high speeds, its more about power, this is not an issue that worries me.

However, what does worry me is how to find the separation velocity. I need them to separate. My collision detection returns 2 points, however, they are actually the same point, just given relative to each object involved in the collision.

I could use the velocity of the vehicles to determine separation, but this is flawed because, depending on how fast the vehicle is going, it may push them apart too far and make it appear that a collision has occurred too soon. I could maybe separate them checking factors of their velocity to see what is necessary to separate, but that would be expensive. Or, I could guess at a factor, but this would result in overlap, which would get the two stuck on top of each other.

I guess your "Vseparation = - Vapproach x restitution" method is basically the last method, right? and the first method is the same but the a restitution of 1.0, right? Is there some less brute force method that you can think of?

[EWClay]

If I understand what you are saying, you can detect a collision but you don't know how big the overlap is, and you might also not have a direction for the separation axis. If you have those things (they should come from the collision test) it is quite easy to work out the separation velocity; I've already given you the formula. Without them it's difficult to see a way to do it.

Correct me if I'm wrong there.

[prushik]

If I understand what you are saying, you can detect a collision but you don't know how big the overlap is, and you might also not have a direction for the separation axis. If you have those things (they should come from the collision test) it is quite easy to work out the separation velocity; I've already given you the formula. Without them it's difficult to see a way to do it.

Correct me if I'm wrong there.

Yeah, basically. Do you have any pointers on how to figure those out? Currently only a true/false is returned and a VEC2 is set to the point of contact.

Now, I'm a bit confused, at first I wondered even what kind of value the overlap would be, scalar, vector? but I guess either would work given that I also have the separation axis direction.

If I had those I could just multiply that by mass and add that as a force and they should separate, so I think that I understand what to do once I have that data. But how can I determine those in my collision detection? I'm not even sure what the separation direction should look like, perpendicular to the side of the vehicle?

[EWClay]

Use the separating axis theorem (SAT).

 

If the collision shapes are oriented bounding boxes you have only four axes to consider: the x and y axes of each box. You can just loop through them and find the minimum overlap. Overlap is a scalar and it's how far you would need to move the objects along the separation axis in order for them to not overlap anymore. If the minimum overlap is negative, the objects are not intersecting.

 

The axis with the minimum overlap is the one to use for impulses, and for moving the objects apart if you choose to do that.

 

The contact point is not that important unless you are using moments of inertia in the collision.

[prushik]

Use the separating axis theorem (SAT).

 

If the collision shapes are oriented bounding boxes you have only four axes to consider: the x and y axes of each box. You can just loop through them and find the minimum overlap. Overlap is a scalar and it's how far you would need to move the objects along the separation axis in order for them to not overlap anymore. If the minimum overlap is negative, the objects are not intersecting.

 

The axis with the minimum overlap is the one to use for impulses, and for moving the objects apart if you choose to do that.

 

The contact point is not that important unless you are using moments of inertia in the collision.

Of course, I should have known by your wording.

I was not using the separating axis theorem before, I was just checking if the corners were contained inside the other object.

I have SAT implemented now, and I see that it does a lot less comparisons, even in the case of a collision. However, it does more math.

I was under the impression that SAT was very efficient for complex shapes, but for simple shapes like rectangles, SAT is still efficient, but not as efficient as simpler methods. Comparing the code that I wrote using both methods, it looks like SAT is a lot more efficient, even in worst cases, should that be true?

Anyways, my implementation of SAT doesn't return anything but a true/false, but I understand how I should get the axis and the overlap amount. Now my next question is, is there an easy way to get the contact point using SAT?

[EWClay]

SAT is pretty fast for boxes, and also correct in all cases. You could have an intersection in which no corners were inside the other box.

There isn't really a contact point but an overlap region. However, what I do is test the boxes in turn and find the maximum extent of the other box against the axis being tested. After a final check that the point is inside the other box I have up to two points, which allows stable resting contact. But if you just want one you could take the average.

[prushik]

SAT is pretty fast for boxes, and also correct in all cases. You could have an intersection in which no corners were inside the other box.

There isn't really a contact point but an overlap region. However, what I do is test the boxes in turn and find the maximum extent of the other box against the axis being tested. After a final check that the point is inside the other box I have up to two points, which allows stable resting contact. But if you just want one you could take the average.

Right, but I'm fairly confident that those cases will never happen, and I would be happier with a fast algorithm that is correct in almost all practical scenarios than a slower one which is perfectly correct all 100% of the time. However, I'll be very happy if the 100% perfect solution is faster.

Actually, the incorrectness of the algorithm was a little bit useful for me, before implementing SAT, my game generated an NPC and placed it exactly on top of the player. since they were exactly the same size, no collision was registered, allowing me to drive away (as long as I drove perfectly straight) and then test collisions from different angles. Now that I'm using SAT, I need to generate the NPC elsewhere. (which I needed to implement later anyway)

 

I realized that after posting, there is no real contact point, the contact point is a bit of an illusion. However, I do need to choose a point somewhere in that region, since I need to apply the forces somewhere. The code that I am using right now actually still does both types of collision checking... SAT for separation axis, and the corner method for point of contact point. Obviously, that needs to be changed eventually. My old algorithm uses the point which is contained inside the other object as the contact point.

Although, my SAT implementation has some trouble. It finds collisions correctly, but does not give the overlap correctly, and does not return the correct axis.

 

My code looks like this if you want to look at it:

void SATgetMinMax(struct vehicle *obj, VEC2 *axis, double *min, double *max)
{
	double mina,maxa;
	VEC2 tmp,corner;

	setVEC(obj->img.w/2,obj->img.h/2,&tmp);
	relativeToWorld(obj,&tmp,&corner);
	addVEC(&corner,&obj->chassis.coord,&corner);
	mina=dotVEC(&corner,axis);
	maxa=mina;
	
	setVEC(-obj->img.w/2,obj->img.h/2,&tmp);
	relativeToWorld(obj,&tmp,&corner);
	addVEC(&corner,&obj->chassis.coord,&corner);
	if (dotVEC(&corner,axis)<mina) mina=dotVEC(&corner,axis);
	if (dotVEC(&corner,axis)>maxa) maxa=dotVEC(&corner,axis);
	
	setVEC(-obj->img.w/2,-obj->img.h/2,&tmp);
	relativeToWorld(obj,&tmp,&corner);
	addVEC(&corner,&obj->chassis.coord,&corner);
	if (dotVEC(&corner,axis)<mina) mina=dotVEC(&corner,axis);
	if (dotVEC(&corner,axis)>maxa) maxa=dotVEC(&corner,axis);
	
	setVEC(obj->img.w/2,-obj->img.h/2,&tmp);
	relativeToWorld(obj,&tmp,&corner);
	addVEC(&corner,&obj->chassis.coord,&corner);
	if (dotVEC(&corner,axis)<mina) mina=dotVEC(&corner,axis);
	if (dotVEC(&corner,axis)>maxa) maxa=dotVEC(&corner,axis);

	*min=mina;
	*max=maxa;
}

//Check for collisions with SAT
int SATXvehicles(struct vehicle *a, struct vehicle *b, VEC2 *over)
{
	int i;
	double overlap,
		mina,maxa,
		minb,maxb;
	VEC2 tmp,
		axis, saxis,
		corner;

	//Axis to check
	setVEC(1.0,0.0,&tmp);
	relativeToWorld(a,&tmp,&axis);
	
	//Find min/max values on axis
	SATgetMinMax(a,&axis,&mina,&maxa);
	SATgetMinMax(b,&axis,&minb,&maxb);
	
	//Check for overlap
	if (!Xline1d(mina,maxa,minb,maxb))
		return 0;
	else
	{
		overlap=minb-maxa;
		setVEC(-axis.y,axis.x,&saxis);
	}

	//Axis to check
	setVEC(0.0,1.0,&tmp);
	relativeToWorld(a,&tmp,&axis);
	
	//Find min/max values on axis
	SATgetMinMax(a,&axis,&mina,&maxa);
	SATgetMinMax(b,&axis,&minb,&maxb);
	
	//Check for overlap
	if (!Xline1d(mina,maxa,minb,maxb))
		return 0;
	else
	{
		if (minb-maxa>overlap)
		{
			overlap=minb-maxa;
			setVEC(-axis.y,axis.x,&saxis);
		}
	}

	//Axis to check
	setVEC(1.0,0.0,&tmp);
	relativeToWorld(b,&tmp,&axis);
	
	//Find min/max values on axis
	SATgetMinMax(a,&axis,&mina,&maxa);
	SATgetMinMax(b,&axis,&minb,&maxb);
	
	//Check for overlap
	if (!Xline1d(mina,maxa,minb,maxb))
		return 0;
	{
		if (minb-maxa>overlap)
		{
			overlap=minb-maxa;
			setVEC(-axis.y,axis.x,&saxis);
		}
	}
	
	//Axis to check
	setVEC(0.0,1.0,&tmp);
	relativeToWorld(b,&tmp,&axis);
	
	//Find min/max values on axis
	SATgetMinMax(a,&axis,&mina,&maxa);
	SATgetMinMax(b,&axis,&minb,&maxb);
	
	//Check for overlap
	if (!Xline1d(mina,maxa,minb,maxb))
		return 0;
	{
		if (minb-maxa>overlap)
		{
			overlap=minb-maxa;
			setVEC(-axis.y,axis.x,&saxis);
		}
	}
	
	copyVEC(&saxis,over);
	multiplyVEC(over,overlap,over);
	multiplyVEC(over,5.0,over);
	
	return 1;
}