In this post I will talk about collision detection and avoidance algorithms. I will be talking about the algorithms that I used in Pigment (A 3d fps game) and my Android project (an Arkanoid clone).
In my Arkanoid clone (I will call it Good Child but it is not the final title :)), It is mostly the testing of a sphere (ball) with other spheres and polygons. In Pigment it is testing of a cylinder (player) with 3d polygons and ray testing (weapons, flag etc).
Let’s begin with Good Child, and the easier algorithm : collision detection of two circles in 2D.
Collision detection of two circles
Well, this is an easy one!
We have two circles with mid points of p1 and p2 and each have radius of r1 and r2. In this case distance between two circles must be greater than r1+r2 so they won’t collide, otherwise there is a collision. This works for higher dimensions too. You can drag green circle to test for collisions. In the case of Good Child, I am using this to testing for collision of ball with other circle objects such as circular bricks, arced walls and guards etc.
Testing circles is pretty easy and cheap operation, you can make it even cheaper by removing square root operation. Let’s say your original algorithm is like this.
function circleCollision(p1, r1, p2, r2){
xdiff = p1.x-p2.x
ydiff = p2.y-p2.y
distance = sqrt(xdiff*xdiff + ydiff*ydiff)
total_radius = r1+r2
return distance < total_radius
}
This should return true (if I didn't make a cs101 mistake). however sqrt is a usually very costly operation. however you can remove it in this case.
function circleCollision(p1, r1, p2, r2){
xdiff = p1.x-p2.x
ydiff = p2.y-p2.y
distance_squared = xdiff*xdiff + ydiff*ydiff
total_radius = r1+r2
total_radius_squared = total_radius*total_radius
return distance_squared < total_radius_squared
}
Instead of comparing a < b, we are comparing a^2 < b^2 which is the same thing (since we know both are positive).
Since it is a cheap way of testing if two thing collides or do not, it can be used before actual testing of two models. Let's say you have two very complex models, and collision testing of them is very costly. Before the actual test code, you can easily generate a boundary sphere for each model that completely surrounds the model and hit test this spheres instead. If this circle/sphere test fails then two objects does not hit other, otherwise they might but you can't know that before the actual collision detection algorithm. This method can save you a lot of cycles since majority of the items will fail the sphere test and you won't waste CPU on more complex test operations. Also instead of using a boundary sphere, you can use a boundary box and test those two boxes.
In this case, we only thought about stationary objects. Assuming the time is standing still, we can test if two circles are touching each other or not. However this is not always the case.
Collision detection for moving circles
In Good Child, currently all objects other than ball and user controlled guards are static. So I will assume only one of the circles are moving and other one is stationary. In computer games, movements are done in timesteps. Usually same as fps. On each 'tick', you move your objects a bit, then test for collisions. So you have a initial and final positions for each objects. To check for collisions, you have to think of all cases between those positions. If object collides in any of those points, then you must alter the final position in this 'tick' to evade collision. Let's show a graphic.
In this diagram, everything is animated so you can think I will simply check distance again on each tick and stop the ball (or bounce it by changing its vector) when distance is below r1+r2 again. However objects can jump each other if fps is low enough and you might miss the collision. This does not looks like correct for circles but think about a wall. A wall is usually a line (for 2d), if you are testing a fast moving bullet, it is pretty much guaranteed that bullet will be on one side of the wall in one tick and on the other side on next. As previously mentioned, you have to think for all possible positions that the object traveled on those tick.
So in previous animation it moves smoothly from 50,50 to 150,150. Let's assume that instead of moving smoothly, it moved same amount in only one frame. So we have a stage like this.
Now as you can see, circle 1 creates a shape like tube while moving. Since circle 2 touches this shape, then we can say that circle 1 hits the circle 2 if it moves from p0 to p1 in one frame.
Since human has excelent visual processing algorithms in their brain, we can see that two shapes touches. But it is not as easy for a computer to see that. To make things a lot easier for CPU, let's reduce to circle 1 to a point and increase radius of circle 2 by same amount!
(You can move objects around to test different cases)
This scene is same as the other but it is much easier to test for collisions. Basically if this line segment represents the path that the ball moves and the circle represent that the area that the line shouldn't touch. If they are touching, there is a collision. And to check collision, we have to do a...
Line Segment - Circle collision detection
This is a little more complex than two circles. Now we want to test if any point of this line segment is inside the circle.
And before that we should find the closest distance from this line segment to center of the circle.
And before that we should find the closest point on the line.
http://youtu.be/9ssV79Qi7mM?t=40s
"If you wish to make an apple pie from scratch, you must first invent the universe."
--Carl Sagan
So let's begin with the finding the point on this line segmeent that is the closest to circle. I will first post the code for that.
function closestPointToACircleFromALine(p0, p1, c, r) {
v1 = c - p0
v2 = p1 - p0
dot_product = v1.x*v2.x + v1.y*v2.y
len = v2.x*v2.x + v2.y*v2.y
t = dot_pruduct/len
if(t<0) t = 0;
else if(t>1) t = 1;
out.x = p0.x + t*v2.x
out.y = p0.y + t*v2.y
return out
}
And here is a canvas that shows how this algorithm works. Drag points to check for different cases.
Now, let's start explaining things. It might look complicated but it really isn't. Basically, all we use is a dot product. Dot products gives us a projection of one vector to another.
This algorithm creates two vectors, v1 and v2. v1 is vector from p0 to c and v2 is the vector from p0 to p1. Then it finds dot product of those two vectors. dot_product gives us the squared distance from out to p0. After that it is trivial, it finds t which is the 'weight' of out between p0 and p1. If t is 0, then out is on p0. If t is 1.0, then out is on p1. t can go below 0 or above 1 so we crop it to between those values to keep closest point between p0 ad p1. After calculating weight, it finds the position of out using v2 and p0 and returns it.
So how useful is this for finding collisions? The answer is distance from this point to c is smaller than circle's radius then there is a collision.
In this example you can move objects around to test the algorithm. Left Image is what our scene looks like, and right scene is the simplified form of this scene. Ball moves from p0 to p1 in one frame and the gray area on the left is the area that the ball covers. If it hits the object, then there is a collision. And on the right, the simplified scene, we find the point 'out' and calculate the distance to c. If it is below radius of ball + radius of object then there is a collision.
In this post I only talked about collision detection for two circles, on next posts I will dive into more about what to do when there is a collision.