Test for catch-up. Document

4 files changed, 154 insertions, 47 deletions

diff --git a/simloop/CMakeLists.txt b/simloop/CMakeLists.txt
index 528e65f..2e0114b 100644
--- a/simloop/CMakeLists.txt
+++ b/simloop/CMakeLists.txt
@@ -24,6 +24,6 @@ target_link_libraries(simloop_test
   simloop
   ctest)
 
-target_compile_options(simloop_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -Wpedantic)
+target_compile_options(simloop_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -pedantic)
 
 add_test(NAME simloop_test COMMAND simloop_test --unittest)
diff --git a/simloop/README.md b/simloop/README.md
new file mode 100644
index 0000000..f45ca05
--- /dev/null
+++ b/simloop/README.md
@@ -0,0 +1,99 @@
+# Simulation loop module
+
+Simulation loop for games and graphics applications.
+
+## Features
+
+- Client retains control flow.
+- Client-controlled time axis.
+- Updates are frame-rate capped and use a fixed time step for determinism.
+- Rendering is optionally frame-rate capped.
+- Interpolation factor for smooth animation and rendering between frames.
+
+Control flow: the client steps the loop and then checks whether the simulation
+must be updated and/or the result rendered. Time readings are external to the
+library and provided by the client.
+
+## Invariants
+
+- An initial render of the initial application state is always triggered.
+- The same frame is not re-rendered if time does not advance.
+- Animation interpolation factor in [0,1].
+
+## Handling Time Spikes
+
+Generally, the simulation's update logic should be able to keep up with the
+requested frame rate; it is the application's responsibility to ensure this.
+Specifically, the frequency with which the application loops must be higher
+than the requested update frequency, given by the update delta time.
+
+However, occasional time spikes may occur, for example when switching to the
+desktop or when pausing the application in a debugger. The library handles this
+simply by requesting an update from the application. Under the assumption that
+the loop frequency is higher than the update frequency, the simulation will
+catch up with the real-time clock.
+
+### Time Spikes in Detail
+
+When a time spike occurs, the simulation clock falls significantly behind the
+real-time clock. Ideally, the simulation should be able to recover and catch up
+to the real-time clock when this occurs.
+
+Under a variable time delta, the loop could simply update the simulation with
+a large delta that puts the simulation back into the current clock time.
+Under a fixed time delta, this isn't possible, and we seem to have the
+following choices instead:
+
+- a) Queue as many updates as necessary to bring the simulation back to the
+  current clock time (time_difference / fixed_delta).
+- b) Queue a single update.
+- c) Some middle ground between the two.
+
+The issue with (a) is that, if the simulation is never able to catch up, then
+the number of requested updates at every loop iteration diverges and the
+simulation eventually appears to freeze.
+
+(b) only works if:
+
+- clock time added per iter < desired update delta time
+
+Where:
+
+- clock time added per iter = update time + render time + vsync + etc
+- desired delta time = 1 / update frequency
+
+If the clock time added per iteration is greater or equal to the desired delta,
+then the simulation can never "catch up" and recover from the spike.
+
+The middle ground is to perform only some number of updates in each loop
+iteration N. The simulation catches up only if:
+
+- clock time added per iter < N * desired update delta time
+
+The ideal value of N depends on how many frames the application can actually
+render. For example, if the application is vsync'ed to a 240hz monitor and is
+able to render that many frames, then:
+
+- N = ceil(1/240hz / desired update delta time)
+
+Realistically, the actual frame rate will be variable. Moreover, if we queued
+as many frames as possible, then we would risk the freeze in option (a) if the
+actual update time were too large for the application to catch up. So the
+library can only guess the value of N.
+
+The library picks a small constant value of N, implementation-defined, that the
+application can override.
+
+### Example: Spike Handling with Option (A)
+
+- desired delta = 10ms (100 fps)
+- actual delta = 20ms ( 50 fps)
+
+| iter | sim time | clock time | comment                       |
+|------|----------|------------|-------------------------------|
+| 0    | 0        | 0          | initial state                 |
+| 1    | 0        | 10         | queue 1 update                |
+| 2    | 10       | 30         | queue (30-10)/10  = 2 updates |
+| 3    | 30       | 70         | queue (70-30)/10  = 4 updates |
+| 4    | 70       | 150        | queue (150-70)/10 = 8 updates |
+| ...  |
diff --git a/simloop/include/simloop.h b/simloop/include/simloop.h
index 7774c35..4e3ed20 100644
--- a/simloop/include/simloop.h
+++ b/simloop/include/simloop.h
@@ -1,49 +1,3 @@
-/* Simulation loop module.
- *
- * This implements a simulation loop but in a way that the client retains
- * control flow. The client steps the loop and then checks whether the
- * simulation must be updated and/or the result rendered.
- *
- * The simulation is updated at a fixed time step given a desired frame rate.
- * Rendering frame rate can likewise be capped or be unlimited.
- * In any case, an interpolation factor is computed for smooth animation between
- * updates.
- * The implementation also guarantees that the same frame is not rendered twice
- * if time does not advance.
- *
- * Generally, the simulation's update logic should be able to keep up with the
- * requested frame rate; it is the application's responsibility to ensure this.
- * Should the update logic not be able to keep up, then the loop requests a
- * single update per iteration, effectively "degrading" to match the update
- * logic frame rate, giving the update logic a chance to catch up with
- * subsequent loop iterations.
- *
- * Under a variable time delta, the loop could simply update the simulation
- * with a large delta that puts the simulation back into the current clock
- * time. Under a fixed time delta this isn't possible, and we seem to have two
- * choices instead:
- *
- *   a) Queue as many updates as necessary to bring the simulation back to the
- *      current clock time (time_difference / fixed_delta).
- *
- *   b) Queue a single update.
- *
- * The issue with (a) is that, if the simulation is never able to catch up, then
- * the number of requested updates at every loop iteration diverges and
- * eventually the simulation appears to freeze. Example:
- *
- *   desired delta = 10ms (100 fps)
- *   actual  delta = 20ms ( 50 fps)
- *   ---------------------------
- *   iter, sim time, clock time
- *   ---------------------------
- *      0,        0,          0, initial state
- *      1,        0,         10, queue 1 update
- *      2,       10,         30, queue (30-10)/10  = 2 updates
- *      3,       30,         70, queue (70-30)/10  = 4 updates
- *      4,       70,        150, queue (150-70)/10 = 8 updates
- *      ...
- */
 #pragma once
 
 #include <stdint.h>
diff --git a/simloop/test/simloop_test.c b/simloop/test/simloop_test.c
index 50e0852..790ad73 100644
--- a/simloop/test/simloop_test.c
+++ b/simloop/test/simloop_test.c
@@ -250,4 +250,58 @@ TEST_CASE(simloop_determinism) {
   TEST_EQUAL(sim[0].sum, sim[1].sum);
 }
 
+/// The simulation loop attempts to catch up with the clock in the event of a
+/// time spike. This is possible only if the simulation loops with a frequency
+/// higher than the requested update frequency given by the update delta time.
+static void simloop_catch_up(
+    struct test_case_metadata* metadata, int update_ddt_ms, int loop_step_ms,
+    bool expect_catchup) {
+  const int            UPDATE_FPS = 1000 / update_ddt_ms;
+  const simloop_time_t UPDATE_DDT =
+      time_delta_from_sec(1.0 / (double)UPDATE_FPS);
+  const simloop_time_t STEP =
+      time_delta_from_sec((double)loop_step_ms / 1000.0);
+  const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
+  const int            EXPECTED_TOTAL_FRAMES_WITH_CATCHUP =
+      (int)(SIM_DURATION_SEC / UPDATE_DDT);
+
+  Simloop    simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
+  SimloopOut simout;
+  int        frames = 0;
+
+  // Simulate a time spike.
+  // Advance time to t=10s. That is a lag of 10,000ms / 100ms = 100 frames.
+  // The simulation now has 20s to catch up.
+  simloop_time_t dt = time_delta_from_sec(10);
+  for (simloop_time_t t = dt; t <= SIM_DURATION_SEC;) {
+    simloop_update(&simloop, dt, &simout);
+
+    if (simout.should_update) {
+      frames++;
+    }
+
+    // New delta is as usual.
+    dt = STEP;
+    t += dt;
+  }
+
+  if (expect_catchup) {
+    TEST_EQUAL(frames, EXPECTED_TOTAL_FRAMES_WITH_CATCHUP);
+  } else {
+    TEST_TRUE(frames < EXPECTED_TOTAL_FRAMES_WITH_CATCHUP);
+  }
+}
+/// (Loop frequency > update frequency) => successful catch-up.
+TEST_CASE(simloop_catch_up_success) {
+  constexpr int UPDATE_DDT_MS = 100;
+  constexpr int LOOP_DDT_MS   = 10;
+  simloop_catch_up(metadata, UPDATE_DDT_MS, LOOP_DDT_MS, true);
+}
+/// (Loop frequency < update frequency) => failed catch-up.
+TEST_CASE(simloop_catch_up_failure) {
+  constexpr int UPDATE_DDT_MS = 10;
+  constexpr int LOOP_DDT_MS   = 100;
+  simloop_catch_up(metadata, UPDATE_DDT_MS, LOOP_DDT_MS, false);
+}
+
 int main() { return 0; }