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 (x
1x
2 + y
1y
2 + z
1z
2), and the
cross product of two
vectors (V
c=(y
1z
2-z
1y
2, z
1y
2-x
1z
2, x
1y
2-y
1x
2)), which is the result of the
normal vector of a
plane that contains two different
vectors ((x
1, y
1, z
1) and (x
2, y
2, z
2) 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
2π, 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!