Collision Detection

Here's what the end result is supposed to be like after implementing the algorithm. You can move around using the mouse or arrow keys: Here's the code.

General Form Functions

I was looking into collision handling and the obvious place to start I thought was using linear functions to describe both the movement vector and level geometry and then just solve for when the two functions equal each other to see if they intersect.
So if if the movement vector is f(x) and you have a line in the geometry g(x) then solving f(x) = g(x) would give you the x value when they intersect. This quickly runs into the problem of how to deal with vertical lines.
Using what most people would consider the normal way for a linear function to look i.e. y = a * x + c would have both a and c approach infinity as the line becomes more vertical.

This is called the slope-intersect form where "a" describes the slope of the line, the higher "a" the steeper the slope is and "c" is the point where the line intersects the y axis. Thus "slope-intersect".

The following line for example cannot be described using the slope-intersect form:

fig 1
fig 1

Here "a" would be undefined. Same with "c" as it would intersect the y axis either infinitely positive or negative direction.
We could get around this by formulating the function using what's called the general form instead of the slope-intersect form. General form functions looking like this:

a * x + b * y = c

Note that "a" and "c" in this case are not the same as "a" and "c" in the slope-intersect function in that "a" does not represent the slope and "c" does not represent the point where the function intersects the y axis.
Using the general form we could define a function for the above line as:

x = 20

Meaning x is always 20 regardless of y.
So how do we get there? Let's start with the slope-intersect form. I won't go into detail on how to derive the formula but in order to find a slope-intersect equation describing a line you pick two points on the line and then use this formula:

y = dy/dx( x - x1 ) + y1

Where dx and dy are the change in x and y between the two points and x1 and y1 are the coordinates for one of them, it doesn't matter which. Let's look at two points on this line:

fig 2
fig 2

Here the change in x between the lower left point and the top right point is 5 and the change in y is 10. For x1 and y1 we pick the the lower left point, 10 and 30. Putting the numbers into the formula gives us:

y = 10/5( x - 10) + 30

Simplifying that gives us:

y = 2x + 10

So a = 2 and c = 10
We run into a problem when dx approaches 0 since we can't divide by 0. So let's rephrase the equation for the slope-intersect form to where we don't have any division by multiplying both sides with dx:

dx * y = dx * dy/dx( x - x1 ) + dx * y1
dx * y = dy ( x - x1 ) + dx * y1
dx * y = dy * x - dy * x1 + dx * y1

Moving things around gives us:

dy * x - dx * y = dy * x1 - dx * y1

On the right hand side of the equation we only have constants so we can bundle them together as a constant called "c" and write it as:

dy * x - dx * y = c

Which is the general form for linear equations. So picking two points on the vertical line:

fig 3
fig 3

And using the formula:

dy * x - dx * y = dy * x1 - dx * y1

Give us a dx of 0, a dy of 10 and then let's pick the lower point for x1 and y1 values:

10 * x - 0 * y = 10 * 20 - 0 * 10

This simplifies down to x = 20 which is what we wanted. Now how does this help us? Well I found that if you have a general form function and you want to see if it intersects a line then you take the coordinates for the two end points on that line, input them into the function and see if the result falls on different sides of that functions c value. If it does then they intersect.
Using the line in fig 2 we first calculate a general form function for it:

10 * x - 5 * y = 10 * 10 - 5 * 30
10x - 5y = -50

Let's say we want to find if it intersects this red line:

fig 4
fig 4

If we input the coordinates for both of the extreme points on that line to the left hand side of the equation:

10 * -10 - 5 * 40 = -300
10 * 30 - 5 * 40 = 100

In neither case is c the same as c for the function we're testing against which was -50 but they fall on opposite sides of it. Further more if we want to know where on the red line the intersection happens we first calculate the length between these two values:

-300 - 100 = -400

So the distance between them is 400. We don't care that the result is negative. Though we could take the absolute value it won't matter because the signs will cancel out in a later step.

And then calculate where the original c falls on this line in percent. To do that we pick one of the points, lets say the left one, and calculate how far apart the left one's c and the expected c of -50 is.
The left point had a c of -300 and to find how far -50 is from -300 we just subtract them from each other:

-300 - -50 = -250

So we get a distance of 250 between -50 and -300. Again we don't care that the result is negative because we'll get rid of the signs shortly.

So on an interval of 400 the point of intersection falls 250 counting from the left point. However this is just some abstract value regarding the c of the equation and doesn't say anything about what coordinates we land on. But if we calculate what percentage it represents on the length of the red line:

-250 / -400 = .625 = 62.5%

Notice that here the signs cancel out. This always happens and is why we won't bother with absolute values.

Now if we take 62.5% of the line's length and see where that gets us from the left most point we should get the coordinates for the intersection. The line went from x = -10 to x = 30 so the length in the x direction is 30 - -10 = 40.

40 * .625 = 25

So we add 25 to the left points x coordinate. The line's position doesn't change in the y direction so y will still be 40.

-10 + 25 = 15

So the intersection should happen at x = 15 and y = 40. We can test this by inputting those two values in the left side of the equation and see if the result is -50. If so it's a valid point on our line:

10 * 15 - 5 * 40 = -50

So since x = 15 and y = 40 are valid points on both the blue horizontal line and the red diagonal one they must then intersect.

Using this for collision detection

Now let's say that blue line in fig 4 is our movement vector, or the direction that we're moving in, and the red line is a wall we might collide with. This only tells us if our movement vector intersects that line at some point at all no matter how far away. What we want to know is if our movement vector intersects the line during a single frame, that is between a starting point and another end point.

To find that out we have to do another run where we invert the conditions and treat the wall line as a function and test if it intersects between our starting point and end point.

fig 5
fig 5 Displays our players movement during a single frame. We have a starting position of x = 5 and y = 20 and an end position of x = 20 and y = 50. The red wall line now has become a function describing the walls direction that goes on infinitely.

The reason for turning the wall into a function is that we can only test if a function intersects a discrete line. Not if two discrete lines intersects each other, that requires us to break it into two steps.

If these two tests both show intersection then we can be certain that a collision has occurred. We can then save the percentage we calculated of where the intersection happened between our start and end point to calculate the exact position for the collision by multiplying that percentage with the distance to get from the start to the end position.

Wall sliding

Let's consider this scenario:

fig 6
fig 6 Here the red player is moving from position 1 to position 2. The wall is the black line and the players motion is completely in line with the wall and because of that the function describing their motion will be exactly the same. The player should be a point and the wall a one dimensional line but they've been given thickness for clarity.

Now will the player collide with the wall? To figure that out we would create a function describing the wall's direction and then compare the "c" values from position 1 and 2 to that functions "c" value. If the values fall on opposite sides of the functions "c" value there could be a collision.
Because position 1 and 2 are located exactly on the line of the wall their "c" values will be exactly the same as the wall function's "c" value and since our function for determining if a value is in between two others looks like this:

bool inbetween( const double start, const double middle, const double end )
	if( middle >= start && middle <= end ) return true;
	if( middle <= start && middle >= end ) return true;
	return false;

Where we use =< and =>, that equal sign and the fact that all "c" values are the same will mean that it'll be considered a possible collision. But where will the collision occur?
Since the steps for determining the point of collision involves subtracting the "c" for position 1 from the "c" for position 2 and those two are the same we'll end up with a value of zero and as a result a division of zero if you look at the equations for fig 4.
So does this mean that we should not count it as a collision? Let's look at another scenario:

fig 7
fig 7 Here again the player's motion is inline with the top horizontal wall of the blue square but he would also be colliding with the very top edge of the left hand vertical wall so should we stop the player at position 3?

Here we would have a collision against both the top and left wall, so do we stop the player at the left wall? I want to implement wall sliding into this game, where the player could be pressing into a wall and still move along it. If we were to stop the player at the vertical wall in this example they'd get stuck every time they hit the very edge of a square which would happen repeatedly if they were moving along a group of contiguous squares.

fig 8
fig 8 Three blue squares are lined up next to each other and our red player is sliding along them. The vertical walls shouldn't be accessible from the outside and if we were to collide against them the player would get stuck on positions 3 and 4. Instead we would want him to move along the walls to position 2 without stopping.

What we'll do instead is create a special condition where we detect that we've collided with a wall and that we are moving parallel with it and then allow the player movement even if we've say collided with the vertical wall as in the above example.
We'd then have three different collision outcome, a collision happened, no collision happened and a collision happened but we'll ignore it since we're sliding along the wall.


The procedure for seeing if a vector goes between two points then boils down to:
1. Express a vector as a general form linear equation and calculate the "c" or right hand value for it.
2. Pick two extreme points on another line we want to test for collision against and input the x and y values for these two points into the equation from step 1. to get two new "c" values.
3. See if the c from step 1. falls in between these two new c values from step 2. If it does our vector intersects between the two points. If not then there's no collision.
4. Calculate the difference between the two c values from step 2. If it's almost 0 then the two lines are parallel and we're sliding against the wall.
5. If we were not sliding along the wall then we must be colliding with it.
6. If the programmer wants to know the point of collision we use the length between the c values for the end points from step 4. to get a percentage of where the function's c falls between them.

In this code the arguments x1, y1 and x2, y2 corresponds either to the coordinates for the extreme points of the red line in fig 4 or to our start and end position in fig 5. So for the red line they would be -10, 40 and 40, 40 respectively.
xpos and ypos would be any point on the blue line in fig 4 corresponding to say the current position of our player and dx, dy is our player's movement vector. The function then returns true or false for if the vector intersects between the two supplied points.
If the last argument *returnprc is not NULL then a percentage corresponding to where in between the two points the intersection happens will be calculated and put in returnprc.
"Step" that you see to the left of the code corresponds to the six steps outlined above. This will be used throughout the tutorial.

	enum collisiontype collision_intersection( const double x1, const double y1, const double x2, const double y2, 
			const double xpos, const double ypos, const double dx, const double dy, double *returnprc )
1.		const double c = xpos * dy - ypos * dx; 
2.		const double const1 = x1 * dy - y1 * dx;
2.		const double const2 = x2 * dy - y2 * dx;

3.		if( !inbetween( const1, c, const2 ) ) return NO_COLLISION;

4.		const double length = const1 - const2;
4.		if( fabs( length ) < .0001 ) return WALL_SLIDE;

6.		if( returnprc != NULL ) {
6.			*returnprc = ( const1 - c ) / length;

5.		return COLLISION;

Choosing which side to test against

A square has four sides but in order to speed things up we won't test for collision against all of them. Instead we'll pick the two sides closest to us, which are the only ones we can collide with. First getting the closest in the Y axis then in the X axis:

fig 9
fig 9 The red player is closest to the top and left wall. So we'll only test for collision against those since he can't reach the other two without going through these.

This will be done by the get_walls() function which I won't go into but should be simple to understand. It will return an array of size [2][6] which is [ number of returned walls, which is a maximum of 2 but could be 1 ][ 2 coordinates for one end point of the wall and 2 coordinates for the other end point + the 2 vector components of the wall]. The vector components are equivalent to treating the wall as moving from one of it's end points to the next, for example a horizontal wall 10 pixels long would have an X component of 10 and a Y component of 0. These are then the 6 values associated with each wall:


It also returns an int which is the numbers of walls it's put in the array so either 1 or 2.
Also note that all walls will be specified in a clockwise order. That is the top wall will first have it's left end point and then right end point, the right wall will have first it's top end point and then it's bottom end point. This will become important later on.

fig 10
fig 10 The way the walls are returned.

Relative motion

Another thing we need to add to this is relative motion. Consider the following scenario where two squares are moving at the same time and crossing each other's paths:

fig 11
fig 11 During a single frame two squares will cross each other's paths.

fig 12
fig 12 If we first move the red one without considering the movement of the blue one...

fig 13
fig 13 And then move the blue one. The result will be that they both will miss each other.

fig 14
fig 14 While they really should have collided in the middle of their motion.

The solution is to subtract the other square's movement vector from the one we're currently testing giving us the relative motion and allowing us to treat other squares as standing still while still accurately solving the collision.
So starting with the same scenario we first take the blue squares movement vector and subtract it from the red one. What this essentially does is invert it and then places it at the end of the red squares own movement vector:

fig 15
fig 15

The combined movement vector then is the relative movement we've been looking for:

fig 16
fig 16 The gray arrow is the relative movement.

And doing the collision detection using the relative movement shows us that the red square will collide with the blue one after traveling a little less than half the length of the relative vector:

fig 17
fig 17 The starting position of the squares. Red now uses the relative movement and the blue one is standing still.

fig 18
fig 18 The red one collides after traveling less than half of the relative movement.

We would now repeat the procedure for the blue square.

Now you might say that the relative movement would place the red square in a position where it shouldn't be. In the above example it would be moved straight right while it's actual motion should be down right, just not the full length of it's movement vector.
But we don't use the relative vector to actually move the squares, we just use it to calculate how far along the relative vector we can move before a collision occurs. Let's say that a collision occurs after 40% of the relative motion, then that holds true for the original vector as well. So then we go back and decrease the red squares own movement vector by 60% and that's where we'll end up actually placing the red square at the end of the frame.

The code for calculating the relative motion is simple, "me" is the current square we've selected and "other" is one that we're testing for collision against:

const double rdx = me->dx - other->dx;
const double rdy = me->dy - other->dy;

Simplifying box collision

In order to use this to test for collision between boxes we first shrink one of the boxes down to a point. This is to allow us to describe this box's motion using a single function. Otherwise we would have to test four different points corresponding to the four corners of that box.
The way we do this is to simply take one of the box's dimensions and adding them to the other box that we're testing for collision against. This can be visualized as sweeping the first box along the borders of the second one then reducing the first one to a point.
The red box in this example would represent our player character and the blue box an obstacle in the level.

fig 19
fig 19

This is called taking the Minkowski sum of the two shapes.

Now we can describe the motion of the red point as a function and test it for intersection against the sides of the larger blue square.

In this code "me" is the current square we've selected and "other" is one of many squares we're testing against. x1 and x2 are then the x coordinates for the left and right side of the blue square in fig 19 and y1 and y2 are the top and bottom y coordinates.

//Calculate the four corners of the cube we might be colliding with
//and increase it's size by out size thus allowing us to treat ourself as a point
const double x1 = other->x - other->halfsize - me->halfsize;
const double x2 = other->x + other->halfsize + me->halfsize;
const double y1 = other->y - other->halfsize - me->halfsize;
const double y2 = other->y + other->halfsize + me->halfsize;

Putting it all together

So now let's look at how we're going to check for collision between the player and the walls of a Minkowski square.
1. First we check if we're actually moving. If not then there's no point in checking for collision during movement.
2. Calculate the relative speed between us and the other square.
3. Check that the relative speed isn't zero. If it is then we're both moving in sync and thus standing still relative to each other, so we can't collide.
4. Start testing each wall in the Minkowski square.
5. Check if the relative movement vector intersects the wall's two end points.
6. If it doesn't then there can be no collision.
7. If it does but we're moving parallel to the wall we detect that as a wall slide. This takes precedence over collisions with any other wall and means we should allow the movement regardless. So we set collision to false and stop testing for further collisions with this square.
8. Check if the wall's vector intersects between our current position and where we're trying to move to.
9. If it doesn't then there can be no collision with this wall.
10. If it does we calculate in percent where along the relative movement vector the wall intersects.
11. Check if this value is less than it was previously. Each collision with a wall sets the percentage of where along the movement vector the collision happened and we want the wall that stops our movement closest to our player. The initial value we check against is 1 meaning 100% meaning the whole of the movement vector.
12. We will also return which wall in our Minkowski square we've collided with. This will be used to change our speed as we'll get into later.
13. Set a flag that a collision has occurred.
14. If a collision occurred then we would have gotten a percentage of where on the relative movement the collision happened. This percentage is is the same as where the collision happened on our own movement vector so we multiply our movement by that percentage to shorten it. This will put us just at the edge of the wall.

1.	if( fabs( *dxme ) < .001 && fabs( *dyme ) < .001 ) return false;

2.	const double rdx = *dxme - dxother;
2.	const double rdy = *dyme - dyother;

3.	if( fabs( rdx) < .001 && fabs( rdy) < .001 ) return false;

	bool collision = false;
11.	double prcshortest = 1;
4.	for( int i = 0; i < nbrwalls; i++ ) {
		//Put the coordinates in local variables to make things more legible 
		const double p1x = walls[ i ][ X_COORD_1 ]; 
		const double p2x = walls[ i ][ X_COORD_2 ];
		const double p1y = walls[ i ][ Y_COORD_1 ];
		const double p2y = walls[ i ][ Y_COORD_2 ];
		const double dxwall = walls[ i ][ X_VEC ]; 
		const double dywall = walls[ i ][ Y_VEC ];

5.		const enum collisiontype collwall = collision_intersection( p1x, p1y, p2x, p2y, xme, yme, rdx, rdy, NULL );
6.		if( collwall == NO_COLLISION ) continue;
7.		if( collwall == WALL_SLIDE ) {
7.			collision = false;
7.			break;

10.		double prcmove;
8.		const bool collvec = collision_intersection( xme, yme, xme + rdx, yme + rdy, p1x, p1y, dxwall, dywall, &prcmove );
9.		if( collvec == NO_COLLISION ) continue;

11.		if( prcmove > prcshortest ) continue; 
11.		prcshortest = prcmove;

12.		*returnwallnbr = i;

13.		collision = true;
13.	if( collision ) {
14.		*dxme *= prcshortest;
14.		*dyme *= prcshortest;

13.		return true;

Solving intersecting boxes

Things never quite work out the way you want them to and we might end up with a situation where two squares are more or less inside of each other and our algorithm is only able to detect collisions from outside of a square, so we have to have a way to push the player outside. To do this we have to find the wall in the Minkowski square that's closest to our player and to do that we're going to flip each wall's vector 90° counter clockwise, then see if this new orthogonal vector intersects the wall and if so where. The intersection that happens closest to the player represents the shortest distance to push him outside the square.

fig 20
fig 20 The red player is inside the square's black walls. We've taken those walls and flipped them 90° counter clockwise, giving us the four blue vectors extending from the player's position. All intersect their respective walls and we can see that the top one intersects it's wall closest to the player meaning that this is the shortest path to push the player outside the square.

fig 21
fig 21 Here none of the blue vectors intersects their walls meaning that the player is outside the square.

In order to create a new vector that's orthogonal to another one you flip the X and Y components of the vector and invert one of them, multiplying it by -1. This is were it's important that we we returned the end points for the walls in a uniform order as we did above, running clockwise around the square. By doing so we know which component of the walls vector to invert in order to make the flip counter clockwise to the original vector. Inverting the wrong component would mean that the orthogonal vector went in the wrong direction and did not intersect the wall even if we were inside the square.

We now know what distance to move our player to place him outside the square but I ran into a problem while doing this. The player can be found to be inside any number of squares during one cycle of doing collision detection. If you immediately change the player's X and Y coordinates each time he's detected as being inside a square this would cause the squares to jump or jitter about occasionally. I got rid of this by buffering all the changes in position into an x and y offset value.
If the player was found to be inside 3 squares then I wouldn't change his X and Y coordinates 3 times during collision detection. Instead I'd create 3 small movement vectors each corresponding to the movement required to get the player outside the 3 squares. Then I'd add these three small vector to an xoffset and yoffset value which would be added to the players position after all collision detection is done. Why this solves the jittering I have no idea but it does.

Another feature I want to add is that when we're detected as being inside the square we want to stop the player from moving back inside after we push him out of it. However if the player is moving away from the square we want to allow that movement.
To do this we'll take the dot product between the orthogonal vector and the player's movement and if it's below zero that will mean that the player is moving into the wall so we'll stop his movement but if it's above zero he's moving away so we'll allow the movement.
The way this works is that if the angle between two vectors is above 90 degrees their dot product will be negative and since the orthogonal vector is pointing away from the wall then if the dot product between it and the player's movement is negative the player's movement must be pointing into the wall.

fig 22
fig 22 The blue vector is the orthogonal one from previously. The red one is the player's movement vector. Since the angle between them is below 90° their dot product will be greater than zero so we would allow the player to move away from the wall in the direction of the red arrow.

fig 23
fig 23 Here the angle between the vectors is greater than 90° meaning their dot product will be less than zero so now we would reset the player's movement vector to zero to stop him from moving back into the square.

It's also worth pointing out that in fig 22 and 23 the player would be detected as being inside the square even if he's just at the edge of one of it's walls but the same principle would apply no matter how far into the square he was.

Putting all of this together into code:
1. For each wall in the Minkowski square do the following.
2. Using the vector describing the wall turn it 90° counter clockwise to create a new vector that's orthogonal to the wall.
3. Check if the wall is intersected by the orthogonal vector coming from the player's position. If it isn't then we can't be inside.
4. Check if the orthogonal vector is intersected by the wall's vector. If it isn't then we're not inside the square.
5. If it is record where in percent along the orthogonal vector the wall intersects.
6. Compare this value to any previous one. We want the wall that intersects it's orthogonal vector closest to our player since this represents the shortest distance to push the player outside the square. We initialize this value to 1 meaning 100% since all collision will occur at or below this.
7. Return which wall we've collided with. To be used later to set our speed.
8. Set a flag that we've been determined to be inside the square.
9. If we've been detected as being inside the square we need to recreate the orthogonal vector for the wall that was the closest to us.
10. Then multiply that vector by the percentage where the wall intersected it. This gives us a shorter vector which if we follow would takes us just to the edge of the wall and places us outside the square. This value is added to a buffer where all possible inside collision results are stored.
11. We then need to check if the player's movement is going into the square by taking the dot product between it and the orthogonal vector.
12. If it is then we zero all movement. If not then the player will be free to move away from the wall.

8.	bool inside = false;
6.	double prcshortest = 1;
1.	for( int i = 0; i < nbrwalls; i++ ) {
		//Put the coordinates in local variables to make things more legible 
		const double p1x = walls[ i ][ X_COORD_1 ]; 
		const double p2x = walls[ i ][ X_COORD_2 ];
		const double p1y = walls[ i ][ Y_COORD_1 ];
		const double p2y = walls[ i ][ Y_COORD_2 ];
		const double dxwall = walls[ i ][ X_VEC ]; 
		const double dywall = walls[ i ][ Y_VEC ];

2.		const double xortho = dywall;
2.		const double yortho = -dxwall;

3.		const enum collisiontype collvec = collision_intersection( p1x, p1y, p2x, p2y, xme, yme, xortho, yortho, NULL );
3.		if( collvec == NO_COLLISION ) continue;

5.		double prcinside;//Where along the vector the wall intersects. In percent.
4.		const bool collwall = collision_intersection( xme, yme, xme + xortho, yme + yortho, p1x, p1y, dxwall, dywall, &prcinside );
4.		if( collwall == NO_COLLISION ) continue;

6.		if( prcinside > prcshortest ) continue;
6.		prcshortest = prcinside;

7.		*returnwallnbr = i;

8.		inside = true;

8.	if( inside ) {
9.		const double xortho = walls[ *returnwallnbr ][ Y_VEC ];
9.		const double yortho = -walls[ *returnwallnbr ][ X_VEC ];

10.		*xoffset += xortho * prcshortest;
10.		*yoffset += yortho * prcshortest;

11.		const double dot = *dxme * xortho + *dyme * yortho;
11.		if( dot < 0 ) {
12.			*dxme = 0;
12.			*dyme = 0;

8.		return true;


We will also modify the speed to facilitate wall sliding. To do this all speed going into the wall should be removed at collision and only the part of the speed that goes along the wall should be retained. This can be though of like projecting the speed vector back to onto the wall:

fig 24
fig 24 Line 1 is our speed when colliding with the purple wall. The speed we want is line 2 and you can think of that line like shining a light at line 1 and getting a shadow of the speed vector projected onto the wall. That shadow vector will naturally be aligned with the wall and will also be smaller than the original speed.

This can be done through the following steps:
1. First we'll check if the speed is going into the wall or away from it using the dot product. This is the same test as we did for the player's movement vector when he was detected as being inside the square above. If the speed is pointing away from the wall we won't modify it so as to allow the player to escape from the wall.
2. Change the wall's vector into a unit vector. That is a vector whose magnitude is 1 "unit" in this case 1 pixel. This is done by dividing each component of the vector by the vector's magnitude which is the same thing as the wall's size.
3. Take the dot product of the speed vector and the new unit wall vector. The result will be a magnitude or length corresponding to a shadow or projection of the speed onto the wall. If we had not created a unit vector in step 1. we'd not get a magnitude from the dot product.
4. Get the sign, + or -, from the dot product. This is important because when we created the wall vector we could make it point in two different directions depending on which end point of it we make the vector start from. This in turn affects if the shadow will be point in the same or opposite direction of the wall vector. And if they're pointing in opposite directions we not only need to modify the wall vectors magnitude but we also need to flip it 180 degrees in order to calculate our final speed.
Luckily as stated above if there's more than 90 degrees between two vectors the dot product will be negative and we can use this to invert the final calculated speed. I'll explain this more below.
5. Let me explain this equation:
We want to project the speed onto the wall so we know that the resulting vector components of the projection should have the same relationship as the vector components of the wall. I.e. if the wall's components are x = 1 and y = 2 then we know that whatever the projected vector might be it's y component must be twice as large as it's x component. Otherwise the projection wouldn't be aligned with the wall.
We then turn to Pythagoras theorem. The magnitude of a vector can be seen as the hypotenuse in a triangle with the catheti being the components of that vector. The magnitude is the same as the length of the wall so we'd then have:

dxwall^2 + dywall^2 = length of wall^2

And we want to modify dxwall and dywall to equal the magnitude of the projected speed. We call this modifier value, which is a precentage, "x" and we get the equation:

( x * dxwall )^2 + ( x * dywall )^2 = length of projection^2

We simplify this:

x^2 * dxwall^2 + x^2 * dywall^2 = length of projection^2
( dxwall^2 + dywall^2 ) * x^2 = length of projection^2
x = sqrt( length of projection^2 / ( dxwall^2 + dywall^2 ) )

x is then what we call "prcmod" in the function. We now know how much we need to change the two vector components of the wall in order to create a vector whose length is the speed projected onto the wall.

6. Combine the wall's vector components and the value from step 5. together with the sign from step 4. to create a new speed.

	void speed_mod( double *xspeed, double *yspeed, const double dxwall, const double dywall )
1.		const double dot = *xspeed * dywall + *yspeed * -dxwall;
1.		if( dot > 0 ) return;

2.		const double lengthwall = get_magnitude( dxwall, dywall );
2.		const double unitdxwall = dxwall / lengthwall;
2.		const double unitdywall = dywall / lengthwall;

3.		const double magspeedproj = *xspeed * unitdxwall + *yspeed * unitdywall;

4.		const int sign = ( magspeedproj > 0 ) ? 1 : -1;

5.		const double prcmod = sqrt( ( magspeedproj * magspeedproj ) / ( dxwall * dxwall + dywall * dywall ) );
6.		*xspeed = prcmod * dxwall * sign;
6.		*yspeed = prcmod * dywall * sign;

Just to explain step 3: Below we have calculated the wall vector as running from it's left side to it's right side, so the purple arrow is our wall vector and it's pointing right but the projected speed, labeled 1, is pointing left. Therefore we not only need to shrink the size of the wall's vector down to get the projected speed but we also need to flip it 180 degrees. The dot product, labeled 2, will in this case be negative. So we just detect that and then multiply the wall vector's components by -1 to flip them and thus the vector in addition to shrinking it.

fig 25
fig 25 Our speed is labeled 1, the dot product labeled 2 and the wall vector is the purple line.

fig 26
fig 26 By taking the dot product in fig 25 we can imagine it as taking the wall and speed vector and putting them end to end and seeing where the speed vector's shadow falls. Since the angle between the speed and wall vectors are more than 90 degrees the resulting dot product will point in the opposite direction of the wall vector. We can know that this is the case because the dot product will be negative.

fig 27
fig 27 Here we have the opposite case to fig 26. The resulting dot product points in the same direction as the wall vector.

fig 28
fig 28 If we place the speed and wall vector end to end the angle between them is less than 90 degrees. The dot product will then be positive and point in the same direction as the wall.


I hope someone might find this useful and not too confusing. There's been many false starts with this approach and I've modified it several times. This tutorial has therefore been written in fits and starts and might come off a bit scatter brained. To make up for this I've extensively commented the source code located here. Maybe this is not the best way to do collision but I find it to be conceptually simple and easy to explain and I think the source code it pretty light compared to other ways of doing collision. Several steps could be simplified if one always assumed axis aligned squares, which is what's currently implemented but I intend to add diagonal walls at some point and so the algorithm was made so that those should be supported without significant modification.