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!

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.

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?

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?

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.

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?

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;
}