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.

Code structure: Cleanliness and efficiency

There are many ways to help make your code more readable, less bug-prone, and even more efficient. These are ignored by so many people whose code I've seen that I've decided to post about it. To many of you this stuff may be considered common sense, and that's a good thing.

Early out with conditionals when appropriate. This prevents your conditionals from nesting.

Bad:

void processMapNodes()
{
    if ( !map.hasBeenProcessed() )
    {
        map.process();

        // Other stuff here

        map.setProcessed(true);
    }
}

Good:

void processMapNodes()
{
    if ( map.hasBeenProcessed() )
    {
        return;
    }

    map.process();

    // Other stuff here

    map.setProcessed(true);
}

Early out with for loops. If you have to loop to find something, break out as soon as you've found it.

Bad:

void removeMapNodeByName(const std::string& name)
{
    for ( int i = 0; i < map_nodes.size(); ++i )
    {
        if ( map_nodes[i].getName() == name )
        {
            // Possibly some stuff here

            map_nodes.erase( map_nodes.begin() + i );
        }
    }
}

Better:

void removeMapNodeByName(const std::string& name)
{
    for ( int i = 0; i < map_nodes.size(); ++i )
    {
        if ( map_nodes[i].getName() == name )
        {
            // Possibly some stuff here

            map_nodes.erase( map_nodes.begin() + i );
    
            // We've found what we're looking for, so we break and stop looping
            break;
        }
    }
}

Best: (Use a conditional to continue as soon as possible)

void removeMapNodeByName(const std::string& name)
{
    for ( int i = 0; i < map_nodes.size(); ++i )
    {
        if ( map_nodes[i].getName() != name )
        {
            continue;
        }

        // Possibly some stuff here

        map_nodes.erase( map_nodes.begin() + i );
        break;
    }
}

Some of these examples are just to give you an idea of how to break out of code as soon as possible, but sometimes you can get even more efficient. In the example above we're simply going through a vector of data and looking for a match and then removing it. If what you're doing is really that trivial then you can use the standard library remove_if algorithm to do that for you. There are good examples of that, here, and here.

Don't nest your conditionals unnecessarily

Bad: Here we have nested conditionals, it starts to get messy

void foo(Bar* pBar)
{
    if ( pBar )
    {
        if ( pBar->hasData() )
        {
            Data* pData = pBar->getData();
            
            for ( int i = 0; i < pData->size(); ++i )
            {
                if ( pData[i].needsProcessing() )
                {
                    pData[i].process();
                }
            }
        }
    }
}

Good: We unnest our if statements and leave the for loop as soon as possible.

void foo(Bar* pBar)
{
    if ( !pBar || !pBar->hasData() )
    {
        return;
    }
     
    Data* pData = pBar->getData();
            
    for ( int i = 0; i < pData->size(); ++i )
    {
        if ( !pData[i].needsProcessing() )
        {
            continue;
        }

        // Do a bunch of stuff here

        pData[i].process();
    }
}

Create data only once it's needed

Bad: We're creating 'node_pos' at a point before we might exit the function early. This is wasteful and unnecessary.

void moveToMapNode(const std::string& name)
{
    Vector3 node_pos;

    if ( map_nodes.empty() )
    {
        return;
    }

    for ( int i = 0; i < map_nodes.size(); ++i )
    {
        if ( map_nodes[i].getName() != name )
        {
            continue;
        }

        node_pos = map_nodes[i].getPosition();
        break;
    }

    player.setPosition( node_pos );
}

Better: We create node_pos after any point were we could leave the function early, so we're never creating it when it might not be needed.

void moveToMapNode(const std::string& name)
{
    if ( map_nodes.empty() )
    {
        return;
    }

    Vector3 node_pos;

    for ( int i = 0; i < map_nodes.size(); ++i )
    {
        if ( map_nodes[i].getName() != name )
        {
            continue;
        }

        node_pos = map_nodes[i].getPosition();
        break;
    }

    player.setPosition( node_pos );
}

Best: We don't need to create a named variable 'node_pos', and it doesn't need to be used in as large of a scope as it was, we can use the position we get directly within the for loop.

void moveToMapNode(const std::string& name)
{
    if ( map_nodes.empty() )
    {
        return;
    }

    for ( int i = 0; i < map_nodes.size(); ++i )
    {
        if ( map_nodes[i].getName() != name )
        {
            continue;
        }

        // This is still fairly clear, even though we have a function call within a function call.
        // I wouldn't recommend nesting function calls any deeper than this, or debugging them 
        // and their return values can get messy if you end up with any bugs.
        player.setPosition( map_nodes[i].getPosition() );
        break;
    }
}

Sort your conditionals such that the cheapest ones are evaluated first, or the one most likely to evaluate positively is evaluated first.

Bad: We're calling the more expensive function first. Both functions in the conditional must be true for us to continue, so we should be calling the cheap function first, and if it returns false there is no need to call the expensive function.

void someFcn()
{
    if ( isExpensiveFcnTrue() && isCheapFcnTrue() )
    {
        // Do stuff here
    }
}

Good: We're calling the least expensive function first.

void someFcn()
{
    if ( isCheapFcnTrue() && isExpensiveFcnTrue() )
    {
        // Do stuff here
    }
}

Bad: We're placing the cheaper methods first, however, if they're functions that are true most of the time then we're still likely to have to evaluate all of the functions, even the expensive one that is usually false.

void someFcn()
{
    if ( cheapFcnThatUsuallyReturnsTrue() 
      && someOtherCheapFcnThatsUsuallyTrue() 
      && moderatelyExpensiveButUsuallyFalse() )
    {
        // Do stuff here
    }
}

Good: We call the more expensive method first, because it usually returns false, allowing us to skip the calls to the less expensive functions that usually return true. Basically your goal is to pay the lowest overall cost in your conditional statement, sometimes that will be calling cheaper methods first to avoid having to call expensive ones, if all of the functions stand similar chances of returning positive values, and sometimes you'll want to call more expensive ones first if it means you can save yourself numerous calls to other methods afterward. You'll need to make a judgement call based on the expense of the methods and what allows you to bail out as early as possible.

void someFcn()
{
    if ( moderatelyExpensiveButUsuallyFalse() 
      && cheapFcnThatUsuallyReturnsTrue() 
      && someOtherCheapFcnThatsUsuallyTrue() )
    {
        // Do stuff here
    }
}

If you're using || in your conditional, then you want to evaluate to true as soon as you can in your conditional, if you have && then you want to evaluate to false as soon as possible. Whatever the logic you're using, you want to do the least amount of work as possible to terminate the conditional check early and/or cheaply. This isn't only the most efficient, but it can make it easier to debug as you're not having to step through as much code when you exit early.

Cache results from an expensive algorithm or method that you might be calling more than once.

The compiler cannot optimize out multiple calls to the same function, unless those functions are purely constant expressions, so it's up to you to do it.

Bad: Here we're calling numCompletedNodes() more than once.

void displayCompletedNodeCount()
{
    // Let's pretend that 'numCompletedNodes()' has a big O of N*log(n) each time it's called.

    // If the player has completed any nodes in the map
    if ( numCompletedNodes() > 0 )
    {
        // We update the UI to display the number of completed nodes
        ui_interface->updateNodeCount( numCompletedNodes() );
    }
}

Better: We cache the number of nodes so we don't have to call the function each time we use it.

void displayCompletedNodeCount()
{
    // Let's pretend that 'numCompletedNodes()' has a big O of N*log(n) each time it's called.

    const unsigned int num_completed_nodes = numCompletedNodes();

    // If the player has completed any nodes in the map
    if ( num_completed_nodes > 0 )
    {
        // We update the UI to display the number of completed nodes
        ui_interface->updateNodeCount( num_completed_nodes );
    }
}

Best: If you really want to be more efficient, in this example it would probably be best to make sure that the numCompletedNodes() function is cheaper to call. Just from the example we can probably assume that it has to go through the map of nodes and calculate for each one if the player has completed it. That is probably information that could be stored on each node, which would bring the big O down to O(n). And you could go further and have a variable that keeps track of the completed node count as it changes, and then it would bring the cost down to O(1) (constant).