Game Loops

game_loops.cpp

	//----------------------
	// Gaffer On Games
	// https://gafferongames.com/post/fix_your_timestep/
	//----------------------

	// Fixed delta time
	// If delta time match the display refresh rate, and you can ensure that your update loop takes less than one frame worth of real time.
	double t = 0.0;
    double dt = 1.0 / 60.0;
    while (!quit) {
        integrate(state, t, dt);
        render(state);
        t += dt;
    }	
	
	// Variable delta time
	// Physics simulation depends on the delta time you pass in, game having a slightly different “feel” depending on framerate or extreme as your spring simulation exploding to infinity, fast moving objects tunneling through walls and players falling through the floor!
	double t = 0.0;
    double prev_time = hires_time_in_seconds();
    while (!quit) {
        double curr_time = hires_time_in_seconds();
        double frame_time = curr_time - prev_time;
        prev_time = curr_time;

        integrate(state, t, frame_time);
        t += frame_time;

        render(state);
    }
	
	// Semi-fixed timestep
	// Never pass in a delta time greater than the maximum value, while still running at the correct speed on different machines.
	double t = 0.0;
    double dt = 1 / 60.0;
    double prev_time = hires_time_in_seconds();
    while (!quit) {
        double curr_time = hires_time_in_seconds();
        double frame_time = curr_time - prev_time;
        prev_time = curr_time;
              
        while (frame_time > 0.0) {
            float delta_time = min(frame_time, dt);
            integrate(state, t, delta_time);
            frame_time -= delta_time;
            t += delta_time;
        }

        render(state);
    }
	
	// Free the physics First loop
	// A fixed delta time value for the simulation plus the ability to render at different framerates. 
	// Advance the physics simulation ahead in fixed dt time steps while also making sure that it keeps up with the timer values coming from the renderer so that the simulation advances at the correct rate. 
	double t = 0.0;
    const double dt = 0.01;
    double prev_time = hires_time_in_seconds();
    double accumulator = 0.0;
    while (!quit) {
        double curr_time = hires_time_in_seconds();
        double frameTime = curr_time - prev_time;
        prev_time = curr_time;

        accumulator += frameTime;

        while (accumulator >= dt) {
            integrate( state, t, dt );
            accumulator -= dt;
            t += dt;
        }

        render(state);
    }

	// Notice that unlike the semi-fixed timestep we only ever integrate with steps sized dt so it follows that in the common case we have some unsimulated time left over at the end of each frame. This left over time is passed on to the next frame via the accumulator variable and is not thrown away.
	// The final touch
	// But what do to with this remaining time? It seems incorrect doesn’t it?	
	// To understand what is going on consider a situation where the display framerate is 60fps and the physics is running at 50fps. There is no nice multiple so the accumulator causes the simulation to alternate between mostly taking one and occasionally two physics steps per-frame when the remainders “accumulate” above dt.
	// Now consider that the majority of render frames will have some small remainder of frame time left in the accumulator that cannot be simulated because it is less than dt. This means we’re displaying the state of the physics simulation at a time slightly different from the render time, causing a subtle but visually unpleasant stuttering of the physics simulation on the screen.
	//One solution to this problem is to interpolate between the previous and current physics state based on how much time is left in the accumulator:
	// Free the physics Final Loop
	double t = 0.0;
    double dt = 0.01;
    double prev_time = hires_time_in_seconds();
    double accumulator = 0.0;
    State previousState;
    State currentState;

    while (!quit) {
        double curr_time = time();
        double frame_time = curr_time - prev_time;
        if (frame_time > 0.25) {
            frame_time = 0.25;
		}		
        prev_time = curr_time;

        accumulator += frame_time;

        while (accumulator >= dt) {
            previousState = currentState;
            integrate(currentState, t, dt);
            t += dt;
            accumulator -= dt;
        }

        const double alpha = accumulator / dt;
        State state = currentState * alpha +  previousState * (1.0 - alpha);

        render(state);
    }
	
//=========================================================================================
	//------------------------------
	// Fabien Sanglard's Website
	// https://www.fabiensanglard.net/timer_and_framerate/index.php
	//------------------------------
	
	// Naive game loop
	// prev_time/lastTime, delta_time/timeSlice
	int prev_time = Timer_Gettime();
    while (1) {
      int curr_time = Timer_Gettime();
      int delta_time = curr_time - prev_time ;

      UpdateWorld(delta_time);
      RenderWorld();

      prev_time = curr_time;
    }

	// Fixed timeslices
	// Fix everything at the cost of a small latency: Update the game timer at a fixed rate inside a second loop.
	// Used in id Software engines or Starcraft II
    int simulationTime = 0;
    while (1) {
      int realTime = Gettime();

      while (simulationTime < realTime) {
             simulationTime += 16; //Timeslice is ALWAYS 16ms (60 FPS). 
             UpdateWorld(16);
      }

      RenderWorld();
    }


//=========================================================================================
	//------------------------------
	// Bob Nystrom
	// http://gameprogrammingpatterns.com/game-loop.html
	//------------------------------
	
// Fixed time step with no synchronization:
// Same as deWitter's The Game Loop
// You have no control over how fast the game runs. On a fast machine, that loop will spin so fast users won’t be able to see what’s going on. On a slow machine, the game will crawl.
while (true)
{
  processInput();
  update();
  render();
}


// Fixed time step with synchronization:
// Same as deWitter's FPS dependent on Constant Game Speed
// The sleep() here makes sure the game doesn’t run too fast if it processes a frame quickly. It doesn’t help if your game runs too slowly. If it takes longer than 16ms to update and render the frame, your sleep time goes negative.
while (true)
{
  double start = getCurrentTime();
  processInput();
  update();
  render();

  sleep(start + MS_PER_FRAME - getCurrentTime());
}

	
// Variable time step:
// Variable or fluid time step
// Same as Naive game loop of Fabien Sanglard's Website
// Same as deWitter's Game Speed dependent on Variable FPS
// The game plays at a consistent rate on different hardware. Players with faster machines are rewarded with smoother gameplay.
// But we’ve made the game non-deterministic and unstable.
// Fast Hardware, each time you add two floating point numbers, the answer you get back can be a bit off. Fred’s faster machine is doing ten times as many operations, so he’ll accumulate a bigger error than George. The same bullet will end up in different places on their machines.
// In order to run in real time, game physics engines are approximations of the real laws of mechanics. To keep those approximations from blowing up, damping is applied. That damping is carefully tuned to a certain time step. Vary that, and the physics gets unstable.
double prev_time = getCurrentTime();
while (true) {
  double curr_time = getCurrentTime();
  double elapsed = curr_time - prev_time;
  processInput();
  update(elapsed);
  render();
  prev_time = curr_time;
}


// Fixed update time step, variable rendering:
// Play catch up
// Same as Gaffer Free the physics First loop
// One part of the engine that usually isn’t affected by a variable time step is rendering. Since the rendering engine captures an instant in time, it doesn’t care how much time advanced since the last one. It renders things wherever they happen to be right then.
// We’ll update the game using a fixed time step because that makes everything simpler and more stable for physics and AI. But we’ll allow flexibility in when we render in order to free up some processor time.
// At the beginning of each frame, we update lag based on how much real time passed. This measures how far the game’s clock is behind compared to the real world. We then have an inner loop to update the game, one fixed step at a time, until it’s caught up. Once we’re caught up, we render and start over again.
// MS_PER_UPDATE is just the granularity we use to update the game. The shorter this step is, the more processing time it takes to catch up to real time. The longer it is, the choppier the gameplay is. Ideally, you want it pretty short, often faster than 60 FPS, so that the game simulates with high fidelity on fast machines.
// But be careful not to make it too short. You need to make sure the time step is greater than the time it takes to process an update(), even on the slowest hardware. Otherwise, your game simply can’t catch up.
double prev_time = getCurrentTime();
double lag = 0.0;
while (true) {
	double curr_time = getCurrentTime();
	double elapsed = curr_time - prev_time;
	prev_time = curr_time;
	lag += elapsed;

	processInput();

	while (lag >= MS_PER_UPDATE) {
		update();
		lag -= MS_PER_UPDATE;
	}

	// Render at arbitrary points in time, display at a point in time between two updates.
	//render();
	// Extrapolate moving objects like bullets.
	render(lag / MS_PER_UPDATE);
}

// There’s one issue we’re left with, and that’s residual lag. We update the game at a fixed time step, but we render at arbitrary points in time. This means that from the user’s perspective, the game will often display at a point in time between two updates.
// Imagine a bullet is flying across the screen. On the first update, it’s on the left side. The second update moves it to the right side. The game is rendered at a point in time between those two updates, so the user expects to see that bullet in the center of the screen. With our current implementation, it will still be on the left side. This means motion looks jagged or stuttery.
// Conveniently, we actually know exactly how far between update frames we are when we render: it’s stored in lag. We bail out of the update loop when it’s less than the update time step, not when it’s zero. That leftover amount? That’s how far into the next frame we are.
// When we go to render, we’ll pass that in:
render(lag / MS_PER_UPDATE);
// The renderer knows each game object and its current velocity. Say that bullet is 20 pixels from the left side of the screen and is moving right 400 pixels per frame. If we are halfway between frames, then we’ll end up passing 0.5 to render(). So it draws the bullet half a frame ahead, at 220 pixels. Ta-da, smooth motion.
// Of course, it may turn out that that extrapolation is wrong. When we calculate the next frame, we may discover the bullet hit an obstacle or slowed down or something. We rendered its position interpolated between where it was on the last frame and where we think it will be on the next frame. But we don’t know that until we’ve actually done the full update with physics and AI.
// So the extrapolation is a bit of a guess and sometimes ends up wrong. Fortunately, though, those kinds of corrections usually aren’t noticeable. At least, they’re less noticeable than the stuttering you get if you don’t extrapolate at all.
// You have to tune the update time step to be both as small as possible for the high-end, while not being too slow on the low end.

//=========================================================================================
	//------------------------------
	// deWiTTERS Game Loop
	// https://dewitters.com/dewitters-gameloop/
	//------------------------------
	
// FPS - FPS is an abbreviation for Frames Per Second. It is the number of times render() is called per second.
// Game Speed - Game Speed is the number of times the game state gets updated per second, the number of times update_game() is called per second. 

// FPS dependent on Constant Game Speed
// Same as Bob Nystrom Fixed time step with synchronization
// MS_PER_FRAME or SKIP_TICKS
const int FRAMES_PER_SECOND = 60; //25;
const int MS_PER_FRAME = 1000 / FRAMES_PER_SECOND;
DWORD start = getCurrentTime();
// getCurrentTime() or GetTickCount() returns the current number of milliseconds that have elapsed since the system was started
int sleep_time = 0;
while(!quit) {
	update();
	render();

	start += MS_PER_FRAME;
	sleep_time = start - getCurrentTime();
	if( sleep_time >= 0 ) {
		Sleep( sleep_time );
	}
	else {
		// We are running behind!
	}
}
// Slow hardware
// When the hardware can’t handle it. The game will run slower. In the worst case the game has some heavy chunks where the game will run really slow, and some chunks where it runs normal. The timing becomes variable which can make your game unplayable.
// Fast hardware
// The game will have no problems on fast hardware, but you are wasting so many precious clock cycles. Running a game on 25 or 30 FPS when it could easily do 300 FPS. You will lose a lot of visual appeal with this, especially with fast moving objects. On the other hand, with mobile devices, this can be seen as a benefit. Not letting the game constantly run at it’s edge could save some battery time.
// Conclusion
// Making the FPS dependent on a constant game speed is a solution that is quickly implemented and keeps the game code simple. But there are some problems: Defining a high FPS will pose problems on slower hardware, and defining a low FPS will waste visual appeal on fast hardware.


// Game Speed dependent on Variable FPS
// Same as Naive game loop of Fabien Sanglard's Website
// Same as Bob Nystrom Variable time step
DWORD prev_frame_tick;
DWORD curr_frame_tick = GetTickCount();
bool game_is_running = true;
while( game_is_running ) {
	prev_frame_tick = curr_frame_tick;
	curr_frame_tick = GetTickCount();

	update_game( curr_frame_tick - prev_frame_tick );
	display_game();
}
// The game code becomes a bit more complicated because we now have to consider the time difference in the update_game() function.
// Slow Hardware
// Slow hardware can sometimes cause certain delays at some points, where the game gets “heavy”. This can definitely occur with a 3D game, where at a certain time too many polygons get shown. This drop in frame rate will affect the input response time, and therefore also the player’s reaction time. The updating of the game will also feel the delay and the game state will be updated in big time-chunks. As a result the reaction time of the player, and also that of the AI, will slow down and can make a simple maneuver fail, or even impossible. For example, an obstacle that could be avoided with a normal FPS, can become impossible to avoid with a slow FPS. A more serious problem with slow hardware is that when using physics, your simulation can even explode!
// Fast Hardware
// Because we have more additions at 100 fps, the rounding error has more chance to get big. So the game will differ when running at 40 or 100 frames per second:
// A small floating point error can become big can make trouble for game at high frame rates. Chances of that happening? Big enough to consider it.
// Conclusion
// This kind of game loop may seem very good at first sight, but don’t be fooled. Both slow and fast hardware can cause serious problems for your game. And besides, the implementation of the game update function is harder than when you use a fixed frame rate, so why use it?


// Constant Game Speed with Maximum FPS
// The game will be updated at a steady 50 times per second, and rendering is done as fast as possible. Remark that when rendering is done more than 50 times per second, some subsequent frames will be the same, so actual visual frames will be dispayed at a maximum of 50 frames per second. When running on slow hardware, the framerate can drop until the game update loop will reach MAX_FRAMESKIP. In practice this means that when our render FPS drops below 5 (= FRAMES_PER_SECOND / MAX_FRAMESKIP), the actual game will slow down.
const int TICKS_PER_SECOND = 50;
const int SKIP_TICKS = 1000 / TICKS_PER_SECOND;
const int MAX_FRAMESKIP = 10;
DWORD prev_time = getCurrentTime();
int loops;
while(!quit) {
	loops = 0;
	while( getCurrentTime() > prev_time && loops < MAX_FRAMESKIP) {
		update_game();
		prev_time += SKIP_TICKS;
		loops++;
	}

	display_game();
}
// Slow hardware
// On slow hardware the frames per second will drop, but the game itself will hopefully run at the normal speed. If the hardware still can’t handle this, the game itself will run slower and the framerate will not be smooth at all.
// Fast hardware
// The game will have no problems on fast hardware, but like the first solution, you are wasting so many precious clock cycles that can be used for a higher framerate. Finding the balance between a fast update rate and being able to run on slow hardware is crucial.
// Conclusion
// Using a constant game speed with a maximum FPS is a solution that is easy to implement and keeps the game code simple. But there are still some problems: Defining a high FPS can still pose problems on slow hardware (but not as severe as the first solution), and defining a low FPS will waste visual appeal on fast hardware. 


// Constant Game Speed independent of Variable FPS
// The game state itself doesn’t need to be updated 60 times per second. Player input, AI and the updating of the game state have enough with 25 frames per second. So let’s try to call the update_game() 25 times per second, no more, no less. The rendering, on the other hand, needs to be as fast as the hardware can handle. But a slow frame rate shouldn’t interfere with the updating of the game.
const int TICKS_PER_SECOND = 25;
const int SKIP_TICKS = 1000 / TICKS_PER_SECOND;
const int MAX_FRAMESKIP = 5;

DWORD prev_time = getCurrentTime();
int loops;
float interpolation;
while(!quit) {
	loops = 0;
	while( getCurrentTime() > prev_time && loops < MAX_FRAMESKIP) {
		update_game();
		prev_time += SKIP_TICKS;
		loops++;
	}
	interpolation = float( getCurrentTime() + SKIP_TICKS - prev_time ) / float( SKIP_TICKS );
	display_game( interpolation );
}

// With this kind of game loop, the implementation of update_game() will stay easy. But unfortunately, the display_game() function gets more complex. You will have to implement a prediction function that takes the interpolation as argument.
// The gamestate gets updated 25 times per second, so if you don’t use interpolation in your rendering, frames will also be displayed at this speed. 25 fps should be enough for a visually pleasing experience, but for fast moving objects, we can still see a improvement when doing more FPS. So what we can do is make fast movements more smooth in between the frames. And this is where interpolation and a prediction function can provide a solution.

// Interpolation and Prediction -
// Like I said the game code runs on it’s own frames per second, so when you draw/render your frames, it is possible that it’s in between 2 gameticks. Let’s say you have just updated your gamestate for the 10Th time, and now you are going to render the scene. This render will be in between the 10Th and 11Th game update. So it is possible that the render is at about 10.3. The ‘interpolation’ value then holds 0.3. Take this example: I have a car that moves every game tick like this:
    // position = position + speed;

// If in the 10Th gametick the position is 500, and the speed is 100, then in the 11Th gametick the position will be 600. So where will you place your car when you render it? You could just take the position of the last gametick (in this case 500). But a better way is to predict where the car would be at exact 10.3, and this happens like this:
    // view_position = position + (speed * interpolation)

// The car will then be rendered at position 530. So basically the interpolation variable contains the value that is in between the previous gametick and the next one (previous = 0.0, next = 1.0). What you have to do then is make a “prediction” function where the car/camera/… would be placed at the render time. You can base this prediction function on the speed of the object, steering or rotation speed. It doesn’t need to be complicated because we only use it to smooth things out in between the frames. It is indeed possible that an object gets rendered into another object right before a collision gets detected. But like we have seen before, the game is updated 25 frames per second, and so when this happens, the error is only shown for a fraction of a second, hardly noticeable to the human eye.
// Slow Hardware
// In most cases, update_game() will take far less time than display_game(). In fact, we can assume that even on slow hardware the update_game() function can run 25 times per second. So our game will handle player input and update the game state without much trouble, even if the game will only display 15 frames per second.
// Fast Hardware
// On fast hardware, the game will still run at a constant pace of 25 times per second, but the updating of the screen will be way faster than this. The interpolation/prediction method will create the visual appeal that the game is actually running at a high frame rate. The good thing is that you kind of cheat with your FPS. Because you don’t update your game state every frame, only the visualization, your game will have a higher FPS than with the second method I described.
// Conclusion
// Making the game state independent of the FPS seems to be the best implementation for a game loop. However, you will have to implement a prediction function in display_game().

// Overall Conclusion
// A constant frame rate can be a good and simple solution for mobile devices, but when you want to get everything the hardware has got, best use a game loop where the FPS is completely independent of the game speed, using a prediction function for high framerates. If you don’t want to bother with a prediction function, you can work with a maximum frame rate, but finding the right game update rate for both slow and fast hardware can be tricky.