Abstract
The aim of collision detection algorithms is to check object bodies to know whether they are intersected or not. Like in a car racing game, you want to know if two cars crashed to do a specific action, or in strategic games, you want to take action when a bomb reaches a building, etc.
The goal of this paper is finding the solution to this problem using a new algorithm and by using and developing predefined equations and algorithms.
Keywords: strategy game algorithms, object boundaries, collision detection, objects intersection, and computer graphics.
Introduction
In strategic games, developers use a plane as the ground of the game. On this ground, you will find the game objects. The plane is divided into blocks; each block has handlers for the objects included in it. As figure 1 shows, the plane is divided into a block (not divided actually) so the developer has to check each object with all other objects on the same block after each movement of the object to see if they are overlapped or not.
Figure 1. All objects in one block
So if there are two objects on the same block, one checking iteration is needed, but if there are three objects, the check is done three times, and if there are 100 objects, they will be checked 4950 times; this means that the algorithm runs 4950 times, and so on.
C= <span style="FONT-FAMILY: Symbol; FONT-SIZE: 9pt">å</span>N from 1 to N-1
Where C is the number of iterations to run the algorithm on a specific block, and N is the object count on this block.
Don’t forget that every time you increase the number of blocks, you will increase the count of loops on these blocks and decrease the count of checks in each loop, so you should balance between big and small block sizes. Remember that if the object body is distributed onto more than one block, all these blocks should contain a handler for this object. So here the focus is on working with two objects only. The algorithm returns a logical value (boolean): true if two objects intersect, false in other cases.
Object boundaries
The introduction section shows an outdoors environment that affects the algorithm. In this step, a new concept appears (object boundaries). Each object must be collected in a mathematical shape to run algorithms on this shape not on the object’s mesh, because if we work on the model itself, we will work on a lot of equations that represent that model. Don’t forget that the algorithms shown here are under a strategic game atmosphere so the speed of the algorithm may be more important in most cases than best and accurate results from the algorithm. So remember always that we want to solve the problem even in 90% of test cases, but in the required time, instead of solving all the test cases in more time. Remember also that if you have dozens of objects you may run this algorithm 100 times in the frame, 2500 times in a second, plus other algorithms in that game.
Figure 2. Two unbound objects
If we have two objects as in figure 2, we need to include these two objects in geometrical shapes to have the ability to apply geometric algorithms on them. Two choices appear now as follows:
- As figure 3 shows, the first option is putting the two objects in spheres.
Figure 3. Objects in spheres
- Putting them inside two cuboids as shown in figure 4.
Figure 4. Objects in cuboids
Sphere algorithms
If we work with circles or spheres, it is simpler than cuboids. Each object has an X, Y, and R (radius of its circle).
Figure 5. Use sphere as the body container
If (L < r1+r2)
Then
2 objects intersect themselves
Return true
Else
2 objects don’t intersect themselves
Return false
Where L is the distance between centers of two spheres that are calculated as:
L <sup>2</sup>= (diffx<sup>2</sup>+diffy<sup>2</sup>+diffz<sup>2</sup>)
- The advantages of this algorithm
This is a very low weight algorithm and will take no value at run time.
- The disadvantages of this algorithm
Each object takes a big free space around it in this sphere. The two objects in figure 3 will be treated as intersected objects though they are far from each other.
Cuboid algorithms
In figure 4, cuboids shapes are used as the object containers. It is more accurate than a sphere (but more complex). Because we are working in collision detection between objects, which run on the same plane, we will neglect 4 points which are on the top - assume you and I will not intersect if our foots don’t intersect. So we will focus on the rectangle algorithms not cuboids. Here, figure 6 shows an example of two objects which don’t intersect themselves.
Figure 6. Non-intersected objects
So if we analyze these rectangles, we will find that any rectangle is a composition of points and lines and we will divide our ideas into:
- Point algorithms
- Line algorithms
Point algorithms
This idea assumes that rectangles are intersected when one or more points from one of them is between the boundaries of another object.
Point algorithm 1 (Midi-point boundaries)
In this algorithm, the two objects are called A and B. The first step is looping on points of object A. The temp value in the loop called is temp and its coordinates are temp_x and temp_y, and we check them with object B's boundaries.
Loop on object "A" points, set temp to variable in loop
{
If (
B_object_x_minimum<= temp_x
And B_object_x_maximum>= temp_x
And B_object_y_minimum<= temp_y
And B_object_y_maximum>= temp_y
)
Then
This point from A is in boundaries of B, return true, leave algorithm
Else
This point from A is not in boundaries of B
}
Get one point from object "B" points, set temp to this point
If (
A_object_x_minimum<= temp_x
And A_object_x_maximum>= temp_x
And A_object_y_minimum<= temp_y
And A_object_y_maximum>= temp_y
)
Then
This point from B is in boundaries of A, return true, leave algorithm.
When reach this step so no intersection between two objects, return false.
But if rectangle B isn’t stable (doesn’t have a line parallel to X-axis or parallel to Y-axis), we can’t work on the minimum and maximum X, Y values. To solve this problem, you can rotate the two rectangles with an angle which will make the unstable object B become stable.
Note: But if you trace this algorithm, you will find that if there are no points from A in B’s boundaries and check only one point from “B” object, you did the algorithm logically and there is no need for checking the other three points from B. This will make you check on five points only, rather than eight points – in the worst case. So by taking care of this note, you will decrease the complexity of the algorithm 3/8 (37.5%).
Hint for complexity decreasing
Firstly, in this algorithm, you should check if one of the two rectangles is stable to depend on it in the first loop (treat it as B) - so as to not take the effort of rotating, especially if the first loop may return to you the answer which you are searching for - that the two objects intersected. Then depending on the other rectangle, if it is not stable, you will rotate it, and use only one point from object B, and you don’t have to make the rotating equation for the other three points in object B.
Search for stable rectangle
If find
{
Make object b= this stable rectangle.
Object a= another rectangle.
}
Else
{
Rotate 2 rectangles (8 points) by the angle of any rectangle line slop.
This rectangle which you get slop from it become stable now so b=this rectangle.
Object a= another rectangle.
}
For each point of A
{
If (this point in boundaries of B)
Then
There are intersection between A and B
Leave algorithm
}
if object (a) is not stable
{
Rotate object (a) by the angle of any its’ lines slop.
Rotate one point from object (b) with the same slop.
}
Check only this rotated point of object "B"
{
If (this point in boundaries of A)
Then
There are intersection between A and B
Leave algorithm
}
If come for here so there are no intersection between A and B
Note the rotation formulas of any point by angle are:
X = x * cos (q) – y * sin (q)
Y = x * sin (q) + y * cos (q)
Where X and Y are the new values of x and y.
Point algorithm 2 (Point’s face on boundary)
This algorithm depends on points and their faces on lines. If the point is between rectangle boundaries, its four faces on the rectangle's lines are on the lines themselves as in figure 7.
Figure 7. Point inside rectangle
Figure 8. Point out of rectangle
But if the point is outside the rectangle there are one or more faces of it on the lines, not on the line itself, as in figure 8 (the solid blue line represents the line from the point and its face, the dashed green line represents the extension of lines from the rectangle, and the black rectangle represents the rectangle of the object).
Solving this idea mathematically
Figure 9. Point and its reflection
Figure 10. Point and its reflection in triangle
From figure 9, we find that the angle between the line between the point and its face and the horizontal line is the same angle between the base line and the vertical line. So by the analysis of two triangles that hold these two angles, as in figure 10 (EDF) and (BAC), we can find that:
A is the point
C is the face of point A on DE
CG is vertical line
DE is the line that we worked on
B is the point with the same y value as "A" and on the line DE
F is the point with "D" x value and "E" y value
^(BCG)=^(EDF)
^(BCG)+^(CBG)=90 && ^(CAG)+^(CBG)=90
So
^(BCG)=^(CAG)=^(EDF)
^(ACB)=^(DFE)=90
^(ABC)=^(DEF)
While 3 angles in 2 triangles equal themselves, so 2 triangles are similar.
So
Line (AB)/line (DE)=line (AC)/line (DF) (1)
While point (B) is on the line (DE), the equation of line (DE) is
Y=ax+b
Y is a the same y of point "A"
A is slope of line DE=(D.y-E.y) / (D.x-E.x)
B is Y-axis displacement of line (DE)
So I can get x of point "b"
So
Line (AB) known length
Line (DE) known length
Line (DF) known length
So I can get length of line (ac) and set in "value" variable
(A.y-C.y)2+(A.x-C.x)2=value2
Where C.y=(a*C.x)+b (line equation)
"a" and "b" can known from line(DE)
(A.y- ((a*C.x)+b))2+(A.x-C.x)2=value2
This equation has only one unknown variable (C.x)
So we can get C.x value and from line (DE) or (AC) equation we can get C.y value.
After getting x and y of point "C" we can say if "C" on the line (DE) or not.
Sure the implementation of this algorithm doesn’t have all these equations; you just put the equations which give you the wanted value.
After you loop on one object’s four points, you have to check only one point from the other object - as the point in boundary algorithm above. The checking on one of the other object points is done to handle a special case as in figure 11. If you depend on the black object, you will get that there is no point from the gray object in the black rectangle though these two objects are intersected.
Figure 11. Two nested objects
Nothing in these two algorithms will cover all the cases because there is a special case as in figure 12 that point algorithms don’t cover, because these two objects are intersected although no point from each object is in the other object's body.
Figure 12. Not covered case in point algorithms
Line algorithms
This kind of algorithms' base idea concentrates on the lines intersection instead of points existing in another object's body.
Line algorithm 1 (Collision detection bunch solution algorithm)
This is from the rule two rectangles are not intersected if there are no points from one in the other's body and if there are no intersections between two lines from these rectangles.
Let's see the last algorithm that will solve the problem by taking care of points and line intersections. By developing another existing algorithm in line clipping – Cohen Sutherland algorithm [2] - and using it for our purpose. We create a new form of memory location –block- to use it to hold variables. This form has four locations LEFT, RIGHT, UP, and DOWN.
Figure 13. Point status representation
This data structure is assigned to each point in the two rectangles from its location related to the other rectangle. If the point is on the left of the other rectangle you should make its left location=1, else left=0, and so on.
Figure 14. Locations that set value to 1
In figure 14, the gray rectangle is 1 of 2 rectangles – the stable rectangle. After completing these 4 locations, if the point is in another rectangle, all four variables will be 0. By doing a bitwise OR operation as in table 1, the result=0, which means these two objects are intersected.
A left
| 0
|
A right
| 0
|
An up
| 0
|
A down
| 0
|
Total
| 0
|
Table 1 Point in another object values -OR op
Here we will work on lines. If there are two points which contain a line between them, we have two inverse variables =1 so this line will intersect the rectangle, as in figure 15.
Figure 15. Intersected line and rectangle
By making a bitwise AND operation as in table 2, the result=1 so the two objects are intersected.
B left
| 1
|
A right
| 1
|
Total
| 1
|
Table 2. Line with 2 inversed points-AND op-
If there are two points that have the same variable =1, the line between them doesn’t intersect the rectangle - as both two points are on the left side of the rectangle.
The complicated part in this algorithm is if we don’t find any of these cases, we must do more analysis on the line because these four variables alone can not give us the decision - if there is intersection or not. For example, the following two lines have a different decision although their points have the same values as in figure 16 and figure 17.
Figure 16. Non-intersected shape
Figure 17. Intersected shape
Here we will make a small calculation on two point values to get us the decision. We will make a bitwise OR calculation between the two point variables as in table 2.
| LEFT
| RIGHT
| UP
| DOWN
|
A
| 0
| 0
| 1
| 0
|
B
| 0
| 1
| 0
| 0
|
Total
| 0
| 1
| 1
| 0
|
Table 3. Calculation to get the probability of intersected lines
From the result, we get that we must check the line between A, B with right and up the line in the rectangle, which results in a 1 from the OR operation.
By using a line equation, we can get the intersected point between two lines, so if this point is on the rectangle line, there is intersection; if it is on its extension, there is no intersection.
Calculate A point’s variable
Loop on points
{
If (the point in another object) -OR between 4 variables-
Then
Intersected objects, Leave algorithm
}
Loop on lines
{
If (line points in same location)
Then
Go to another line and repeat the loop
If (line points in inverse location)
Then
Intersected objects, Leave algorithm
Else
{
Calculate which lines expected that might intersect (as table 3)
Loop on these lines
{
Calculate the intersection point by line equation
If (intersected point on the boundary line itself)
Then
Intersected objects, Leave algorithm
Else
Go to another line and repeat the loop
}
}
}
Calculate one of B point variable
If (the point in object "A")
Then
Intersected objects, Leave algorithm
If come for here so there are no intersection between A and B
The last part in the algorithm (calculate one of B points…) is to cover a case as in figure 11, if you depend on the black rectangle as the “B” object.
References
- [1] Bruno Miguel teixeira de sousa “Game Programming All In One”, Game development series, Premier Press.
- [2] Donald Hearn and M. Pauline Baker “Computer Graphics C Version” Second Edition. Prentice Hall.
History
- Version 1: 5 June 2011, Initial version.
