-
Notifications
You must be signed in to change notification settings - Fork 513
Expand file tree
/
Copy pathgame-loop.html
More file actions
689 lines (672 loc) · 43.1 KB
/
game-loop.html
File metadata and controls
689 lines (672 loc) · 43.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8" />
<title>Game Loop · Sequencing Patterns · Game Programming Patterns</title>
<!-- Tell mobile browsers we're optimized for them and they don't need to crop
the viewport. -->
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<link rel="stylesheet" type="text/css" href="style.css" />
<link href="https://fonts.googleapis.com/css?family=Merriweather:400,400italic,700,700italic|Source+Code+Pro|Source+Sans+Pro:200,300,400,600,400italic,600italic|Rock+Salt" rel="stylesheet" type="text/css">
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-42804721-1', 'gameprogrammingpatterns.com');
ga('send', 'pageview');
</script>
<script src="jquery-3.6.0.min.js"></script>
<script src="script.js"></script>
</head>
<body id="top">
<div class="page sidebar">
<span class="theme-toggler" title="dark theme" onclick="toggleTheme()"></span>
<div class="content">
<nav class="top">
<span class="prev">← <a href="double-buffer.html">Previous Chapter</a></span>
<span class="next"><a href="update-method.html">Next Chapter</a> →</span>
<span class="toc">≡ <a href="/">The Book</a></span>
</nav>
<h1>Game Loop</h1>
<h1 class="book"><a href="/">Game Programming Patterns</a><span class="section"><a href="sequencing-patterns.html">Sequencing Patterns</a></span></h1>
<h2><a href="#intent" name="intent">Intent</a></h2>
<p><em>Decouple the progression of game time from user input and processor speed.</em></p>
<h2><a href="#motivation" name="motivation">Motivation</a></h2>
<p>If there is one pattern this book couldn’t live without, this is it. Game loops
are the quintessential example of a “game programming pattern”. Almost every
game has one, no two are exactly alike, and relatively few programs outside of
games use them.</p>
<p>To see how they’re useful, let’s take a quick trip down memory lane. In the
olden days of computer programming when everyone had <span
name="beard">beards</span>, programs worked like your dishwasher. You dumped a
load of code in, pushed a button, waited, and got results out. Done. These were
<em>batch mode</em> programs — once the work was done, the program stopped.</p>
<aside name="beard">
<p>Ada Lovelace and Rear Admiral Grace Hopper had honorary beards.</p>
</aside>
<p>You still see these today, though thankfully we don’t have to write them on
punch cards anymore. Shell scripts, command line programs, and even the little
Python script that turns a pile of Markdown into this book are all batch mode
programs.</p>
<h3><a href="#interview-with-a-cpu" name="interview-with-a-cpu">Interview with a CPU</a></h3>
<p>Eventually, programmers realized having to drop off a batch of code at the
computing office and come back a few hours later for the results was a terribly
slow way to get the bugs out of a program. They wanted immediate feedback.
<em>Interactive</em> programs were born. Some of the first interactive programs were
games:</p>
<p><span name="cave"></span></p>
<div class="codehilite"><pre><span></span><code><span class="n">YOU</span><span class="w"> </span><span class="k">ARE</span><span class="w"> </span><span class="n">STANDING</span><span class="w"> </span><span class="k">AT</span><span class="w"> </span><span class="n">THE</span><span class="w"> </span><span class="k">END</span><span class="w"> </span><span class="k">OF</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">ROAD</span><span class="w"> </span><span class="k">BEFORE</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">SMALL</span><span class="w"> </span><span class="n">BRICK</span><span class="w"></span>
<span class="n">BUILDING</span><span class="w"> </span><span class="p">.</span><span class="w"> </span><span class="n">AROUND</span><span class="w"> </span><span class="n">YOU</span><span class="w"> </span><span class="k">IS</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">FOREST</span><span class="p">.</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">SMALL</span><span class="w"></span>
<span class="n">STREAM</span><span class="w"> </span><span class="n">FLOWS</span><span class="w"> </span><span class="k">OUT</span><span class="w"> </span><span class="k">OF</span><span class="w"> </span><span class="n">THE</span><span class="w"> </span><span class="n">BUILDING</span><span class="w"> </span><span class="ow">AND</span><span class="w"> </span><span class="n">DOWN</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">GULLY</span><span class="p">.</span><span class="w"></span>
<span class="o">></span><span class="w"> </span><span class="k">GO</span><span class="w"> </span><span class="ow">IN</span><span class="w"></span>
<span class="n">YOU</span><span class="w"> </span><span class="k">ARE</span><span class="w"> </span><span class="n">INSIDE</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">BUILDING</span><span class="p">,</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="n">WELL</span><span class="w"> </span><span class="n">HOUSE</span><span class="w"> </span><span class="k">FOR</span><span class="w"> </span><span class="n">A</span><span class="w"> </span><span class="k">LARGE</span><span class="w"> </span><span class="n">SPRING</span><span class="p">.</span><span class="w"></span>
</code></pre></div>
<aside name="cave">
<p>This is <a href="http://en.wikipedia.org/wiki/Colossal_Cave_Adventure">Colossal Cave
Adventure</a>, the first
adventure game.</p>
</aside>
<p>You could have a live conversation with the program. It waited for your input,
then it would respond to you. You would reply back, taking turns just like you
learned to do in kindergarten. When it was your turn, it sat there doing
nothing. Something like:</p>
<p><span name="exit"></span></p>
<div class="codehilite"><pre><span></span><code><span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">char</span><span class="o">*</span> <span class="n">command</span> <span class="o">=</span> <span class="n">readCommand</span><span class="p">();</span>
<span class="n">handleCommand</span><span class="p">(</span><span class="n">command</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div>
<aside name="exit">
<p>This loops forever, so there’s no way to quit the game. A real game would do
something like <code>while (!done)</code> and set <code>done</code> to exit. I’ve omitted that to keep
things simple.</p>
</aside>
<h3><a href="#event-loops" name="event-loops">Event loops</a></h3>
<p>Modern graphic UI applications are surprisingly similar to old adventure games
once you shuck their skin off. Your word processor usually just sits there doing
nothing until you press a key or click something:</p>
<div class="codehilite"><pre><span></span><code><span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">Event</span><span class="o">*</span> <span class="n">event</span> <span class="o">=</span> <span class="n">waitForEvent</span><span class="p">();</span>
<span class="n">dispatchEvent</span><span class="p">(</span><span class="n">event</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div>
<p>The main difference is that instead of <em>text commands</em>, the program is waiting
for <em>user input events</em> — mouse clicks and key presses. It still works
basically like the old text adventures where the program <span
name="idle"><em>blocks</em></span> waiting for user input, which is a problem.</p>
<p>Unlike most other software, games keep moving even when the user isn’t providing
input. If you sit staring at the screen, the game doesn’t freeze. Animations
keep animating. Visual effects dance and sparkle. If you’re unlucky, that
monster keeps chomping on your hero.</p>
<aside name="idle">
<p>Most event loops do have “idle” events so you can intermittently do stuff
without user input. That’s good enough for a blinking cursor or a progress bar,
but too rudimentary for games.</p>
</aside>
<p>This is the first key part of a real game loop: <em>it processes user input, but
doesn’t wait for it</em>. The loop always keeps spinning:</p>
<div class="codehilite"><pre><span></span><code><span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">processInput</span><span class="p">();</span>
<span class="n">update</span><span class="p">();</span>
<span class="n">render</span><span class="p">();</span>
<span class="p">}</span>
</code></pre></div>
<p>We’ll refine this later, but the basic pieces are here. <code>processInput()</code> handles
any user input that has happened since the last call. Then, <span
name="update"><code>update()</code></span> advances the game simulation one step. It runs
AI and physics (usually in that order). Finally, <code>render()</code> draws the game so
the player can see what happened.</p>
<aside name="update">
<p>As you might guess from the name, <code>update()</code> is a good place to use the <a
href="update-method.html" class="pattern">Update Method</a> pattern.</p>
</aside>
<h3><a href="#a-world-out-of-time" name="a-world-out-of-time">A world out of time</a></h3>
<p>If this loop isn’t blocking on input, that leads to the obvious question: how
<em>fast</em> does it spin? Each turn through the game loop advances the state of the
game by some amount. From the perspective of an inhabitant of the game world,
the hand of their clock has <span name="tick">ticked</span> forward.</p>
<aside name="tick">
<p>The common terms for one crank of the game loop are “tick” and “frame”.</p>
</aside>
<p>Meanwhile, the <em>player’s</em> actual clock is ticking. If we measure how quickly the
game loop cycles in terms of real time, we get the game’s “frames per second”.
If the game loop cycles quickly, the FPS is high and the game moves smoothly and
quickly. If it’s slow, the game jerks along like a stop motion movie.</p>
<p>With the crude loop we have now where it just cycles as quickly as it can, two
factors determine the frame rate. The first is <em>how much work it has to do each
frame</em>. Complex physics, a bunch of game objects, and lots of graphic detail all
will keep your CPU and GPU busy, and it will take longer to complete a frame.</p>
<p>The second is <em>the speed of the underlying platform.</em> Faster chips churn through
more code in the same amount of time. Multiple cores, GPUs, dedicated audio
hardware, and the OS’s scheduler all affect how much you get done in one tick.</p>
<h3><a href="#seconds-per-second" name="seconds-per-second">Seconds per second</a></h3>
<p>In early video games, that second factor was fixed. If you wrote a game for the
NES or Apple IIe, you knew <em>exactly</em> what CPU your game was running on and you
could (and did) code specifically for that. All you had to worry about was how
much work you did each tick.</p>
<p>Older games were carefully coded to do just enough work each frame so that the
game ran at the speed the developers wanted. But if you tried to play that same
game on a faster or slower <span name="turbo">machine</span>, then the game
itself would speed up or slow down.</p>
<aside name="turbo">
<p>This is why old PCs used to have
“<a href="http://en.wikipedia.org/wiki/Turbo_button">turbo</a>” buttons. New PCs were
faster and couldn’t play old games because the games would run too fast. Turning
the turbo button <em>off</em> would slow the machine down and make old games playable.</p>
</aside>
<p>These days, though, few developers have the luxury of knowing exactly what
hardware their game will run on. Instead, our games must intelligently adapt to
a variety of devices.</p>
<p>This is the other key job of a game loop: <em>it runs the game at a consistent
speed despite differences in the underlying hardware.</em></p>
<h2><a href="#the-pattern" name="the-pattern">The Pattern</a></h2>
<p>A <strong>game loop</strong> runs continuously during gameplay. Each turn of the loop, it
<strong>processes user input</strong> without blocking, <strong>updates the game state</strong>, and
<strong>renders the game</strong>. It tracks the passage of time to <strong>control the rate of
gameplay</strong>.</p>
<h2><a href="#when-to-use-it" name="when-to-use-it">When to Use It</a></h2>
<p>Using the wrong pattern can be worse than using no pattern at all, so this
section is normally here to caution against over-enthusiasm. The goal of design
patterns isn’t to cram as many into your codebase as you can.</p>
<p>But this pattern is a bit different. I can say with pretty good confidence that
you <em>will</em> use this pattern. If you’re using a game <span
name="engine">engine</span>, you won’t write it yourself, but it’s still there.</p>
<aside name="engine">
<p>For me, this is the difference between an “engine” and a “library”. With
libraries, you own the main game loop and call into the library. An engine owns
the loop and calls into <em>your</em> code.</p>
</aside>
<p>You might think you won’t need this if you’re making a turn-based game. But even
there, though the <em>game state</em> won’t advance until the user takes their turn,
the <em>visual</em> and <em>audible</em> states of the game usually do. Animation and music
keep running even when the game is “waiting” for you to take your turn.</p>
<h2><a href="#keep-in-mind" name="keep-in-mind">Keep in Mind</a></h2>
<p>The loop we’re talking about here is some of the most important code in your
game. They say a program spends <span name="percent">90%</span> of its time in
10% of the code. Your game loop will be firmly in that 10%. Take care with this
code, and be mindful of its efficiency.</p>
<aside name="percent">
<p>Made up statistics like this are why “real” engineers like mechanical and
electrical engineers don’t take us seriously.</p>
</aside>
<h3><a href="#you-may-need-to-coordinate-with-the-platform's-event-loop" name="you-may-need-to-coordinate-with-the-platform's-event-loop">You may need to coordinate with the platform’s event loop</a></h3>
<p>If you’re building your game on top of an OS or platform that has a graphic UI
and an event loop built in, then you have <em>two</em> application loops in play. They’ll
need to play nice together.</p>
<p>Sometimes, you can take control and make your loop the only one. For
example, if you’re writing a game against the venerable Windows API, your
<code>main()</code> can just have a game loop. Inside, you can call <code>PeekMessage()</code> to
handle and dispatch events from the OS. Unlike <code>GetMessage()</code>, <code>PeekMessage()</code>
doesn’t block waiting for user input, so your game loop will keep cranking.</p>
<p>Other platforms don’t let you opt out of the event loop so easily. If you’re
targeting a web browser, the event loop is deeply built into browser’s execution
model. There, the event loop will run the show, and you’ll use it as your game
loop too. You’ll call something like <code>requestAnimationFrame()</code> and it will
call back into your code to keep the game running.</p>
<h2><a href="#sample-code" name="sample-code">Sample Code</a></h2>
<p>For such a long introduction, the code for a game loop is actually pretty
straightforward. We’ll walk through a couple of variations and go over their
good and bad points.</p>
<p>The game loop drives AI, rendering, and other game systems, but those aren’t the
point of the pattern itself, so we’ll just call into fictitious methods here.
Actually implementing <code>render()</code>, <code>update()</code> and others is left as a
(challenging!) exercise for the reader.</p>
<h3><a href="#run,-run-as-fast-as-you-can" name="run,-run-as-fast-as-you-can">Run, run as fast as you can</a></h3>
<p>We’ve already seen the simplest possible game loop:</p>
<div class="codehilite"><pre><span></span><code><span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">processInput</span><span class="p">();</span>
<span class="n">update</span><span class="p">();</span>
<span class="n">render</span><span class="p">();</span>
<span class="p">}</span>
</code></pre></div>
<p>The problem with it is 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. If you have a part of the game
that’s content-heavy or does more AI or physics, the game will actually play
slower there.</p>
<h3><a href="#take-a-little-nap" name="take-a-little-nap">Take a little nap</a></h3>
<p>The first variation we’ll look at adds a simple fix. Say you want your game to
run at 60 FPS. That gives you about <span name="16">16</span> milliseconds per
frame. As long as you can reliably do all of your game processing and rendering
in less than that time, you can run at a steady frame rate. All you do is process
the frame and then <em>wait</em> until it’s time for the next one, like so:</p>
<p><img src="images/game-loop-simple.png" alt="A simple game loop flowchart. Process Input → Update Game → Render → Wait, then loop back to the beginning." /></p>
<p>The code looks a bit like this:</p>
<aside name="16">
<p><em>1000 ms / FPS = ms per frame</em>.</p>
</aside>
<div class="codehilite"><pre><span></span><code><span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">double</span> <span class="n">start</span> <span class="o">=</span> <span class="n">getCurrentTime</span><span class="p">();</span>
<span class="n">processInput</span><span class="p">();</span>
<span class="n">update</span><span class="p">();</span>
<span class="n">render</span><span class="p">();</span>
<span class="n">sleep</span><span class="p">(</span><span class="n">start</span> <span class="o">+</span> <span class="n">MS_PER_FRAME</span> <span class="o">-</span> <span class="n">getCurrentTime</span><span class="p">());</span>
<span class="p">}</span>
</code></pre></div>
<p>The <code>sleep()</code> here makes sure the game doesn’t run too <em>fast</em> if it processes a
frame quickly. It <em>doesn’t</em> help if your game runs too <em>slowly</em>. If it takes
longer than 16ms to update and render the frame, your sleep time goes
<em>negative</em>. If we had computers that could travel back in time, lots of things
would be easier, but we don’t.</p>
<p>Instead, the game slows down. You can work around this by doing less work each
frame — cut down on the graphics and razzle dazzle or dumb down the AI. But that
impacts the quality of gameplay for all users, even ones on fast machines.</p>
<h3><a href="#one-small-step,-one-giant-step" name="one-small-step,-one-giant-step">One small step, one giant step</a></h3>
<p>Let’s try something a bit more sophisticated. The problem we have basically
boils down to:</p>
<ol>
<li>
<p>Each update advances game time by a certain amount.</p>
</li>
<li>
<p>It takes a certain amount of <em>real</em> time to process that.</p>
</li>
</ol>
<p>If step two takes longer than step one, the game slows down. If it takes more
than 16 ms of processing to advance game time by 16ms, it can’t possibly keep
up. But if we can advance the game by <em>more</em> than 16ms of game time in a single
step, then we can update the game less frequently and still keep up.</p>
<p>The idea then is to choose a time step to advance based on how much <em>real</em> time
passed since the last frame. The longer the frame takes, the bigger steps the
game takes. It always keeps up with real time because it will take bigger and
bigger steps to get there. They call this a <em>variable</em> or <em>fluid</em> time step. It
looks like:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">double</span> <span class="n">lastTime</span> <span class="o">=</span> <span class="n">getCurrentTime</span><span class="p">();</span>
<span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">double</span> <span class="n">current</span> <span class="o">=</span> <span class="n">getCurrentTime</span><span class="p">();</span>
<span class="kt">double</span> <span class="n">elapsed</span> <span class="o">=</span> <span class="n">current</span> <span class="o">-</span> <span class="n">lastTime</span><span class="p">;</span>
<span class="n">processInput</span><span class="p">();</span>
<span class="n">update</span><span class="p">(</span><span class="n">elapsed</span><span class="p">);</span>
<span class="n">render</span><span class="p">();</span>
<span class="n">lastTime</span> <span class="o">=</span> <span class="n">current</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<p>Each frame, we determine how much <em>real</em> time passed since the last game update
(<code>elapsed</code>). When we update the game state, we pass that in. The engine is then
responsible for advancing the game world forward by that amount of time.</p>
<p>Say you’ve got a bullet shooting across the screen. With a fixed time step, in each
frame, you’ll move it according to its velocity. With a variable time step, you
<em>scale that velocity by the elapsed time</em>. As the time step gets bigger, the
bullet moves farther in each frame. That bullet will get across the screen in
the <em>same</em> amount of <em>real</em> time whether it’s twenty small fast steps or four
big slow ones. This looks like a winner:</p>
<ul>
<li>
<p>The game plays at a consistent rate on different hardware.</p>
</li>
<li>
<p>Players with faster machines are rewarded with smoother gameplay.</p>
</li>
</ul>
<p>But, alas, there’s a serious problem lurking ahead: we’ve made the game <span
name="deterministic">non-deterministic</span> and unstable. Here’s one example
of the trap we’ve set for ourselves:</p>
<aside name="deterministic">
<p>“Deterministic” means that every time you run the program, if you give it the
same inputs, you get the exact same outputs back. As you can imagine, it’s much
easier to track down bugs in deterministic programs — find the inputs that caused
the bug the first time, and you can cause it every time.</p>
<p>Computers are naturally deterministic; they follow programs mechanically.
Non-determinism appears when the messy real world creeps in. For example,
networking, the system clock, and thread scheduling all rely on bits of the
external world outside of the program’s control.</p>
</aside>
<p>Say we’ve got a two-player networked game and Fred has some beast of a gaming
machine while George is using his grandmother’s antique PC. That aforementioned
bullet is flying across both of their screens. On Fred’s machine, the game is
running super fast, so each time step is tiny. We cram, like, 50 frames in the
second it takes the bullet to cross the screen. Poor George’s machine can only fit in about
five frames.</p>
<p>This means that on Fred’s machine, the physics engine updates the bullet’s position
50 times, but George’s only does it five times. Most games use floating point
numbers, and those are subject to <em>rounding error</em>. Each time you add two
floating point numbers, the answer you get back can be a bit off. Fred’s machine
is doing ten times as many operations, so he’ll accumulate a bigger error than
George. The <em>same</em> bullet will end up in <em>different places</em> on their machines.</p>
<p>This is just one nasty problem a variable time step can cause, but there are more.
In order to run in real time, game physics engines are approximations of the
real laws of mechanics. To keep those approximations from <span
name="blowup">blowing up</span>, damping is applied. That damping is carefully
tuned to a certain time step. Vary that, and the physics gets unstable.</p>
<aside name="blowup">
<p>“Blowing up” is literal here. When a physics engine flakes out, objects can get
completely wrong velocities and launch themselves into the air.</p>
</aside>
<p>This instability is bad enough that this example is only here as a cautionary
tale and to lead us to something better…</p>
<h3><a href="#play-catch-up" name="play-catch-up">Play catch up</a></h3>
<p>One part of the engine that usually <em>isn’t</em> affected by a variable time step is
<span name="render">rendering</span>. 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.</p>
<aside name="render">
<p>This is more or less true. Things like motion blur can be affected by time step,
but if they’re a bit off, the player doesn’t usually notice.</p>
</aside>
<p>We can use this fact to our advantage. We’ll <em>update</em> 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 <em>render</em> in order to free up some
processor time.</p>
<p>It goes like this: A certain amount of real time has elapsed since the last turn
of the game loop. This is how much game time we need to simulate for the game’s
“now” to catch up with the player’s. We do that using a <em>series</em> of <em>fixed</em> time
steps. The code looks a bit like:</p>
<div class="codehilite"><pre><span></span><code><span class="kt">double</span> <span class="n">previous</span> <span class="o">=</span> <span class="n">getCurrentTime</span><span class="p">();</span>
<span class="kt">double</span> <span class="n">lag</span> <span class="o">=</span> <span class="mf">0.0</span><span class="p">;</span>
<span class="k">while</span> <span class="p">(</span><span class="nb">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="kt">double</span> <span class="n">current</span> <span class="o">=</span> <span class="n">getCurrentTime</span><span class="p">();</span>
<span class="kt">double</span> <span class="n">elapsed</span> <span class="o">=</span> <span class="n">current</span> <span class="o">-</span> <span class="n">previous</span><span class="p">;</span>
<span class="n">previous</span> <span class="o">=</span> <span class="n">current</span><span class="p">;</span>
<span class="n">lag</span> <span class="o">+=</span> <span class="n">elapsed</span><span class="p">;</span>
<span class="n">processInput</span><span class="p">();</span>
<span class="k">while</span> <span class="p">(</span><span class="n">lag</span> <span class="o">>=</span> <span class="n">MS_PER_UPDATE</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">update</span><span class="p">();</span>
<span class="n">lag</span> <span class="o">-=</span> <span class="n">MS_PER_UPDATE</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">render</span><span class="p">();</span>
<span class="p">}</span>
</code></pre></div>
<p>There’s a few pieces here. At the beginning of each frame, we update <code>lag</code> 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. You can visualize it sort of like this:</p>
<p><img src="images/game-loop-fixed.png" alt="A modified flowchart. Process Input → Update Game → Wait, then loop back to this step then → Render → Loop back to the beginning." /></p>
<p>Note that the time step here isn’t the <em>visible</em> frame rate anymore.
<code>MS_PER_UPDATE</code> is just the <em>granularity</em> 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.</p>
<p>But be careful not to make it <em>too</em> short. You need to make sure the time step
is greater than the time it takes to process an <code>update()</code>, even on the <span
name="bail">slowest</span> hardware. Otherwise, your game simply can’t catch up.</p>
<aside name="bail">
<p>I left it out here, but you can safeguard this by having the inner update loop
bail after a maximum number of iterations. The game will slow down then, but
that’s better than locking up completely.</p>
</aside>
<p>Fortunately, we’ve bought ourselves some breathing room here. The trick is that
we’ve <em>yanked rendering out of the update loop</em>. That frees up a bunch of CPU
time. The end result is the game <em>simulates</em> at a constant rate using safe fixed
time steps across a range of hardware. It’s just that the player’s <em>visible
window</em> into the game gets choppier on a slower machine.</p>
<h3><a href="#stuck-in-the-middle" name="stuck-in-the-middle">Stuck in the middle</a></h3>
<p>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.</p>
<p>Here’s a timeline:</p>
<p><img src="images/game-loop-timeline.png" alt="A timeline containing evenly spaced Updates and intermittent Renders." /></p>
<p>As you can see, we update at a nice tight, fixed interval. Meanwhile, we render
whenever we can. It’s less frequent than updating, and it isn’t steady either. Both
of those are OK. The lame part is that we don’t always render right at the point
of updating. Look at the third render time. It’s right between two updates:</p>
<p><img src="images/game-loop-timeline-close.png" alt="Close-up of the timeline showing Renders falling between Update steps." /></p>
<p>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.</p>
<p>Conveniently, we actually know <em>exactly</em> how far between update frames we are
when we render: it’s stored in <code>lag</code>. We bail out of the update loop when it’s
less than the update time step, not when it’s <em>zero</em>. That leftover amount?
That’s how far into the next frame we are.</p>
<p>When we go to render, we’ll pass that in:</p>
<p><span name="normal"></span></p>
<div class="codehilite"><pre><span></span><code><span class="n">render</span><span class="p">(</span><span class="n">lag</span> <span class="o">/</span> <span class="n">MS_PER_UPDATE</span><span class="p">);</span>
</code></pre></div>
<aside name="normal">
<p>We divide by <code>MS_PER_UPDATE</code> here to <em>normalize</em> the value. The value passed to
<code>render()</code> will vary from 0 (right at the previous frame) to just under 1.0
(right at the next frame), regardless of the update time step. This way, the
renderer doesn’t have to worry about the frame rate. It just deals in values
from 0 to 1.</p>
</aside>
<p>The renderer knows each game object <em>and its current velocity</em>. 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
<code>render()</code>. So it draws the bullet half a frame ahead, at 220 pixels. Ta-da,
smooth motion.</p>
<p>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 <em>think</em> 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.</p>
<p>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.</p>
<h2><a href="#design-decisions" name="design-decisions">Design Decisions</a></h2>
<p>Despite the length of this chapter, I’ve left out more than I’ve included. Once
you throw in things like synchronizing with the display’s refresh rate,
multithreading, and GPUs, a real game loop can get pretty hairy. At a high
level, though, here are a few questions you’ll likely answer:</p>
<h3><a href="#do-you-own-the-game-loop,-or-does-the-platform" name="do-you-own-the-game-loop,-or-does-the-platform">Do you own the game loop, or does the platform?</a></h3>
<p>This is less a choice you make and more one that’s made for you. If you’re
making a game that runs in a web browser, you pretty much <em>can’t</em> write your own
classic game loop. The browser’s event-based nature precludes it. Likewise, if
you’re using an existing game engine, you will probably rely on its game loop
instead of rolling your own.</p>
<ul>
<li>
<p><strong>Use the platform’s event loop:</strong></p>
<ul>
<li>
<p><em>It’s simple.</em> You don’t have to worry about writing and optimizing the
core loop of the game.</p>
</li>
<li>
<p><em>It plays nice with the platform.</em> You don’t have to worry about
explicitly giving the host time to process its own events, caching
events, or otherwise managing the impedance mismatch between the
platform’s input model and yours.</p>
</li>
<li>
<p><em>You lose control over timing.</em> The platform will call your code as it
sees fit. If that’s not as frequently or as smoothly as you’d like, too
bad. Worse, most application event loops weren’t designed with games in
mind and usually <em>are</em> slow and choppy.</p>
</li>
</ul>
</li>
<li>
<p><strong>Use a game engine’s loop:</strong></p>
<ul>
<li>
<p><em>You don’t have to write it.</em> Writing a game loop can get pretty tricky.
Since that core code gets executed every frame, minor bugs or
performance problems can have a large impact on your game. A tight game
loop is one reason to consider using an existing engine.</p>
</li>
<li>
<p><em>You don’t get to write it.</em> Of course, the flip side to that coin is
the loss of control if you <em>do</em> have needs that aren’t a perfect fit for
the engine.</p>
</li>
</ul>
</li>
<li>
<p><strong>Write it yourself:</strong></p>
<ul>
<li>
<p><em>Total control.</em> You can do whatever you want with it. You can design it
specifically for the needs of your game.</p>
</li>
<li>
<p><em>You have to interface with the platform.</em> Application frameworks and
operating systems usually expect to have a slice of time to process
events and do other work. If you own your app’s core loop,
it won’t get any. You’ll have to explicitly hand off control
periodically to make sure the framework doesn’t hang or get confused.</p>
</li>
</ul>
</li>
</ul>
<h3><a href="#how-do-you-manage-power-consumption" name="how-do-you-manage-power-consumption">How do you manage power consumption?</a></h3>
<p>This wasn’t an issue five years ago. Games ran on things plugged into walls or on
dedicated handheld devices. But with the advent of smartphones, laptops, and
mobile gaming, the odds are good that you do care about this now. A game that runs
beautifully but turns players’ phones into space heaters before running out of
juice thirty minutes later is not a game that makes people happy.</p>
<p>Now, you may need to think not only about making your game look great, but also use as
little CPU as possible. There will likely be an <em>upper</em> bound to performance
where you let the CPU sleep if you’ve done all the work you need to do in a
frame.</p>
<ul>
<li>
<p><strong>Run as fast as it can:</strong></p>
<p>This is what you’re likely to do for PC games (though even those are
increasingly being played on laptops). Your game loop will never explicitly
tell the OS to sleep. Instead, any spare cycles will be spent cranking up
the FPS or graphic fidelity.</p>
<p>This gives you the best possible gameplay experience but, it will use as much
power as it can. If the player is on a laptop, they’ll have a nice lap
warmer.</p>
</li>
<li>
<p><strong>Clamp the frame rate:</strong></p>
<p>Mobile games are often more focused on the quality of gameplay than they are
on maximizing the detail of the graphics. Many of these games will set an upper
limit on the frame rate (usually 30 or 60 FPS). If the game loop is done
processing before that slice of time is spent, it will just sleep for the
rest.</p>
<p>This gives the player a “good enough” experience and then goes easy on their
battery beyond that.</p>
</li>
</ul>
<h3><a href="#how-do-you-control-gameplay-speed" name="how-do-you-control-gameplay-speed">How do you control gameplay speed?</a></h3>
<p>A game loop has two key pieces: non-blocking user input and adapting to the
passage of time. Input is straightforward. The magic is in how you deal with
time. There are a <span name="platform">near-infinite</span> number of platforms
that games can run on, and any single game may run on quite a few. How it
accommodates that variation is key.</p>
<aside name="platform">
<p>Game-making seems to be part of human nature, because every time we’ve built a
machine that can do computing, one of the first things we’ve done is made games
on it. The PDP-1 was a 2 kHz machine with only 4,096 words of memory, yet Steve
Russell and friends managed to create Spacewar! on it.</p>
</aside>
<ul>
<li>
<p><strong>Fixed time step with no synchronization:</strong></p>
<p>This was our first sample code. You just run the game loop as fast as you
can.</p>
<ul>
<li>
<p><em>It’s simple</em>. This is its main (well, only) virtue.</p>
</li>
<li>
<p><em>Game speed is directly affected by hardware and game complexity.</em> And
its main vice is that if there’s any variation, it will directly affect
the game speed. It’s the fixie of game loops.</p>
</li>
</ul>
</li>
<li>
<p><strong>Fixed time step with synchronization:</strong></p>
<p>The next step up on the complexity ladder is running the game at a fixed
time step but adding a delay or synchronization point at the end of the
loop to keep the game from running too fast.</p>
<ul>
<li>
<p><em>Still quite simple.</em> It’s only one line of code more than the
probably-too-simple-to-actually-work example. In most game loops, you
will likely do synchronization <em>anyway</em>. You will probably <a href="double-buffer.html">double
buffer</a> your graphics and synchronize the buffer
flip to the refresh rate of the display.</p>
</li>
<li>
<p><em>It’s power-friendly.</em> This is a surprisingly important consideration
for mobile games. You don’t want to kill the user’s battery
unnecessarily. By simply sleeping for a few milliseconds instead of
trying to cram ever more processing into each tick, you save power.</p>
</li>
<li>
<p><em>The game doesn’t play too fast.</em> This fixes half of the speed concerns
of a fixed loop.</p>
</li>
<li>
<p><em>The game can play too slowly.</em> If it takes too long to update and render
a game frame, playback will slow down. Because this style doesn’t
separate updating from rendering, it’s likely to hit this sooner than
more advanced options. Instead of just dropping <em>rendering</em> frames to
catch up, gameplay will slow down.</p>
</li>
</ul>
</li>
<li>
<p><strong>Variable time step:</strong></p>
<p>I’ll put this in here as an option in the solution space with the caveat
that most game developers I know recommend against it. It’s good to remember
<em>why</em> it’s a bad idea, though.</p>
<ul>
<li>
<p><em>It adapts to playing both too slowly and too fast.</em> If the game can’t
keep up with real time, it will just take larger and larger time steps
until it does.</p>
</li>
<li>
<p><em>It makes gameplay non-deterministic and unstable.</em> And this is the real
problem, of course. Physics and networking in particular become much
harder with a variable time step.</p>
</li>
</ul>
</li>
<li>
<p><strong>Fixed update time step, variable rendering:</strong></p>
<p>The last option we covered in the sample code is the most complex, but also
the most adaptable. It updates with a fixed time step, but it can drop
<em>rendering</em> frames if it needs to to catch up to the player’s clock.</p>
<ul>
<li>
<p><em>It adapts to playing both too slowly and too fast.</em> As long as the game
can <em>update</em> in real time, the game won’t fall behind. If the player’s
machine is top-of-the-line, it will respond with a smoother gameplay
experience.</p>
</li>
<li>
<p><em>It’s more complex.</em> The main downside is there is a bit more going on
in the implementation. 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.</p>
</li>
</ul>
</li>
</ul>
<h2><a href="#see-also" name="see-also">See Also</a></h2>
<ul>
<li>
<p>The classic article on game loops is Glenn Fiedler’s “<a href="http://gafferongames.com/game-physics/fix-your-timestep/">Fix Your
Timestep</a>“. This
chapter wouldn’t be the same without it.</p>
</li>
<li>
<p>Witters’ article on <a href="http://www.koonsolo.com/news/dewitters-gameloop/">game
loops</a> is a close
runner-up.</p>
</li>
<li>
<p>The <a href="http://unity3d.com/">Unity</a> framework has a complex game loop detailed
in a wonderful illustration <a href="http://docs.unity3d.com/Manual/ExecutionOrder.html">here</a>.</p>
</li>
</ul>
<nav>
<span class="prev">← <a href="double-buffer.html">Previous Chapter</a></span>
<span class="next"><a href="update-method.html">Next Chapter</a> →</span>
<span class="toc">≡ <a href="/">The Book</a></span>
</nav>
</div>
</div>
<footer>© 2009-2021 Robert Nystrom</footer>
</body>
</html>