Be warned. You may need to know some knowledge about vector math to completely understand everything. Sufficient knowledge of OOP in programming or scripting languages such as, respectively, C++ or Perl is required. You will see why in just a few paragraphs within the writeup.

Part I: Checking for a collision

The basic way of getting the ball rolling is using a for loop to iterate through every plane. Inside the loop the shortest distance from the plane to the player's position should be calculated using physics formulas such as the dot product of two vectors to get the closest distance from a plane (x1x2 + y1y2 + z1z2), and the cross product of two vectors (Vc=(y1z2-z1y2, z1y2-x1z2, x1y2-y1x2)), which is the result of the normal vector of a plane that contains two different vectors ((x1, y1, z1) and (x2, y2, z2) in respect to the previous cross product expression).

A normal vector is a vector that is perpendicular from the given plane. It can be used for other things such as lighting (shading, etc.) in programming 3D games, but for this, it is just to use in a dot product to check the shortest distance to a plane. To help understand what a normal vector is, a diagram is shown:

                       ^
                    ^ /
    Normal Vector-->|/__
            <---/   |¬ /--->
               /______/ (Infinite plane)
                  /
                 /
                v

NOTE: In order for the collision to work, the normal vector of a plane should be facing the player. The player should never be able to collide with a plane from behind.

According to the theorems of Geometry, "The shortest line connecting a skew point to a plane is always perpendicular to the plane." This is the reason for using the normal as a parameter of the dot product.

If the distance is close enough, the points of a polygon should be checked. In order for this to be done, the specific point on the plane that the player will collide at is required. This is done by rescaling the velocity vector by how far away the person is from the shortest distance from the plane. Add the player's position to that vector, and that altogether is the vector of the point on collision from the origin.

Then the points of the polygon are subtracted by the point on collision so an angle can be obtained, like so:

Let p1 = vertex of polygon,
    p2 = another vertex of polygon,
    pc = point on collision,
     a = angle between vectors.

. <-- p1 ----------.
|                  |
|                  |
|   . <-- pc       |
|                  |
|                  |
. <-- p2 __________.

v1 = p1-pc
v2 = p2-pc

.------------------.
|\ v1              |
| \                |
| a. <-- pc        |
| /                |
|/ v2              |
.__________________.
Angle a is obtained by dividing the dot product of the vectors by the product of the magnitude, or length, of the vectors (√(x² + y² + z²)):
           v1 . v2
cos a = -------------
        ||v1||•||v2||
Solving for a, the equation is:
             v1 . v2 
a = cos-1 ------------- 
          ||v1||•||v2||
The reason for getting the angle at the vertex of two of these vectors is simple. This is done with every possible angle made with the polygon, like so:
.---------.
|\       /|
| \     / |
|  \a2 /  |
|   \ /   |
| a1 . a3 |
|   / \   |
|  /a4 \  |
| /     \ |
|/       \|
._________.

The sum of all of these angles should be 2π radians when the point is within the polygon. If the sum does not add up to , whether it is more than or less than the value, then the point is not within the plane. The value should not be checked specifically for 2π. It's best to have the code check in between a certain margin of error. This will be explained in The player's response to collision detection.

Part II: The player's response to collision detection

Just to stay on track, here is a small refresher on how the collision detection would be written in pseudocode and where the response to it should be placed:

for(loop from plane 0 to plane x, where x is the maximum number of planes)
{
    if(the player is close enough to the plane for collision to occur)
    {
        if(the point of collision on the plane is within a polygon)
        {
            ...
            Collision response code would go here.
            ...
        }
    }
}
The main thing done is: the player is "bounced back" to a certain distance from the plane. This is done by calculating the normal vector of the plane, if not calculated already and stored in a variable. This diagram will show how to bounce the player back:
Let:
   O = player,
____ = polygon to be collided with,
---- = the sufficient distance from the polygon,
d    = Distance from the ___ to the ---,
p    = player's distance from the ___.
Vp   = (x,y,z) position of the player's location.

Frame A:
____________________

--------------------
       O               (Player is safe.)
      
Frame B:
____________________
       O               p < d (Player has crossed the boundary.)*
--------------------

Frame C:
____________________
                        Vp = Vp + Plane's normal with length: (d-p)**
-------O------------    (Player is 'bounced' back to this exact distance)

* Make sure this stage of collision is never displayed, or the collision won't look smooth at all!
** Don't know how to manipulate the distance of a vector? Here's how. There are easier ways, but it will be done this way to help the reader understand what's going on.
Let:
(xn, yn, zn) = the XYZ value of the normal vector,
m = magnitude of the vector (√(xn² + yn² + zn²)).

First, turn the normal vector into a unit vector, if not already:

xn = xn / m,
yn = yn / m,
zn = zn / m.

This makes the magnitude of the vector a length of one.

After this is done, the vector is then multiplied by (d-p).

xn = xn * (d-p),
yn = yn * (d-p),
zn = zn * (d-p).
This makes the vector have a magnitude of (d-p). The XYZ values are added to the XYZ values of the player's position after this.

Part III: Extra tips!

  • Difference Between a Slide and a Slanted Floor: If the normal of a vector of a plane is a slanted floor (yn is > 0.0, but less than a steep wall), assume that (xn, yn, zn) is (0, 1, 0), otherwise the player will look like he is sliding down a sliding board when walking down a ramp.
  • What Goes Up Must Come Down: If the player is jumping in the air up toward a ceiling (where yn is equal to or close to -1.0), then the y value of the player's current velocity should become the opposite of itself so the feeling is like the person just bumped his head and fell back down at the same speed he came up.
  • Give Less Margin of Collision to Floors: It is best to make the point-in-polygon tolerance have more margin for the walls than the floors/ceilings. The walls are best to make realistic. The floors and ceilings with a high margin seem weird, because it is possible to stand beyond the polygon, which is like levitating about a foot away from a cliff.

This tutorial should be able to help anyone who is ambitious to create a decent first-person shooter. This collision detection can be applied to other things, such as rockets, bullets, other players, and AI. There are other ways to apply collision detection, but this method seemed the easiest and most fit for a first person shooter.

Happy coding!


Log in or registerto write something here or to contact authors.