The title of this post starts with "simple" because we can complicate it a lot. This is a very simple explanation of the collision detection.
The collision detection is used in graphical applications like games to know whether an object hit another object, like the character of the game against a wall or against other object. If this happens the character should stop, die, exploit...
It's quite important to make this part of the game precise and efficient, because it can ruin a game if it's not precise (the game loose a lot of of reality) and also if it's not efficient (it will slow the game).
Let's start by the shapes. We are going to use simple shapes. Points (x,y), Rectangles and Circles.
To define a rectangle we could use 2 points: the lower left and the upper right
To define a circle we will use the center point and the radius.
If we have 2 circles how could we know if they are overlapping one each other?
Just checking the distance between the two centers. If the distance is minor than the addition of the two radius, is because we have an overlap. If it's bigger we don't have overlap.
It seems easy, but how can we calculate the distance between two points?
Remembering the vectors of the math class, if we have two points:
A-------------------------->B
distance is the square root of the square of the difference of each coordinate.??
difX = B.x - A.x
difY = B.y - A.y
Dist = sqrt(difX*difX + difY*difY)
So we just have to check if this distance is minor than the addition of the radius. Easy. But we can do it better cos we know that the sqrt function is very expensive. So we can avoid it checking if the squared distance is minor than the square of the addition of the radius.
public float distanceSquare(Point a, Point b){
//use distance square to avoid use square root cos is expensive
float x = b.x - a.x;
float y = b.y - a.y;
return x*x + y*y;
}
public boolean circle2cirlce(Circle a, Circle b){
float sumRad = a.radius + b.radius;
return distanceSquare(a.center, b.center) < sumRad*sumRad;
}
That was really easy, but what if we have two rectangles? If we think a little about it, we can find a solution. But there is the Separating Axis Theorem SAT to help us. The theorem says that if two convex polygons are not overlapping, we can draw a line between them. Then using an axis that will be the normal of this line we can get the projection of the shapes in the axis and see that the projections do not overlap. Well is a quick explanation. If you want to know more about it just search Separating Axis Theorem on the Internet.
That theorem is very good to check collisions between polygons, because you just have to check the projections on the axis. One polygon has the same number of axis that of vertices's. And when you find two projections that don't overlap, you can finish the check. That makes this method very efficient.
But we are using a simple version of polygon. We are using rectangles. And they are always aligned with the axis X and Y. So for us should be much more easy. We just need 2 axis cos the projections are the same in the other two.
In this image we can see the projections in the axis. In this concrete case we could use x and y.
So one first approximation to the method to check if two rectangles are overlapping could be:
public boolean rectWithRectProjection(Rectangle a, Rectangle b){
float minX, maxX, minY, maxY;
//axis x (1,0)
minX = Math.min(a.downLeft.x, b.downLeft.x);
maxX = Math.max(a.downLeft.x+a.width, b.downLeft.x +b.width);
if(a.width + b.width < maxX - minX)
return false;
//axis y (0,1)
minY = Math.min(a.downLeft.y , b.downLeft.y);
maxY = Math.max(a.downLeft.y+a.height, b.downLeft.y+b.height);
if (a.height+b.height < maxY - minY)
return false;
return true;
}
In this case we are used the version that gives the width and the height of the rectangle.
This method is slow because uses the min and max functions that are very expensive. We can do it better just getting the points that can be overlapped in each case. Let's see how two rectangles can be overlapped. Depending on the side that is each one.
To avoid using max and min functions, we can just check this 4 possibilities. One for each axis of the rectangle. If we use the 2 points version of the rectangles we can write it like:
public static boolean rectWithRect(Rectangle2Points a, Rectangle2Points b){
return (a.downLeft.x <= b.upRight.x &&
a.upRight.x >= b.downLeft.x &&
a.downLeft.y <= b.upRight.y &&
a.upRight.y >= b.downLeft.y);
}
In this case we just check two points in each condition. This version is much more efficient. In each condition we are checking one axis (one side of the rectangle) left, right, bottom, top. Notice that all the conditions must be true. If one of this conditions is false we can assure that the rectangles are not colliding. So knowing this we can make this checking faster in some cases:
public static boolean rectWithRectCut(Rectangle2Points a, Rectangle2Points b){
if(a.downLeft.x > b.upRight.x)
return false;
if(a.upRight.x < b.downLeft.x)
return false;
if(a.downLeft.y > b.upRight.y)
return false;
if(a.upRight.y < b.downLeft.y)
return false;
return true;
}
We need to invert the major/minor operators cos now we are checking if not meet the condition. You can use NOT (!) instead if you want, of course.
Using the other version of rectangle it would be:
public static boolean rectWithRect(RectanglePointWH a, RectanglePointWH b){
return (a.downLeft.x <= b.downLeft.x + b.width && a.downLeft.x + a.width >= b.downLeft.x &&
a.downLeft.y <= b.downLeft.y + b.height && a.downLeft.y + a.height >= b.downLeft.y);
}
//FASTEST
public static boolean rectWithRectCut(RectanglePointWH a, RectanglePointWH b){
if(a.downLeft.x > b.downLeft.x + b.width)
return false;
if(a.downLeft.x + a.width < b.downLeft.x)
return false;
if(a.downLeft.y > b.downLeft.y + b.height)
return false;
if(a.downLeft.y + a.height < b.downLeft.y)
return false;
return true;
}
Getting the time of these algorithms with two rectangles not overlapping
PROJECTION
COLLISION NOT FOUND
Time:166993
NOT CUT
COLLISION NOT FOUND
Time:18404
CUT
COLLISION NOT FOUND
Time:2170
We can see that it's a big difference. Of course this difference between the NOT CUT algorithm and the CUT will only happen when the rectangles are not colliding, cos when we find that the rectangles are not colliding we finish the algorithm. But the good news are that in a game we usually have lots of objects and very few colliding. So considering this difference for every object in the game on every frame... it could be important.
If we want to check if a single point is overlapping a rectangle, the logic is quite similar. I'm not going to write the code here.
Now let's think how can we detect collisions between circles and rectangles. The first attempt is to use a similar algorithm than the one used to check two rectangles. And it could work in most of the cases, but not in all of them. Why? Because if we use the same algorithm we are treating the circle as if it were a square with the diameter as a side. Think in this case
Here we can see that if we consider the circle as a square, we have a collision. But it's a fake collision. Its cos this algorithm is not precise. So we need to change the algorithm to check this. One way to do this is find the closest point of the rectangle to the circle, and then check if the distance from this point to the center of the circle is bigger than the radius. But how can we find this closest point?
Yes, another time we have to check the axis. If the Y coordinate of the center of the circle is into the space used by the rectangle (look at the right circle), we have to use the Y coordinate of the circle to the Y of the closest point. Otherwise we will use the biggest or the fewest Y coord of the rectangle (depending if the circle is up or down). The same with the X. Once we have the X and Y of the closest point we can check the distance. Ah, remember that if we check the distance squared is more efficient.
public static boolean colisioCercleRectangle(Circle c, Rectangle2Points r) {
Point closest;
float closestX = c.center.x;
float closestY = c.center.y;
if(c.center.x < r.downLeft.x) {
closestX = r.downLeft.x;
}
else if(c.center.x > r.upRight.x) {
closestX = r.upRight.x;
}
if(c.center.y < r.downLeft.y) {
closestY = r.downLeft.y;
}
else if(c.center.y > r.upRight.y) {
closestY = r.upRight.y;
}
System.out.println(" closest x:"+closestX+" closesty:"+closestY);
closest = new Point(closestX,closestY);
return distanceSquare(c.center,closest) < c.radius * c.radius;
}
Well I think that's all. I just want to say that this is a very simple way to do this. We are using circles and rectangles, and the rectangles are always parallel to the axis X and Y. And of course in 3D the things are much more difficult. But this can work for a simple 2D game.
