This page will discuss some methods behind handling the collision loop. We can all talk about how we WOULD program certian things without actually getting down to coding it. But, unfortunately, if you really want to make a game, you have to program things like this. I'll explain it as well as I can, and even include some formulas for you.

This page will not discuss seeing if objects are in collision within a given frame. This discussion is about detections of the actual point of collision and react accurately to them.

We'll be talking about two different kinds of collision detection: reflection and sliding. Reflection collision happens in games like billards, or grenades bouncing along the ground after you fire them. Sliding collision occurs usually on player controlled objects that strike a wall and continue sliding along the surface. Both types of collision use the same kinds of algebra to detect collisions, but use different loop methods and cover different circumstances.

The method I like to use for any kind of collision detection is to calculate an object's new position based on acceleration, velocity and other factors. Then I take the old position and connect them together as a segment. With that segment, I detect for collisions along its length during the frame, returning a 0.0 for a collision that happens immediately, to 1.0 where a collision occurs at the end of the current frame.

The kinds of collision I will assist with here are circle-line and point-circle

To handle collisions with circles and lines, there are two possibilities. The circle can collide with the line itself, or collide with the endpoints. You need to check for both circumstances.

You can assemble a polygon with one-sided lines and have an accurate working system.

(more here - algebra, cases to watch out, examples of what it can be used for, single-double sided lines)

Reflection collision

When a collision is reflective, the impact of the collision causes the object to bounce off. When an object bounces off a line, it uses the normal of the line to calculate a reflected velocity. When the collision is with a point, a normalized vector is drawn from the point collided with to the cneter of the circle at the point of collision, and the velocity is reflected off from that.

Multiple collisions within a single frame are handled like this: parse through all possible collisions, and detect for the collision that occurs first (smallest t). Move the object forward to that time, apply that collision's reflection, and repeat. Look for the earliest collision, move the object forward, etc. until no more collisions are detected. It shouldn't be mathematically possible for an object to get stuck if all collisions in a system are reflective, but a sliding object that isn't knocked away could trap the object in a snug position. But we won't go into that here. Not yet, anyway.

Sliding collision

When a collision is sliding, the velocity component of the travel segment that is contrary to the normal of the surface is absorbed. The rest of the travel segment is then used to continue the object on its way. Normals are drawn the same way in a point collision.

In the case of multiple collisions, where sliding collision is concerned, there is one important possibility to consider - the object could get stuck. Imagine a player trying to walk into a corner and doesn't stop, or tries to get around two points with not enough space between them. The player would stop, unable to move forward. To detect for this is basically pretty simple. Record the last obejct collided with when a collision takes place. If in the same frame, while applying the rest of the object's movement, a collision occurs with another object at time 0.0, check the resulting sliding effect. If it is contrary to the normal of the last collision, then the object is stuck. It's important to always calculate the sliding effect off from the original object's intended direction of movement, not off from any previous sliding effect, for accuracy (it's as if the moving object never collided with the last object and collided only with the new one all along).

Data storage

Lines are made up of the segment and the endpoints. A polygon is made up of vertices with segments connecting them. To reduce calculation, store the vertices and segments separately in the polygon structure so that collision isn't detected on the endpoints twice (this would happen if you detected for collision on the endpoints of a line in the same routine that you detect for a collision on the line itself)

Math

* Reflection off a line
* Reflection off a point
* Sliding off a line
* Sliding off a point

* Point-circle collision

// Sets global variable g_CollisionT to smallest time that a 
    collision takes place
// Initialize g_CollisionT to 2.0f before you call this routine repeatedly
// p_x0, p_y0 is the starting point for the travel segment
// p_xoffset, p_yoffset is the travel vector for the point
// p_cx, p_cy are the center for the circle
// p_radius is the radius of the circle
// This works for point-circle, circle-point (the result is the same as point-circle), 

//    circle-circle (add the radii), and even when both objects are moving (set 
//    appropriate p_xoffset, p_yoffset before the call)
bool PointCircleCollision(float p_x0, float p_y0, float p_xoffset, float p_yoffset 
						    , float p_cx, float p_cy, float p_radius)
{
	float A, B, C;
	float C1, C2;
	float t1;
	bool coll;


	// If point is moving away from circle center, there is certainly no collision
	if ((p_x0 - p_cx) * p_xoffset + (p_yo - p_cy) * yoffset ) > 0.0f )
		return false;


	A = p_xoffset * p_xoffset + p_yoffset * p_yoffset;

	// If A is 0, there isn't any movement - collision is impossible
	//  Actually, we use this value, which is necessary for extremely
	//  slow moving objects (in a billiard games that are close to 
	//  coming to a stop)
    If (fabs(A) <= 0.000001f)
		return false;


	B = 2.0f * ((p_x0 - p_cx) * p_xoffset + (p_y0 - p_cy) * p_yoffset);
	C = (p_x0 - p_cx) * (p_x0 - p_cx) + (p_y0 - p_cy) * (p_y0 - p_cy) - (p_radius 
		    * p_radius);


	C1 = (B * B) - (4.0f * A * C);
    C2 = (2.0f * A);

	// If C1 < 0, then a square root isn't possible, which means 
    a collision isn't possible
	If (C1 < 0.0f) Then
		return false;
    
	C1 = sqrt(C1);

	// Initialize
    coll = False;

	// The -0.001f's are for truncation
	// Look for the lesser t ONLY - based on negativity of C2
	if ( C2 > 0.0f )
	{
		t1 = (-B - C1) / C2;
		if ((t1 >= -0.001f) && (t1 <= 1.0f))
			if (t1 < g_CollisionT)
			{
				g_CollisionT = t1;
				coll = True;
				// Track objects collided with here or in calling
				//  function
			}
	}
    else
    {
    	t1 = (-B + C1) / C2;
    	if ((t1 >= -0.001f) && (t1 <= 1.0f))
	    	if (t1 < g_CollisionT) Then
			{
			    g_CollisionT = t1;
			    coll = true;
				// Track objects collided with here or in calling
				//  function
		    }
	}

	// If coll is true then there is a collision
    return coll;
}

* Circle-line collision

Continuation

I just finished writing a VB program with balls bouncing off from each other. It uses the "find first collision, advance everything to that point, apply collision, repeat until frame time consumed" methodology.

It currently tracks collisions between ball-ball and ball-line (edge of screen). It isn't possible for the balls to collide witht he endpoints of lines, since the edge of a ball cannot touch the corner of the screen. However, if I introduce polygons in the middle of the playfield, then colliding with an endpoint is certainly possible. This creates a design difficulty, becuase currently the ball-ball collision is handled using the PointCirlce collision function, and it is hardcoded to accept two ball objects as parameters. I suppose if I want to track ball-endpoint collisions, I could either rewrite the function more generally, or write a new one that expects to track only endpoint-ball collisions, even though it is using the same formula.

Basically what I am realizing is this. In a frame-time consuming collision method, you have to track the earliest time of the collision, what kind of collision it is, and what it is occurring between. The possibilities currently are:

• Bouncing ball and line
• Bouncing ball and endpoint
• Bouncing ball and bouncing ball
• Pushed circle and line
• Pushed circle and endpoint
• Pushed circle and bouncing ball
• Pushed circle and Pushed circle? Sure why not.

Bouncing balls apply reflective collision. Pushed circles apply sliding collision.

Each collision will be applied differently when detected. I think the collision routines themselves should expect to track these events, unless the actual formulas are in general functions (so that code isn't duplicated) and they return either a time, or a boolean with a time stored in a global

Deceleration - a new challenge

What if an object has a variable speed throughout, and we want to accurately represent the declerating speed at which two balls collide?

We would have to track a new event:

• Ball stopping

Because if we involve deceleration as part of the travel distance, two balls could collide if they've stopped and started going backwards. Detecting a ball stopping, then, advances everything forward to that point, and that ball is then not considered as moving in the next iteration.

I suppose an even greater challenge comes with two objects decelerating, and trying to generate a formula that accurately represents their position with each other, even though both could be at a different current velocity. The previous strategy was to subtract their movement offset to geernate one large movement for only one of the objects. I'm sure there's a formula for it, but it's going ot be pretty complicated. Hopefully, some variables cancel.

I'm also wondering how adequate it would be to adjust every ball's velocity at the end of the current frame. That way, we could simulate deceleration but still treat velocity as constant for a frame and avoid a complex formula. I tried it with a per-frame multiplier of 0.99 and it seems to work pretty well (with a per frame time of 10ms). It may be necessary in a case like this to handle the animation in 10ms increments to make the deceleration identical on all machines. If 10ms hasn't elapsed yet, that frame is ignored.

Also, a true game of billiards offers a new collision challenge:

• Ball-pocket

Each pocket can be represented as a stationary ball that, if collided with, makes the ball disappear.

Which brings to mind a representational possibility. Endpoints of lines could be thought of as balls that are stationary. If the collision then is simply treated as ball-ball, and the stationary flag of each ball is checked, then only the ball that is not stationary is affected and the collision to totally reflective upon the moving ball.

Update

Well, I have a makeshift billiard game going in VB, rendered with GDI.

I enjoyed most setting up the collision models, and parameterizing the circles and lines such that I can arrange them anyway I wish without having to do any special reprogramming. It wasn't very hard to add a status prompt or power bar, or get the cue ball to aim with the mouse, or place the cue ball.

I also set up some invisible collider balls for the holes, and rendered some larger ghost circles around them to make it look like the balls are actually going into a hole.

What I did not do is mark any of the balls, or make sure the player doesn't place the cue ball outside the play area or inside a ball or hole.

I like setting things up. I don't like that error checking stuff. Data structure and process design good. Error checking bad.