Introduction: Collision detection is an important aspect in any good game. However, computing collision can be resource consuming, inacurate and frustrating. This tutorial is designed to demonstrate methods of increasing speed and creating a collision detection function.

Methodolgy: There are two methods that will be demonstrated in this tutorial. The first method is faster than the second method but if te coordinate plane location of the center of one of the polygons is miscalculated, it may cause problems and when using it with triangle collision detection, the lack of another side may also cause problems. It also comes with two more cons one of which is share by both methods however in the second, it can be corrected; the unshared problem known only to method one is that the center of the polygon being used to perform the main calculations can not be inside the other polygon; to correct this, switch polygons. The shared problem is that if one of the polygons is inside of another, you will have to modify calculations to have it work properly.

Method One: The first method is a simple few step proccess.

1) Calculate the center of one of the two polygons.

2) Connect the center point to each of the polygon's vertexes

3) Perform a check with each one of the radial lines;

if it intersects with another polygon's side, collision Psuedo-Code:

C = Center

V = Vertex (Corner)

A = Side point one

B = Side point two

Do

If (C.X,C.Y)-(V.X,V.Y) Intersects (A.X,A.Y)-(B.X,B.Y) Then

Collide = True

Exit Function

Else

A.X = NextSide.X1

A.Y = NextSide Y1

B.X = NextSide.X2

B.Y = NextSide.Y2

End If

Loop

Method Two: More accurate but more computation time

1) Cycle through each side of one polygon

2) Cycle through each side of the other polygon

3) Do the line segments that make of the sides intersect?

Yes: Collide = True

No : Cycle to next side of other polygon

4) If cycled through all other polygon sides, move to

next side of polygon one.

BASIC Code For Calculating Intersections:

Function Intersect(X0 As Double,Y0 As Double,X1 As Double,Y1 As Double,X2 As Double,Y2 As Double,X3 As Double,Y3 As Double,OX As Double,OY As Double)

''Original code was written in C++.

''Courtesy of "Scott" from GameDev.net

''http://www.gamedev.net/reference/articles/article423.asp

DIM As Single A1, B1, C1, A2, B2, C2, DI

DIM As Single M1, M2

If ((X1-X0)<>0) Then

M1 = (Y1-Y0)/(X1-X0)

Else

M1 = 1e+10

End If

If ((X3-X2)<>0) Then

M2=(Y3-Y2)/(X3-X2)

Else

M2 = 1e+10

End If

If M1 = M2 Then Intersect = 0: Exit Function

A1 = M1 : B1 = -1 : C1 = (Y0-M1*X0)

A2 = M2 : B2 = -1 : C2 = (Y2-M2*X2)

DI = 1/(A1*B2-A2*B1)

OX=((B1*C2 - B2*C1)*DI)

OY=((A2*C1 - A1*C2)*DI)

Intersect = 1

End Function

Final Note: On a final note(s), when using the function above, it will return a "0" if the lines are parrallel and never intersect and a "1" if they do. The function treats each line segment as a line so you will need to make sure that when writing a collision detection routine that the values returned are in the bounds of were the collision could take place. Example:

We know a collision could only take place in a box from

(0,5)-(10,20). So when the X and Y values are returned, we

would make sure they were in the proper range like this:

If X >= 0 And X <= 10 AND Y >= 5 And Y <= 20 Then InBounds = True