Setting up a game update loop in-sync with rendering

One thing that just about every game ends up needing is a way to update the game in-step with the devices v-sync. Some games even take it a step further and update their rendering system separate from their game world, so the game world and rendering can update independently. For now we'll keep it simple and just talk about setting up an update loop that remains in-sync with rendering.

First, you want to keep your frame updates within reasonable limits, relative to the device's refresh rate. And like V-sync, you also only want to update with time changes that are multiples of the refresh rate. First we'll set up a few variables to hold some of that data.

static const float s_device_refresh = 60.f;
static const float s_device_quarter_refresh = s_device_refresh / 4.f;
static const float s_min_framerate = s_device_quarter_refresh;
static const float s_max_frametime = 1 / s_min_framerate;
static const float s_target_framerate = s_device_refresh;
static const float s_min_frametime = 1 / s_target_framerate;

Note that I'm not actually reading in the device's refresh rates in this post, I'm assuming a refresh rate of 60 fps. In real-world use you'll need to grab the refresh rate from the device and store it for use. And we will just use a quarter of the refresh rate as the minimum update rate that we'll accept, which is 15 fps in this example.

And we'll create a couple of variables to hold how much time since we last allowed the game to update, and the total time elapsed since the program started.

static float s_time_buffer = 0.f;
static float s_actual_time_elapsed = 0.f;

Let's setup a simulated update function. The update function is the one you would end up calling whenever we calculate that it will line up with the device's refresh. All we do in this example is show how much time the update method would be given to update the game, how much actual time has passed since the program started, and what frame the device would be on by this point.

void update(const float time_delta, const float game_time)
{
    std::cout << "Update, time_delta: " << time_delta << ", total time: " << game_time << ", frame #: "
              << static_cast<int>(game_time / (1 / s_device_refresh)) << std::endl << std::endl;
}

Now, for the bread and butter, we need a method that processes how much time has elapsed since the OS last let our program update, and can take that time and figure out if we need an update, and how much time that update should be allowed to simulate.

void process_update_needed(const float time_delta)
{
    s_time_buffer += time_delta;
    s_actual_time_elapsed += time_delta;
    
    std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
    
    float time_this_update = 0.f;
    
    while ( s_time_buffer >= s_min_frametime )
    {
        s_time_buffer -= s_min_frametime;
        time_this_update += s_min_frametime;
    }
    
    while ( time_this_update > 0.f )
    {
        if ( time_this_update >= s_max_frametime )
        {
            time_this_update -= s_max_frametime;
            update(s_max_frametime, s_actual_time_elapsed);
        }
        else
        {
            update(time_this_update, s_actual_time_elapsed);
            time_this_update = 0.f;
        }
    }
}

We update s_time_buffer, which holds how much time we have stored up. Here we're also keeping track of the total time elapsed (s_actual_time_elapsed). We create a float to store how much time we're going to send to our 'update' function. Now, what the condition for the while loop is doing is, if the amount of time we've accumulated is greater than or equal to 1/60th of a second (since we're assuming 60 fps) then we remove 1/60th of a second from the time buffer and add it to the amount of time we'll be sending to the update method. The next while loop, if there is any time to be send to the update method, will check to see if the amount of time we're sending to the update method is greater than the maximum frame time. If the time is greater than the maximum frame time, then we just send the maximum frame time for this update and then we subtract that amount from the time remaining to be sent to update. Once the time remaining is less than the maximum frame time then we just send the rest.


There are a couple of major considerations to make when updating your game:

1. Do you want predictable time slices for every receiver of update calls?
2. If your update calls are expensive, do you really want to call them more than once per frame? (This can lead to a well-of-despair problem, which we'll talk about later as well)

The example above will split of the time into slices that are multiples of the refresh rate, and call update for every slice. This ensures that receivers of the update method get time slices that are always multiples of the refresh rate, never less than the refresh rate, and never greater than the max time amount that you've defined. Why is having a multiple of the refresh rate important? If you're moving anything on the screen, it will look smoothest if it moves at the same rate at all times.

Why a timestep that is a multiple of the screen refresh rate?

Let's imagine a dot moving across the screen, we'll just talk about it's X position, assuming 0 is the left side of the screen, and 100 is the right side of the screen. The dot moves at 100 units per second, so it should cross the screen in 1 second. Now lets look at the numbers, comparing time elapsed with the times that the screen has actually rendered.

---------------------------------------------------------------------------------
Time (ms) | Frame (60fps) |  Dot pos (actual time)  |  Dot pos (refresh times)  |
----------+---------------+-------------------------+---------------------------|
0         |  0            |  0                      |  0                        |
10        |  0            |  1                      |  0                        |
21        |  1            |  2.1                    |  1.67                     |
33.3      |  2            |  3.33                   |  3.33                     |
43        |  2            |  4.3                    |  3.33                     |
54        |  3            |  5.4                    |  5.0                      |
66.6      |  4            |  6.66                   |  6.66                     |
---------------------------------------------------------------------------------

In the above table you can see what kind of results we get if don't use fixed time steps that are multiples of the refresh rate. The numbers on the left represent non-fixed times that would be passed to your update method. The second column shows you what frame the game would be on at those times. The third column shows the X position where you would be rendering the dot on the screen on that frame, and the fourth column shows where you actually want to be rendering the dot on the screen if you the smooth constant speed the player is expecting to see. So, if you want to get rid of the visual jitteriness, the key is to update only one frames that you'll be rendering on, and to update at a rate that matches the last time that you rendered. The big caveat with this is that you need to make sure that the time your frames are taking to process is fairly consistent. If you wait until a specific time so that you can update in-sync with the monitor refresh rate and then your update takes much longer than average, your update will actually push back the render to the next frame, and you'll end up with jitteriness anyway. So one of your end goals for your game should be a fairly consistent framerate.

Avoid the well-of-despair problem

The well-of-despair problem is when your time accumulates, and requires more fixed timestep updates to get rid of. The extra update calls end up increasing the amount of time your frame takes, which in turn makes your time accumulate to larger values. And thus the cycle continues until your framerate is hosed completely.

There are a couple of ways to get around the problem, both have their own issues though.

Option 1.) Lie about time
If the accumulated time exceeds a certain threshold then you can just send the update method a certain maximum value. This will result in your game moving in slow-motion. I'm sure you've seen this in certain games in the past, at times when a lot is going on and the device can't keep up. That is why that happens in those games. Here's an updated 'process_update_needed' function that handles the well-of-despair problem by lying about time. If our 'time_this_update' was 0.12f, and our s_max_time_threshold is 0.1f, then we'll be updating only 0.1f, causing the game to visually slow down by about 18%.

static const float s_max_time_threshold = s_device_refresh / 6.f;

void process_update_needed(const float time_delta)
{
    s_time_buffer += time_delta;
    s_actual_time_elapsed += time_delta;
    
    std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
    
    float time_this_update = 0.f;
    
    while ( s_time_buffer >= s_min_frametime )
    {
        s_time_buffer -= s_min_frametime;
        time_this_update += s_min_frametime;
    }
    
    if ( time_this_update > s_max_time_threshold )
    {
        // We'll split the large amount of time into at least 2 updates to
        // keep the update time steps from being too large.
        update( s_max_time_threshold / 2, s_actual_time_elapsed );
        update( s_max_time_threshold / 2, s_actual_time_elapsed );
    }
    else
    {
        while ( time_this_update > 0.f )
        {
            if ( time_this_update >= s_max_frametime )
            {
                time_this_update -= s_max_frametime;
                update(s_max_frametime, s_actual_time_elapsed);
            }
            else
            {
                update(time_this_update, s_actual_time_elapsed);
                time_this_update = 0.f;
            }
        }
    }
} 

Option 2.) Don't used fixed timesteps once you exceed the maximum time threshold, just pass the actual time. This can result in extremely large timesteps in some cases, which can cause bugs.

void process_update_needed(const float time_delta)
{
    s_time_buffer += time_delta;
    s_actual_time_elapsed += time_delta;
    
    std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
    
    float time_this_update = 0.f;
    
    while ( s_time_buffer >= s_min_frametime )
    {
        s_time_buffer -= s_min_frametime;
        time_this_update += s_min_frametime;
    }
    
    if ( time_this_update > s_max_time_threshold )
    {
        update( time_this_update, s_actual_time_elapsed );
    }
    else
    {
        while ( time_this_update > 0.f )
        {
            if ( time_this_update >= s_max_frametime )
            {
                time_this_update -= s_max_frametime;
                update(s_max_frametime, s_actual_time_elapsed);
            }
            else
            {
                update(time_this_update, s_actual_time_elapsed);
                time_this_update = 0.f;
            }
        }
    }
}

The reason the above method can cause bugs is due to the potential for a large time step. For example let's say your player's character is running and trying to jump over a gate that is rising up to block him. If the timesteps were small enough the gate would rise up before the player got to it and the player would be blocked by it. Now let's say you game has a hitch that causes it to freeze for a full second, and when the game resumes it passes that full second timestep to your player and the player jumps a second of distance through the air. There are ways to tackle this problem, but this is just one example of something you would need to handle with large timesteps. If you can stick to more updates at a smaller timestep, or allowing the game to slow down a bit, then you avoid those problems, as a tradeoff for the slowdown you'll get.

Alright, we're almost done. We want a way to test our code, here's the main() function to do that for you:

#include <ctime>

int main(int argc, const char * argv[])
{
    // Randomize with time as a seed
    std::srand( static_cast<unsigned int>(std::time(0)) );
    
    static const float min_frametime = 0.01f;   // 100 fps
    static const float max_frametime = 0.04f;   // 25 fps
    
    for ( int i = 0; i < 30; ++i )
    {
        float rand_frametime = min_frametime + static_cast<float>(std::rand()) / (static_cast<float>( RAND_MAX / (max_frametime - min_frametime) ));
        process_update_needed( rand_frametime );
    }
    
    return 0;
}

Here's the full source code for the version that allows the game to slow down to avoid the well-of-despair problem.

#include <iostream>
#include <ctime>

static float s_time_buffer = 0.f;
static float s_actual_time_elapsed = 0.f;
static const float s_device_refresh = 60.f;
static const float s_device_quarter_refresh = s_device_refresh / 4.f;
static const float s_min_framerate = s_device_quarter_refresh;
static const float s_max_frametime = 1 / s_min_framerate;
static const float s_target_framerate = s_device_refresh;
static const float s_min_frametime = 1 / s_target_framerate;
static const float s_max_time_threshold = s_device_refresh / 6.f;

void update(const float time_delta, const float game_time)
{
    std::cout << "Update, time_delta: " << time_delta << ", total time: " << game_time << ", frame #: "
              << static_cast<int>(game_time / (1 / s_device_refresh)) << std::endl << std::endl;
}

void process_update_needed(const float time_delta)
{
    s_time_buffer += time_delta;
    s_actual_time_elapsed += time_delta;
    
    std::cout << "Processing update, time_delta: " << time_delta << ", time accumulated: " << s_time_buffer << std::endl;
    
    float time_this_update = 0.f;
    
    while ( s_time_buffer >= s_min_frametime )
    {
        s_time_buffer -= s_min_frametime;
        time_this_update += s_min_frametime;
    }
    
    if ( time_this_update > s_max_time_threshold )
    {
        // We'll split the large amount of time into at least 2 updates to
        // keep the update time steps from being too large.
        update( s_max_time_threshold / 2, s_actual_time_elapsed );
        update( s_max_time_threshold / 2, s_actual_time_elapsed );
    }
    else
    {
        while ( time_this_update > 0.f )
        {
            if ( time_this_update >= s_max_frametime )
            {
                time_this_update -= s_max_frametime;
                update(s_max_frametime, s_actual_time_elapsed);
            }
            else
            {
                update(time_this_update, s_actual_time_elapsed);
                time_this_update = 0.f;
            }
        }
    }
}

int main(int argc, const char * argv[])
{
    // Randomize with time as a seed
    std::srand( static_cast<unsigned int>(std::time(0)) );
    
    static const float min_frametime = 0.01f;   // 100 fps
    static const float max_frametime = 0.04f;   // 25 fps
    
    for ( int i = 0; i < 30; ++i )
    {
        float rand_frametime = min_frametime + static_cast<float>(std::rand()) / (static_cast<float>( RAND_MAX / (max_frametime - min_frametime) ));
        process_update_needed( rand_frametime );
    }
    
    return 0;
}

Simple Gravity for your 3D game

Beginners out there are often making a really simple game and don't always need a physics engine. If you want to try out some basic gravity for your game, then something like this might work for you.

Any object in your 3D world is going to need a 3D position (a point, often represented by a vector class). Applying gravity to your 3D objects is actually really simple, assuming you're not trying planetary physics around a sphere (or a gravity well of some kind). Each frame during an update cycle you just add gravity to the velocity of your objects. And later in the update cycle you move all of your objects based on their velocity. Here's some C++ pseudocode of how this might work:

#include <vector>

class Object
{
public:
    Object();

    Vector3 m_position;
    Vector3 m_velocity;
    Matrix3 m_rotation;
    float   m_elasticity;
};

class SceneManager
{
public:
    void update(float timeDelta);

private:
    std::vector<Object> m_objects;
}

void SceneManager::update(float timeDelta)
{
    // Be careful here, I'll explain why after the code snippet
    for ( unsigned int i = 0; i < m_objects.size(); ++i )
    {
        applyGravity(m_objects[i]);

        updatePosition(m_objects[i]);
    }
}

void applyGravity(float timeDelta, Object& obj)
{
    static Vector3 gravity(0.0f, -9.8f, 0.0f);

    // Factor time when adding gravity, because 9.8m/s is a speed, and speed requires time
    obj.m_velocity += (timeDelta * gravity);
}

void updatePosition(Object& obj)
{
    obj.m_position += obj.m_velocity;
}

Be careful when looping through your game's object list and making changes, if your change of position does something like cause a collision with another object, and you are handling that immediately, you could wind up making changes to your list of objects while you're in the middle of iterating through them. The above sample will work, but if your 'applyGravity' and 'updatePosition' methods don't end up getting inlined then you're going to be incurring two function calls for every object in your scene. If those methods don't get inlined then I would recommend passing your entire list of objects that you want updated to the function and let the function loop through them and make the updates. It would like something like this:

void SceneManager::update(float timeDelta)
{
    applyGravity(m_objects);
    updatePosition(m_objects);
}

void applyGravity(float timeDelta, std::vector<Object>& objs)
{
    // A hard-coded gravity, you might want to have this somewhere convenient
    // where it can be changed at run-time. Depends on what you're trying to do.
    static const Vector3 gravity(0.0f, -9.8f, 0.0f);

    const float gravityThisFrame = (timeDelta * gravity);

    for ( unsigned int i = 0; i < objs.size(); ++i )
    {
        objs[i].m_velocity += gravityThisFrame;
    }
}

void updatePosition(std::vector<Object>& objs)
{
    for ( unsigned int i = 0; i < objs.size(); ++i )
    {
        objs[i].m_position += objs[i].m_velocity;
    }
}

Once you have gravity your next concern will probably be some kind of collision detection with the ground. How you do that will be determined by your game, but once you've detected a collision with the ground, a simple way to handle the bounce is to flip the velocity and reduce it by some amount. The more you reduce the velocity the less bouncy your object is.

void handleGroundCollision(Object& obj)
{
    objs[i].m_velocity.y *= -objs[i].m_elasticity.y;
}

The above method assumes your gravity is in the direction of the -Y axis. If you have a gravity going in a different direction then you may need to do a bit more of a complex calculation to bounce your object. The following method will handle basic collisions with any stationary object. In this case you need to pass the normal of the surface the object is hitting, if that is flat ground and your 'up' axis is +Y then the surface normal is Vector3(0.0f, 1.0f, 0.0f). Make sure your surface normal is normalized/unitized before using it in this method.

void Vector3::reflect( const Vector3& normal, float elasticity )
{
    const float dotProductTimesTwo = Dot(normal) * 2.0f; 
    x -= dotProductTimesTwo * normal.x * elasticity;
    y -= dotProductTimesTwo * normal.y * elasticity;
    z -= dotProductTimesTwo * normal.z * elasticity;
}

// Or if you don't have your own Vector class, use this:
void reflect( Vector3& velocity, const Vector3& normal, float elasticity )
{
    const float dotProductTimesTwo = Dot(normal) * 2.0f;
    velocity -= ((dotProductTimesTwo * normal) * elasticity);
}

Setting your object's elasticity to 0.0f would mean that it would not bounce at all. A value of 1.0f would mean a perfect bounce, which would have no loss of energy on the bounce. Any value higher than 1.0f would cause the ball to move with a higher velocity than when it bounced. Usually you're going to want something between 0.0f and 1.0f, feel free to experiment with it a bit.

One more optimization consideration to make with this. If you have a lot of objects it can become more and more expensive to loop through them all each frame. If you separate your object list, or have another one for only the objects that can be moved or affected by gravity, then that will limit how many objects you're having to loop through each frame. Additionally if you have some more advanced detection methods you may know when an object is at rest due to it sitting on top of another object, if that is the case you may not need to apply gravity to it. Be careful with that optimization though, if gets tricky if you start mucking around with the direction of gravity.

Djikstra's Algorithm: Finding the Shortest Path

For those that are unfamiliar, Djikstra's Algorithm is used to find the guaranteed shortest path between two points in a graph (as opposed to A* which will take an educated guess, but is more efficient). For the second time in as many years I've found myself needing a shortest path algorithm in a game project. The last one that I wrote was before my blog existed and I never published it, and since then I've lost access to the code base it was published in. This time I'm a bit more pressed for time and didn't want to write my own from scratch so I decided to grab one from online and fix it up a bit.

Here's the original that I found: http://www.reviewmylife.co.uk/blog/2008/07/15/dijkstras-algorithm-code-in-c/

It has several issues with it that I needed to solve:

• The algorithm itself and several methods related to it were not encapsulated, which is messy. At the least they should be in their own file.
• Any nodes and edges that were created had to be deleted by the user otherwise the program would leak memory.
• The code assumes all edges were bi-directional, I need to handle the possibility of a directional edge.
• Querying the node graph would remove the nodes from the graph, making it so that if you wanted to query again you had to recreate the graph.
• The code didn't handle the case in which there wasn't a possible path between two nodes
• There were several inefficiencies.

The changes I made were:

• Encapsulated the algorithm, and the containers for the nodes and edges into a Graph class.
• The Graph class destructor made sure to clean up the nodes and edges to prevent memory leaks.
• Made edges directional while still allowing for bi-directional connections.
• Allowing the Graph class to not remove nodes while calculating the shortest path, so the user can query the graph as often as they'd like without recreating it.
• Made a user-friendly method to allow the user to get a path between any two nodes.
• Corrected inefficiencies.

For the code containing all of my changes, (click here). I go over the changes in more detail at the end of this post.

In the example code, here is the graph:

Notice that the edges between A and B, and E and F, are uni-directional, you cannot move from B to A, or F to E. In a shortest path algorithm, each node connection (edge) has a weight rather than a distance, this is because we're really not looking for the path of least distance, but the path that can be traversed the fastest, so we may want to factor in things along the path that may slow down the traveller. For example, the connection between B and E, and B and D are of different distances, but both have a weight of 4. Maybe the path between B and E is a smooth concrete path, but from B to D is a swampy path that is hard to traverse.

Given the weights that we've given to each edge, denoted by the numbers near each edge, the shortest path from A to F is: A->B->E->F. Because some edges are uni-directional, the shortest path from F to A is: F->D->B->E->C->A (in fact, that's the only path from F to A). We can also start on nodes besides A and F. For example, the shortest path from C to D is: C->E->F->D.

Below here you'll find the code, organized into main.cpp and three classes. Graph is the class that contains the algorithm and stores Nodes and Edges. And a class for Node, and a class for Edge.

First let's look at main.cpp so we can see how the graph is created and utilized:

#include <iostream>

#include "graph.h"
#include "node.h"

// NOTE: Credit for the original code for this implementation of 
// Djikstra's Algorithm goes to:
// http://www.reviewmylife.co.uk/blog/2008/07/15/dijkstras-algorithm-code-in-c/
// I've modified it to suit my needs.

void outputPath(std::vector<node> path)
{
    for ( long i = (path.size() - 1); i >= 0; --i )
    {
        std::cout << path[i]->getID() << " ";
    }
    
    std::cout << std::endl;
}

int main(int argc, const char * argv[])
{
    Graph graph;
    
    // Create and name our nodes
    Node* a = graph.createNode('a');
    Node* b = graph.createNode('b');
    Node* c = graph.createNode('c');
    Node* d = graph.createNode('d');
    Node* e = graph.createNode('e');
    Node* f = graph.createNode('f');
    
    // Create some edges
    graph.createEdge(a, b, 5);
    graph.createEdge(a, c, 4);
    graph.createEdge(b, d, 4);
    graph.createEdge(b, e, 4);
    graph.createEdge(c, e, 6);
    graph.createEdge(d, f, 3);
    graph.createEdge(e, f, 2);
    
    // Create some edges so we can get from 'f' to 'a'
    graph.createEdge(f, d, 3);
    graph.createEdge(d, b, 4);
    graph.createEdge(e, c, 6);
    graph.createEdge(c, a, 4);
 
    std::vector<node> path;

    // Go from 'c' to 'f'
    graph.getPathFromStartNodeToFinishNode(c, f, path);
    outputPath(path);
    
    // Go from 'a' to 'f'
    graph.getPathFromStartNodeToFinishNode(a, f, path);
    outputPath(path);
    
    // Go from 'f' to 'a'
    graph.getPathFromStartNodeToFinishNode(f, a, path);
    outputPath(path);
    
    return 0;
}

And below you'll find the three class .h/.cpp files.

graph.h

#pragma once

#include <vector>

class Node;
class Edge;

class Graph
{
public:
    Graph() {}
    ~Graph();
    
    Node* createNode(char id);
    Edge* createEdge(Node* node1, Node* node2, const int weight);
    void removeEdge(Edge* edge);
    
    void getPathFromStartNodeToFinishNode(Node* node1, Node* node2, std::vector<node>& path);

private:
    void processGraph();
    Node* extractSmallest(std::vector<node>& nodes);
    
private:
    std::vector<node> m_nodes;
    std::vector<edge> m_edges;
};

graph.cpp

#include "graph.h"
#include "node.h"
#include "edge.h"

#include <iostream>

Graph::~Graph()
{
    for ( int i = 0; i < m_nodes.size(); ++i )
    {
        delete m_nodes[i];
    }
    
    for ( int i = 0; i < m_edges.size(); ++i )
    {
        delete m_edges[i];
    }
}

Node* Graph::createNode(char id)
{
    Node* new_node = new Node(id);
    
    m_nodes.push_back(new_node);
    
    return new_node;
}

Edge* Graph::createEdge(Node* node1, Node* node2, const int weight)
{
    // Yes, we intentionally reverse the node order here
    Edge* new_edge = new Edge(node2, node1, weight);
    
    m_edges.push_back(new_edge);
    
    return new_edge;
}

void Graph::removeEdge(Edge* edge)
{
    std::vector<edge>::iterator it = m_edges.begin();
    for ( ; it < m_edges.end(); ++it)
    {
        if (*it == edge)
        {
     m_edges.erase(it);
     return;
        }
    }
}

void Graph::getPathFromStartNodeToFinishNode(Node* start, Node* finish, std::vector<node>& path)
{
    path.clear();
    
    // Clear any existing node information
    for ( int i = 0; i < m_nodes.size(); ++i )
    {
        m_nodes[i]->setDistanceFromStart(INT_MAX);
        m_nodes[i]->setPreviousNode(NULL);
    }
    
    start->setDistanceFromStart(0);
    
    processGraph();
    
    Node* previous = finish;

    while (previous)
    {
        path.push_back(previous);
        
        previous = previous->getPreviousNode();
    }
    
    if ( path.size() == 1 )
    {
        path.clear();
    }
}

void Graph::processGraph()
{
    // Create a copy of the nodes.
    std::vector<node> nodes = m_nodes;
    
    while (nodes.size() > 0)
    {
 Node* smallest = extractSmallest(nodes);
        
        std::vector<node> out_nodes;
        smallest->adjacentRemainingNodes(nodes, m_edges, out_nodes);
        
 const size_t size = out_nodes.size();
 for (int i = 0; i < size; ++i)
 {
     Node* adjacent = out_nodes[i];
            
     const int distance_to_node = adjacent->distanceToNode(m_edges, smallest);
            if ( distance_to_node == -1 )
            {
                continue;
            }
            
            const int total_distance = distance_to_node + smallest->getDistanceFromStart();   
     if ( total_distance < adjacent->getDistanceFromStart() )
     {
         adjacent->setDistanceFromStart(total_distance);
         adjacent->setPreviousNode(smallest);
     }
 }
    }
}

Node* Graph::extractSmallest(std::vector&ltnode&gt& nodes)
{
    if ( nodes.empty() )
    {
        return NULL;
    }
    
    int smallest_position = 0;
    
    Node* smallest = nodes[0];
    for ( int i = 1; i < nodes.size(); ++i )
    {
        Node* current = nodes[i];
        
        if ( current->getDistanceFromStart() < smallest->getDistanceFromStart() )
        {
            smallest = current;
            smallest_position = i;
        }
    }
    
    nodes.erase(nodes.begin() + smallest_position);
    
    return smallest;
}

node.h

#pragma once

#include <vector>

class Edge;

class Node
{
public:
    Node(char id) :
        id(id)
        , m_previous(NULL)
        , m_distance_from_start(INT_MAX)
    {
    }
    
    char getID() const                          { return id; }
    
    void setPreviousNode(Node* node)            { m_previous = node; }
    Node* getPreviousNode() const               { return m_previous; }
    
    void setDistanceFromStart(int distance)     { m_distance_from_start = distance; }
    int getDistanceFromStart() const            { return m_distance_from_start; }
    
    Node* extractSmallest(std::vector<node>& nodes);
    
    void adjacentRemainingNodes(const std::vector<node>& nodes, const std::vector<edge>& edges,
                                std::vector<node>& out_nodes) const;
    
    int distanceToNode(const std::vector<edge>& edges, const Node* other_node) const;
    
    bool contains(const std::vector<node>& nodes, const Node* node) const;
    
private:
    char    id;
    Node*   m_previous;
    int     m_distance_from_start;
};

node.cpp

#include "node.h"
#include "edge.h"

void Node::adjacentRemainingNodes(const std::vector<node>& nodes, const std::vector<edge>& edges,
                                  std::vector<node>& out_nodes) const
{
    const size_t size = edges.size();
    
    for(int i = 0; i < size; ++i)
    {
        const Edge* edge = edges[i];
        Node* adjacent = NULL;
        if (edge->first() == this)
        {
            adjacent = edge->second();
        }
        else if (edge->second() == this)
        {
            adjacent = edge->first();
        }
        
        if (adjacent && contains(nodes, adjacent))
        {
            out_nodes.push_back(adjacent);
        }
    }
}

int Node::distanceToNode(const std::vector<edge>& edges, const Node* other_node) const
{
    const size_t size = edges.size();
    for(int i = 0; i < size; ++i)
    {
        const Edge* edge = edges[i];
        if ( edge->connects(this, other_node) )
        {
            return edge->getDistance();
        }
    }

    // Happens if two nodes do not connect or the connection is directed in the opposite direction
    return -1;
}

bool Node::contains(const std::vector<node>& nodes, const Node* node) const
{
    for(int i = 0; i < nodes.size(); ++i)
    {
        if (node == nodes[i])
        {
            return true;
        }
    }
    
    return false;
}

edge.h

#pragma once

#include <vector>

class Node;

class Edge
{
public:
    Edge(Node* node1, Node* node2, int distance) :
        m_node1(node1)
      , m_node2(node2)
      , m_distance(distance)
    {
        // Assert that node1 and node2 aren't null and that distance is a positive value
    }
    
    Node* first() const           { return m_node1; }
    Node* second() const          { return m_node2; }
    int getDistance() const       { return m_distance; }
    
    bool connects(const Node* node1, const Node* node2) const;
    
private:
    Node* m_node1;
    Node* m_node2;
    int m_distance;
};

edge.cpp

#include "edge.h"
#include "node.h"

bool Edge::connects(const Node* node1, const Node* node2) const
{
    return ( (node1 == m_node1) && (node2 == m_node2) );
}

The Changes

The Graph class destructor made sure to clean up the nodes and edges to prevent memory leaks.
The original required you to keep track of all of your own pointers to nodes and edges and delete them.

Graph::~Graph()
{
    for ( int i = 0; i < m_nodes.size(); ++i )
    {
        delete m_nodes[i];
    }
    
    for ( int i = 0; i < m_edges.size(); ++i )
    {
        delete m_edges[i];
    }
}

Made edges directional while still allowing for bi-directional connections.
The original 'connects' method checked if the edge went in either direction, which made it so you could not have uni-directional edges.

#include "edge.h"
#include "node.h"

bool Edge::connects(const Node* node1, const Node* node2) const
{
    return ( (node1 == m_node1) && (node2 == m_node2) );
}

And here we handle the case where we don't get a valid distance from a distance check, which can happen if there is no possible path.

void Graph::processGraph()
{
    // Create a copy of the nodes.
    std::vector<Node*> nodes = m_nodes;
    
    while (nodes.size() > 0)
    {
        Node* smallest = extractSmallest(nodes);
        
        std::vector out_nodes;
        smallest->adjacentRemainingNodes(nodes, m_edges, out_nodes);
        
        const size_t size = out_nodes.size();
        for (int i = 0; i < size; ++i)
        {
     Node* adjacent = out_nodes[i];
            
            // We get the distance, if it's -1 then we know there is no possible path between the two nodes
     const int distance_to_node = adjacent->distanceToNode(m_edges, smallest);
            if ( distance_to_node == -1 )
            {
                continue;
            }
            
            const int total_distance = distance_to_node + smallest->getDistanceFromStart();   
     if ( total_distance < adjacent->getDistanceFromStart() )
     {
         adjacent->setDistanceFromStart(total_distance);
         adjacent->setPreviousNode(smallest);
     }
        }
    }
}

Allowing the Graph class to not remove nodes while calculating the shortest path, so the user can query the graph as often as they'd like without recreating it.
The key change from the original is that we make a copy of the list of nodes. The copies list is then whittled away by this function and then goes out of scope, the original would alter the 'm_nodes' list, thus requiring the user to recreate it after each time they queried for a new path.

void Graph::processGraph()
{
    // Create a copy of the nodes.
    std::vector<node> nodes = m_nodes;
    
    // ... Rest of function ...
}

Made a user-friendly method to allow the user to get a path between any two nodes.
The original required you to recreate the entire graph, and then manually set the distance on the start node to 0, and then run the algorithm. I don't have the graph nodes deleted after they process so here I clear out changes the nodes might be storing, then set the distance on the start node, then iterate through the nodes and save out the path. If the path only ends up with the last node in it then we know that there is no path to the start node.

void Graph::getPathFromStartNodeToFinishNode(Node* start, Node* finish, std::vector<node>& path)
{
    path.clear();
    
    // Clear any existing node information
    for ( int i = 0; i < m_nodes.size(); ++i )
    {
        m_nodes[i]->setDistanceFromStart(INT_MAX);
        m_nodes[i]->setPreviousNode(NULL);
    }
    
    start->setDistanceFromStart(0);
    
    processGraph();
    
    Node* previous = finish;

    while (previous)
    {
        path.push_back(previous);
        
        previous = previous->getPreviousNode();
    }
    
    if ( path.size() == 1 )
    {
        path.clear();
    }
}

Corrected inefficiencies
There were several places in the original code sample that included the use of std::vector's 'at' method. This method is around 5-10x slower than using the [] operator. 'at' performs a range check, which is unnecessary if your code is setup to prevent indices from going out of range. Additionally there were places where entire containers were being created on the heap (using 'new'), and then deleted within the same scope. These have been changed to use the stack instead, which is generally much more efficient.

As an example, here was the original method:

void Dijkstras()
{
    while (nodes.size() > 0)
    {
        Node* smallest = ExtractSmallest(nodes);
        vector<node>* adjacentNodes = 
            AdjacentRemainingNodes(smallest);

        const int size = adjacentNodes->size();
        for (int i=0; i<size; ++i)
        {
            Node* adjacent = adjacentNodes->at(i);
            int distance = Distance(smallest, adjacent) + smallest->distanceFromStart;
   
            if (distance < adjacent->distanceFromStart)
            {
                adjacent->distanceFromStart = distance;
                adjacent->previous = smallest;
            }    
        }
        delete adjacentNodes;
    }
}

And here you can see that we're creating a vector on the stack and passing it by reference to the 'adjacentRemainingNodes' method. Because it's not being created on the heap we also don't have to worry about deleting a pointer that was created by another method:

void Graph::processGraph()
{
    // Create a copy of the nodes.
    std::vector<Node*> nodes = m_nodes;
    
    while (nodes.size() > 0)
    {
        Node* smallest = extractSmallest(nodes);
        
        std::vector<node> out_nodes;
        smallest->adjacentRemainingNodes(nodes, m_edges, out_nodes);
        
        const size_t size = out_nodes.size();
        for (int i = 0; i < size; ++i)
        {
            Node* adjacent = out_nodes[i];
            
            const int distance_to_node = adjacent->distanceToNode(m_edges, smallest);
            if ( distance_to_node == -1 )
            {
                continue;
            }
            
            const int total_distance = distance_to_node + smallest->getDistanceFromStart();   
            if ( total_distance < adjacent->getDistanceFromStart() )
            {
                adjacent->setDistanceFromStart(total_distance);
                adjacent->setPreviousNode(smallest);
            }
        }
    }
}

The bounce-pad hack in LEGO Universe

The bounce-pads (also known as "bouncers") in LEGO Universe were a means of travel, when you stepped on them they sent you to a specific location in the map, usually somewhere nearby that you could not otherwise reach. Bounce-pads were one of the first gameplay elements created during the production of the game (almost 3 years before the game released), and had no real issues during the entire production run or alpha/beta testing, so we were all somewhat surprised to run into a huge bug on the very first day the game opened up to the public.

The whole company gathered in the gym around some big screen TVs so we could watch the game go live for the first time. We watched a few people get in the game and play for a short time and then we all scattered back to our desks so we could login and play the game ourselves. No sooner than had I created my first character I had a person from the live service team at my desk describing to me a serious bug. Apparently there were a large number of players that were stuck in the very first area of the game called "The Venture Explorer", a small spaceship that served as an introduction level to teach players them the basics. About two thirds of the way through the map there is a spot where you must quickbuild your first LEGO model, a bounce-pad, and afterwards you step on it and it bounces you to the next NPC to give you your next mission. It seemed that about 1 in 100 players would build the bounce-pad but could not step on it to get bounced, so they had no way to get to NPC to get the next mission. 

We had some in-game GMs talking with some of the players having this problem, and apparently they could see the bounce-pad but they couldn't step on it. The part of the code responsible for bouncing the player was the bounce-pad code that would set the player's velocity when the physics system told it that the player collided with the bounce-pad. Somewhere in that flow something was broken, and I wanted to find out what it was. We had nobody in the office that was experiencing this bug, none of our testers had seen it at any point during production either. Because we couldn't reproduce this in-house my next thought was to see what information I could get from the clients that were seeing the bug. As a gameplay programmer I didn't really know the details of what kinds of reporting and tools the live team had setup with the game to be able to get me information about this problem. As it turns out, there was almost nothing.

The client version of the game was setup to generate log messages for any errors, and there's a good chance the log file might tell me if something was amiss, like maybe the physics for the bounce-pad was failing to load, or if something was going wrong in the collision check. Sadly, the live team never got around to setting up a way for the clients to be able to send us their logs, or for a GM to be able to send a message to the client's program and have it return the logs to us. At the time they said something about possible legal reasons for us not getting information about them sent automatically to us, which seemed a bit ridiculous since the information didn't contain any account information besides the name of their in-game character, and a 32-bit account ID, which even if it got into the wrong hands is worthless. Anyway, getting any information from the client was impossible at the time.

Server log files were one thing I did have access to, unfortunately this was a client issue since not everyone was seeing it, and since the functionality to make the player bounce was entirely client-side, with only some server-side monitoring to check for cheating.

My next idea was to use some in-game tools that I had written during development, that created huge amounts of data about any object in the world. I was hoping I could use this tool to see if there might be any issues with the bounce-pad itself that the tool could find. The tool would analyze thousands of points of data on an object (at run-time) and check for any inconsistencies and report them back. This tool was not built into the version of the client that players used, so I would need to build an internal version of the client and log-in with it, additionally the server would not return the requested information unless you were using a GM account, for security reasons. It took awhile but finally I was given a temporary GM account to be able to analyze the problem, and still we were able to find nothing, mostly because the client information about the object was based on my client, which was working fine.

After about a day of sifting through logs and using tools to try and find any issues I could find nothing, and in the mean time GMs were having to sit in the game and teleport these players to the NPC so they could get their missions. The pressure was on to find a solution, but the only information I had to go on was that a small percentage of players were seeing a problem, and because this appeared to be a client-side problem and there was no system to get client logs back to me, there was nothing I could put in the game to get me any information about the problem. The reason this problem was on me was because I had written the bounce-pad system, the system that now appeared to be broken.

I enlisted the help of a couple fellow gameplay programmers to try and see what we could do to reproduce the problem in-house. We tried removing the physics asset from the computer to see how the game would react, and when starting the game the patching system would see the missing asset and simply download it again. There were code paths that could be hit if a physics file failed to load, so we put in some code to force the physics asset to fail to load, and in that case the game put in a fallback physics shape (a 1x1x1 cube), and even though that wasn't the proper shape it was still enough the player could touch it and the system would respond and bounce them, so that was a no-go. We checked to see if maybe the collision could be succeeding and somehow the bounce-pad code was failing to translate that into a bounce, but we couldn't see any point of failure, or a way to force it to fail.

So here we are with a problem we cannot produce, and a system we can't seem to make fail, and no way to get any information from the players that were seeing the problem. Leaving the bug as-is was unacceptable, as it would mean a lot of lost customers or the expense of GMs permanently stationed near the broken bounce-pad to teleport players. So the solution, was a hack.

During early development of LEGO Universe, almost all gameplay was entirely server-based. Things like attacking, picking up power-ups on the ground, and using bounce-pads were done entirely on the server and then the server would inform the client of the event. This was very secure but it resulted in laggy gameplay, which didn't work well for an action game like LEGO Universe. Along with other systems the bounce-pads were made so that the client-side object did the bouncing of the player, and simply told the server what it had done so that the server could check for any possible cheating or hacking. So, remembering that it used to work on the server years ago, and that the bounce-pads were still properly loading on the server, the solution presented itself. I put in code on the server so that if the player stood on a bounce-pad for more than half of a second and did not get a message from the client's bounce-pad that they've bounced, that it would assume the bounce-pad on the client was broken and bounce the player from the server. The result was that for those 1 in 100 players seeing the problem, that one bounce-pad on the first level would feel a little bit laggy but it would work. We also setup some server-side logging for any time the server-side bounce-pad needed to take over, and we found that we were only ever seeing the logging for that one bounce-pad in the first level of the game. For some reason that we never tracked down, it was only ever that one asset that exhibited this problem in the game, there was never another problem related to the physics for an asset not properly loading. 

We did make the assumption that the physics were likely failing somehow on those clients, because the only way we weren't able to bounce on the client was if a physics collision message was never sent to the bouncer, so I do feel some comfort in that the system I wrote may not have been the problem, it just affected my system. Even though as a team we take responsibility for the entire product, rather than saying "this is my code, that is your code", it's still feels good when you've written a system that works well, so you never want to see it break down and fail. It remains the biggest hack that I've ever made to a released product, but I don't feel bad about it, I feel like I made the best of the situation with what I was given, and in the end the players never knew the difference. 

QuickStart Game Engine v0.25 Preview: Buoyancy/Density Physics

I'm currently working on v0.25 of the QuickStart Game Engine, which will include a handful of performance enhancements, but most of the work has gone into a new component called WaterVolumePhysicsComponent. This component lets you describe a volumetric region in which water physics will be applied to any dynamic physics body, this means that water will now apply drag to anything within it, it will apply a weight to objects as they leave the water (because they're still "wet"), and it will take into account the density differences between the water and the physics body, allowing less dense entities to float, and denser entities to sink. The density differences between the body and water will also determine if the entity just barely sits near the top of the water, or if it's incredibly light it will float almost entirely on top of the water.

In previous versions of the engine there has been a yellow sphere that could be fired by pressing spacebar, in the new demo there will be two new spheres, a blue one fired by pressing Left Ctrl, and a red one fired by pressing Left Shift. The blue sphere will be extremely light, letting it rise very quickly out of the water and float almost entirely on top of the water, the yellow sphere will be medium density which is slightly less dense than water, letting it float to the top but not sit as high above the water as the blue sphere, and the red sphere will be very heavy and dense, letting it sink to the bottom of the water.

Density is really all that matters in terms of buoyancy in the water, but it also affects the amount of force and momentum an object has; All 3 spheres are the same size, but different densities, so each sphere weighs much differently than another. If you fire a blue sphere at one of the wooden crates in the demo, it doesn't have enough weight to move the crate almost at all, but the yellow sphere can give it a small nudge because it's a higher weight, and the red sphere can knock the crates around pretty good because they're much heavier than the crates. It is fun to fire the different spheres at things and watch how they act differently in the water.

I expect version 0.25 to be released in the next week or two.

Why Gamebryo was "fun"

If you didn't catch it in the title, there was some sarcasm in there. Gamebryo (the game engine used to make LEGO Universe as well as other titles such as Fallout 3, Oblivion, Epic Mickey, and more) had some very annoying quirks that made my life a little bit more difficult, as well as some of my coworkers'.

Both the Matrix and the Quaternion classes had multiple ways to create rotations, and naturally Gamebryo used no naming convention between these two classes.

Create a Rotation from the X axis and an angle?
Matrix function: MakeXRotation(float angle)
Quaternion function: FromAngleAxisX(float angle)

Gamebryo included a lot of functionality in either the Matrix or Quaternion classes, but not both. It's like a cruel joke.

Want to make your matrix an identity matrix? Call 'MakeIdentity( )'. Want to do that with a Quaternion? Do it yourself, there is no function.

Want to lerp (linearly interpolate) a Quaternion? Go for it. Want to lerp a Matrix? Sorry, convert it to a Quaternion, lerp it, then convert it back to a matrix. On top of that, the Slerp (spherical linear interpolation) did not even work properly with Gamebryo, often causing objects to rotate 350 degrees to get to the target, rather than 10 degrees. We ended up discontinuing the use of Gamebryo's Slerp method altogether and calling to Havok to have it do the rotations for us. Alternatively we could have just rolled our own Slerp code or altered Gamebryo's version to use ours, but Gamebryo made calls internally to its Slerp method so we didn't want to break something by fixing something.

Gamebryo also thought it would be cute to use opposite rotation directions for matrices vs. quaternions. Those two rotation functions I listed earlier, if you want to represent the same rotation with a matrix as well as a quaternion you pass a positive angle into one, and a negative angle into the other. It's always fun to try and remember which way you need to rotate which type depending on the case you were using it in. Gamebryo likes to make sure the programmer is paying attention I guess.

Here's another little chestnut that Gamebryo left me to deal with. Their camera coordinate system has a 'forward' vector of X, rather than Z. Seriously? What game has EVER done that? For those new to game programming, about 90% of games use the X-axis as a 'right' vector, and Z as a 'forward', the other 10% use the Y-axis as the forward and the Z-axis as the 'up'. But I had never seen an X-axis be used for a 'forward' before. There was no way we were going to use the X-axis as the forward for LEGO Universe, so we ended up having to deal with Gamebryo's wacky camera coordinate system. It was always a fun task when trying to do something that involved aligning the camera based on a rotation that was in another system, you'll set them to the same rotations and then rotate the camera 90 degrees to line it up.

I might go more into some annoyances using Gamebryo later, but for now I'm still bound to an NDA on most subjects.

Optimizing methods, Unitizing vectors

Speeding up small but often used functions can have a big result if they're something you're doing many times each frame.

In this post we'll look at a very commonly used technique in 3D game programming, unitizing/normalizing of a 3D vector. Unitizing vectors is needed for all kinds of things like finding distances, angles between directions (dot product), A.I., rendering techniques, finding cross products.

void Vector3::Unitize()
{
    x /= GetLength();
    y /= GetLength();
    z /= GetLength();
}

The above version of Unitize() is easy readable, but about as far from optimized as you can get. The compiler may optimize this a bit for you, but lets do as much as we can ourselves to see what could be faster.

1.) We're calling GetLength()three times, we should call it once and use that result instead. Length is somewhat expensive because it requires using a square root calculation.

2.) Rather than dividing each component by 'length', we could multiply each component by 1.0f / length. Multiplications are almost always faster than division.

3.) Rather than multiplying each component by 1.0f / length we could store 1.0f / length in a variable and use that in place to save 2 extra division calculations.

4.) Declare our function inline, which helps the chances that the compiler will choose to inline the method in the final machine code, which saves a function call. Standard function calls have a small expense to them.

Let's see what we have ended up with:

inline void Vector3::Unitize()
{
    const float inverseLength = 1.0f / GetLength(); 
    x *= inverseLength;
    y *= inverseLength;
    z *= inverseLength;
}

Please note, premature optimization can be wasteful, I prefer to wait until my program is having performance issues, and then I profile to find out what is slow and then target that. Even if a profiler told you that your normalization function was taking up a lot of your program's time, you might find that the compiler has already optimized it to the level we see above. You might be better off finding ways to not call certain functions as often as you are, for example, to help improve performance, rather than optimize the functions themselves. Also, anytime you try and optimize something that is already working you have a chance of causing new bugs, or possibly making performance worse rather than better. But, knowledge is power, if you know an efficient way of doing something, and you know it works, then you might as well do it that way the first time.