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, whenver 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 strait forward. 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 frame. 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!