FPS Player Movement Class
Home -->
Programming Projects -->
FPS Game Code -->
FPS Player Movement
Collision Detection
The purpose of this page is to describe a class used to
control the movement of a player in a first person shooter
computer game.
The player is modeled as an ellipsoid and collides against
the world accordingly.
In Block Arena, there is code to compute the intersection
of a sphere moving linearly with a triangle.
The ellipsoid version of this reduces to the sphere version
by scaling the world.
Various descriptions of how the
sphere-triangle intersection algorithm works
can be found on the internet
(for example,
here).
For this exposition, we will assume that this algorithm has
been implimented by the function
MoveEllipsoidThroughWorld:
void MoveEllipsoidThroughWorld(
const Vector & current_middle_pos,
double horiz_radius,
double vert_radius,
const Vector & offset,
Vector & new_middle_pos);
The arguments current_middle_pos,
horiz_radius,
vert_radius, and
offset are inputs, and
new_middle_pos will
hold the output of the algorithm.
The argument current_middle_pos
is the position of the middle of the ellipsoid
(before it is moved).
The arguments horiz_radius and
vert_radius refer to the dimensions
of the ellipsoid.
That is, the set of all points (x,y,z) on the surface
of the ellipsoid is given by the following equation:
(x - current_middle_pos.x)^2 / (horiz_radius^2) +
(y - current_middle_pos.y)^2 / (horiz_radius^2) +
(z - current_middle_pos.z)^2 / (vert_radius^2) = 1
The argument offset refers to the
direction (and distance) in which the ellipsoid
wants to be moved.
If the ellipsoid does not collide with
any objects in the world, then the
function will set
new_middle_pos = current_middle_pos + offset
and return.
If the ellipsoid does collide with
the geometry of the world,
the ellipsoid will slide
along surfaces and
new_middle_pos will be set accordingly.
"Sure" Footing
Other than MoveEllipsoidThroughWorld,
there is one other function that needs to
have access to the geometry of the world:
the OnSureFooting function:
bool OnSureFooting(
const Vector & foot_pos);
The argument "foot_pos" is the position of the
feet of the player.
This function will return true iff the feet
of the player are on or (very) slightly above
a surface (whose surface normal is close to
the "up" direction).
Thankfully, this function is quite easy
to impliment compared with
MoveEllipsoidThroughWorld.
It is needed because a player
moves differently when he is on
sure fooring than when he is not.
For example, a player should not be able to jump if he
is already in the air or if he is on a surface
that is nearly vertical.
If the OnSureFooting function returns false,
then the player is treated as if he is in the air.
Fixed Time Delta
Computer games like Quake update objects in the world
using fixed time deltas.
For an explanation of how this works,
here is a useful article.
Here is a brief example
to explain what is going on:
in Block Arena,
a time delta of 0.05 seconds is used.
As an example, suppose
that 453.86 seconds have ellapsed since
the start of the game.
Instead of calculating the player's position
for the time 453.86,
his position is calculated for the times
453.85 and 453.90 (his position is
calculated for the current time rounded
both down and up to the nearest multiple of 0.05.
The only time the player's "actual" position is
needed is for rendering (a process that does not
affect physics),
and this is calculated by
linearly interpolating between
the calculated posiitons at times 453.85 and 453.90.
It might seem like this technique is overly complicated,
but there are significant advantages.
First, if variable timesteps are used, then
one needs to solve a differential equation
to accomodate the acceleration and drag that
are affecting the player.
Even if one does this correctly,
when the player is moved through the world,
he is done so linearly (by the
MoveEllipsoidThroughWorld function),
so if the timestep is too large,
artifacts may occur.
Physics
The movement physics of the player
is determined by the variables
movement_acc,
ground_drag,
air_drag,
jump_impulse,
air_control,
gravity, and
max_planar_speed.
These are set to resonable values
in the constructor of the class.
To understand exactly how these
variables are used, look at the
code for the function
CalculateDesiredVel.
That function contains the essential
code that is easy to mess up when
writing such a class.
Circle Jumping
The way the function CalculateDesiredVel
is written, it is possible for the player to
circle jump.
Circle jumping is not a bug.
Rather, it is a phenomenon that is inherent
to the way the movement algorithm works.
Here is how to understand circle jumping:
the player has a "maximum planar speed",
which is the value max_planar_speed.
The length of the projection of the velocity
of the player onto the xy-plane
is allowed to be greater than max_planar_speed
(which might happen due to jumping on a bounce pad),
but in this situation the player is not allowed to
increase his planar speed.
He is, however, allowed to change the direction of
his velocity vector.
That is, if the player
is moving at a speed s > max_planar_speed
in the xy-plane, then if
pressing the movement keys causes an increase
in the speed of the player in the xy-plane,
the new velocity in the xy-plane is first
calculated and then it is rescalled to
have length s.
Circle jumping is the trick used to gradually change
the direction of the velocity vector
without changing its magnitude.
For example, the player could detonate a rocket
behind himself which causes him to go
faster in the xy-plane than max_planar_speed.
He can then bunny hop to maintain his speed.
When it is time to turn a corner,
by pressing the strafe and forward buttons
at the same time (to get optimal results)
and turning to one side, he can gradually
change the direction he is going
without changing his speed.
He is bunny hopping the entire time while
turning.
Hence, he is circle jumping.
Disclaimer: the circle jumping that is
possible to do here is much more mild
than in Quake3.
Indeed, the circle jumping here is so mild
that it might not be fair to label it as such.
That is, for the algorithm presented here,
the player cannot circle jump
to increase his planar speed,
whereas he can in Quake3.
Here is a place to read about how circle
jumping in Quake3 works.
Floats vs Doubles
Since the collision detection system
we have described works by detecting
when the ellipsoid of the player moves
through a surface but does not
detect if the ellipsoid is in
a surface, it is a good idea to use
doubles instead of floats!
That is, whenever the player is walking
on the ground, the ellipsoid is just
barely above a surface, which means that
high accuracy is essential.
In fact, accuracy is so essential that
a more sophistocated way of representing
the player's position may want to be
used depending on the application.
For example, consider a block based
first person shooter game.
It would be a good idea to represent
the player's position as the sum of
block position (a tripple of integers)
and a Vector (a tripple of doubles).
Numbers of this form can be added
(or subtracted) by adding (or subtracting)
both the integer and double components
separately.
The collision detection system should
be able to handle colliding a
moving ellipsoid whose center is
represented by a number of
this form with a block
(whose position is represented by
a tripple of ints).
The Code
Here is the class that
moves the player through the world:
class PlayerMovementController{
private:
//---------------------------------
// PRIVATE DATA MEMBERS
//---------------------------------
//The "collision detection" system.
CollisionSystem * col_sys;
//The movement "keys"
//that are pressed.
bool key_forward;
bool key_back;
bool key_left;
bool key_right;
bool key_jump;
//The change in velocity induced
//by the outside world such as
//rocket explosions, bounce pads, etc.
Vector impulse;
//Movement params.
double movement_acc;
double ground_drag;
double air_drag;
double jump_impulse;
double air_control;
double gravity;
double max_planar_speed;
//The size of the player.
double horiz_radius;
double vert_radius;
//Quake3 uses about 0.05 seconds for this value.
double fixed_timestep;
//The leftover time is the remainder of
//time (in seconds) that has not been processed.
//After processing is done, leftover_time
//should be between 0.0 and fixed_timestep,
//and this specifices the player position
//between start_pos and end_pos.
double leftover_time;
//The feet of the player are at the position
// start_pos*(1-leftover_time) + end_pos*leftover_time.
Vector start_pos;
Vector end_pos;
//The unit-length vector describing
//where the player is looking.
Vector head_look;
//---------------------------------
// PRIVATE MEMBER FUCNTIONS
//---------------------------------
void UpdateWithFixedTimestep();
Vector CalculateDesiredVel();
void PerformMotion(const Vector & offset);
public:
//---------------------------------
// PUBLIC MEMBER FUCNTIONS
//---------------------------------
PlayerMovementController(
CollisionSystem * col_sys,
const Vector & starting_pos);
//Movement commands:
void MoveForwardStart();
void MoveForwardStop();
void MoveBackStart();
void MoveBackStop();
void MoveRightStart();
void MoveRightStop();
void MoveLeftStart();
void MoveLeftStop();
void MoveJump();
void MoveStop();
//Should be called when the player
//stands on a bounce pad, etc.
//The value new_impulse should be the
//desired change in velocity of the
//player that needs to be applied.
void AddImpulse(const Vector & new_impulse);
//Turning command:
//(Should be from mouse dx and dy).
void Turn(int dx, int dy);
//The position of the feet
//of the player.
Vector GetPos();
//Where the player is looking.
Vector GetLook();
//(end_pos - start_pos) / fixed_timestep.
Vector GetVelocity();
//The elapsed_time is in seconds.
void Update(double elapsed_time);
};
Here is the constructor:
PlayerMovementController::PlayerMovementController(
CollisionSystem * col_sys,
const Vector & starting_pos)
{
this->col_sys = col_sys;
key_forward = false;
key_back = false;
key_left = false;
key_right = false;
key_jump = false;
impulse = Vector(0.0, 0.0, 0.0);
//The following values are good
//given that the position of
//the player is in meters.
//If fixed_timestep is changed,
//the movement params also
//need to be tweeked
//(especially ground_drag
//and air_drag).
movement_acc = 50.0;
ground_drag = 0.3;
air_drag = 0.0;
jump_impulse = 10.0;
air_control = 0.1;
gravity = 17.0;
max_planar_speed = 9.0;
horiz_radius = 0.3;
vert_radius = 0.8;
fixed_timestep = 0.05;
leftover_time = 0.0;
start_pos = starting_pos;
end_pos = starting_pos;
//Not really important.
head_look = Vector(1.0, 0.0, 0.0);
}
For the movement functions,
the idea is that when "w" key is pressed,
the MoveForwardStart function should be called.
When the "w" key is released,
the MoveForwardStop function should be called.
When the space bar is hit,
the MoveJump() function should be called.
Notice that jumping is a "one time thing"
whereas moving forward is something
that starts at one time and
ends at another.
void PlayerMovementController::MoveForwardStart() {
key_forward = true;
}
void PlayerMovementController::MoveForwardStop() {
key_forward = false;
}
void PlayerMovementController::MoveBackStart() {
key_back = true;
}
void PlayerMovementController::MoveBackStop() {
key_back = false;
}
void PlayerMovementController::MoveRightStart() {
key_right = true;
}
void PlayerMovementController::MoveRightStop() {
key_right = false;
}
void PlayerMovementController::MoveLeftStart() {
key_left = true;
}
void PlayerMovementController::MoveLeftStop() {
key_left = false;
}
void PlayerMovementController::MoveJump() {
key_jump = true;
}
void PlayerMovementController::MoveStop() {
key_forward = false;
key_back = false;
key_left = false;
key_right = false;
key_jump = false;
}
The AddImpulse should be called when
the vector new_impulse needs to be added to
the current velocity of the player.
This will result in the new_impulse
vector being added to the impulse member.
The impulse member will be used and then
set to zero when UpdateWithFixedTimestep is called.
void PlayerMovementController::AddImpulse(
const Vector & new_impulse)
{
impulse += new_impulse;
}
The function Turn(int dx, int dy) that takes
in the mouse dx and dy values and changes the member
head_look is relatively easy to impliment
and is not related to movement, so we will not go
into details.
The easiest way to impliment such as function is to
have two additional members theta and phi
of the class (which represent the vector
head_look in spherical coordinates)
and compute head_look from these values appropriately.
The functions GetPos,
GetLook, and GetVelocity
are all very straightforward.
A word needs to be said about how we are dealing
with velocity.
We do not store the velocity as a separate
quantity.
Rather, we compute the velocity from the position
of the player at two points in time
(the two positions are start_pos and end_pos)
The reason for doing this is so keep the
collision detection system as simple as possible,
although it does cause very slightly misleading results.
I am doing things this way to keep this tutorial
as simple as possible.
That proper way to deal with velocity would be for
the function MoreEllipsoidThroughWorld
to also return the "new velocity", and this
value would be used to set a member of the class
called velocity.
Getting the new velocity from the collision system
is needed if we want to detect
when the velocity of the player changes from hitting
the ground after falling from high up.
No matter what, the members start_pos and end_pos
are both still needed for interpolation purposes.
Vector PlayerMovementController::GetPos() {
return start_pos * (1-leftover_time)
+ end_pos * leftover_time;
}
Vector PlayerMovementController::GetLook() {
return head_look;
}
Vector PlayerMovementController::GetVelocity() {
return (end_pos - start_pos) / fixed_timestep;
}
The Update function should be called once every
update cycle.
The elapsed_time is going to vary.
The Update function chops
the quantity leftover_time + elapsed_time into pieces
of size fixed_timestep, with the remainder
assigned to leftover_time.
The player is then moved in a discrete fashion appropriately.
Notice that the player is being moved independently
from the rest of the simulation.
That is, we are not using the method where everything in
the world is advanced in time by fixed_timestep many seconds.
That is, if 0.6 seconds have ellapsed, then the player movement
controller is updated with the elapsed_time value of 0.6,
then the system that moves particles is updated with
this value, etc.
Each system will take this elapsed_time value
and chop it up accordingly so they can step through their
own discrete simulation.
void PlayerMovementController::Update(
double elapsed_time)
{
leftover_time += elapsed_time;
int count = 0;
while( leftover_time >= fixed_timestep ) {
UpdateWithFixedTimestep();
leftover_time -= fixed_timestep;
++count;
if( count > 200 ) {
cout << "update taking too long\n";
exit(0);
}
}
}
Both before and after this function is called,
leftover_time will be between 0
and fixed_timestep.
There is a danger in using fixed timesteps
that the simulation will take too long.
That is, if the time in real life used to
compute one step of the simulation is
ever longer than fixed_timestep,
then the program will go into what is called a
spiral of death, in which more and more
time is being spent on the simulation each frame.
This is the purpose of the variable
count used in the function.
The UpdateWithFixedTimestep function
moves the player through one step of the simulation.
First, the desired velocity of the player is calculated
(using which keys are being pressed, as well as the
momentum of the player, etc).
Next, the desired offset is calculated.
When the PerformMotion function is called,
if the player does not collide with anything in the world,
then start_pos will be replaced with end_pos
and end_pos will be replaced with
end_pos + desired_offset.
void PlayerMovementController::UpdateWithFixedTimestep() {
Vector desired_vel = CalculateDesiredVel();
Vector desired_offset = desired_vel * fixed_timestep;
PerformMotion(desired_offset);
}
The PerformMotion function is quite simple.
Recall that start_pos and end_pos
refer to the position of the feet of the player
at two points in time.
Recall also that the MoveEllipsoidThroughWorld
function takes the values
current_middle_pos,
horiz_radius,
vert_radius, and
offset as input and sets
new_middle_pos as output.
void PlayerMovementController::PerformMotion(
const Vector & offset)
{
//Performing the move.
Vector current_middle_pos =
end_pos + Vector(0.0, 0.0, vert_radius);
Vector new_middle_pos;
if( Length(offset) > 0.001 ) {
col_sys->MoveEllipsoidThroughWorld(
current_middle_pos, horiz_radius,
vert_radius, offset, new_middle_pos);
} else {
new_middle_pos = current_middle_pos;
}
//Getting the new foot position.
Vector new_foot_pos =
new_middle_pos - Vector(0.0, 0.0, vert_radius);
//Updating the state.
start_pos = end_pos;
end_pos = new_foot_pos;
}
Something to note in this function is that
if the offset has a very small length,
then no motion will be performed.
The reason for this is that
if the MoveElipseThroughWorld function
is not written carefully, it will normalize the
offset vector as a first step and this will
cause terrible problems
(normalizing a vector that is almost the zero
vector is a bad idea).
CalculateDesiredVel is really
the essential function of the
PlayerMovementController class.
If this function is written in the naive way,
the player will be able to reach enormous
speeds by bunny hopping.
To avoid this, there needs to be some way
to "cap the player's velocity".
However, simply
rescalling the velocity vector if it is
larger than the maximum allowed velocity
will not give desirable results.
For example, if the player is hit by a rocket
or stands on a jump pad, he should be able
to move faster than his maximum velocity.
Hence, what needs to happen is that if the
player's velocity is already greater than
the maximum allowed velocity, by pressing
the movement keys he should not be able
to go any faster, but he can maintain
his current speed.
Another important thing to note is that
the z-component (up and down) of the
velocity of the player should be treated
separately from the projection of
the velocity onto the xy-plane for
max-speed capping purposes.
That is, the length of the velocity
vector projected onto the xy-plane
is what is important, not the
length of the velocity vector itself.
Vector PlayerMovementController::CalculateDesiredVel() {
//Ground vs air control.
bool in_air = !(col_sys->OnSureFooting(end_pos));
double control = (in_air ? air_control : 1.0);
//Momentum and impulses.
Vector desired_vel = Vector(0.0, 0.0, 0.0);
Vector momentum = (end_pos - start_pos) / fixed_timestep;
desired_vel += momentum;
desired_vel += impulse;
impulse = Vector(0.0, 0.0, 0.0);
//Jumping.
if( key_jump ) {
if( !in_air ) {
//Actually jumping.
desired_vel.z = jump_impulse;
}
key_jump = false;
}
//Gravity.
desired_vel.z -= gravity * fixed_timestep;
//Drag:
//Note: the behavior of drag highly
//depends on the fixed_timestep.
if( in_air ) {
desired_vel *= (1.0 - air_drag);
} else {
desired_vel *= (1.0 - ground_drag);
}
//Dealing with player input.
Vector current_planar_vel = desired_vel;
current_planar_vel.z = 0.0;
double current_planar_speed = Length(current_planar_vel);
Vector look = head_look;
look.z = 0.0;
if( Length(look) > 0.001 ) Normalize(look);
//The vector left is perpendicular to the vector look.
Vector left = Vector(-look.y, look.x, 0.0);
Vector add = Vector(0.0, 0.0, 0.0);
if( key_forward ) add += look;
if( key_back ) add -= look;
if( key_left ) add += left;
if( key_right ) add -= left;
if( add != Vector(0.0, 0.0, 0.0) ) {
Normalize(add);
add *= movement_acc * control * fixed_timestep;
Vector new_planar_vel = current_planar_vel + add;
double new_planar_speed = Length(new_planar_vel);
if( new_planar_speed > max_planar_speed ) {
if( new_planar_speed > current_planar_speed ) {
//The player is speeding up, so his planar speed
//should be capped at max(max_planar_speed,
//current_planar_speed)
double cap_speed = max(
max_planar_speed,
current_planar_speed);
Normalize(new_planar_vel);
new_planar_vel *= cap_speed;
} else {
//The player is not speeding up, so his
//velocity does not need to be capped.
}
} else {
//No need to cap the velocity.
}
desired_vel.x = new_planar_vel.x;
desired_vel.y = new_planar_vel.y;
}
return desired_vel;
}
Note that when the player jumps,
the z-component of his velocity is set
to jump_impulse regardless of
the previous value of the z-component.
This is to prevent players from
jumping really high by combining
a normal jump with, say, a rocket jump.
That is it!