Hacker News new | more | comments | ask | show | jobs | submit login
Game Loop (gameprogrammingpatterns.com)
393 points by tosh 27 days ago | hide | past | web | favorite | 56 comments



While this book seems to get a lot of praise (as it deserves, obviously), I wish the style of teaching complex programming topics walked me through the pain of making something work, exploring a few alternative solutions, showing the tradeoffs, and then after the pain has been experienced by the learner, a proper solution is finally introduced and recommended. IMO it's a much more powerful technique for teaching if you walk the learner through the pains first, then arrive at a solution, and tell them that "you've just invented the game loop!"; i.e. the concept is given a name at the _very end_, not defined at the beginning as a solution to a pain the learner never experienced. Unfortunately very few books/tutorials take this approach.


This is a great book about Kalman & Bayesian filters. It provides alternative approaches and goes deep in explanation of algorithms.

https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...


Game Programming Patterns actually does that in places! Check out the State chapter for instance.[1]

[1] http://gameprogrammingpatterns.com/state.html


Reminds me of high school ceramics were we would have to grab two pieces of plexiglass and place our clay in between and use a pin roller to flatten our clay. If you wanted thinner sheets of clay you would continue the process with thinner pieces of plexiglass.

What we didn't know was that there was a slab roller sitting next to us all along that the teacher hadn't mentioned during the start of the course.

Through natural progression of working on "advanced" projects, we were then introduced to the slab roller as it cut time to focus on the new techniques we were learning.

The teacher essentially did that for the remainder of the course and the ones that stayed behind to learn a bit more were able to use the shortcuts before the others because they were progressing on their off time.


I also experienced that the most intuitive way of learning things, is to follow the natural evolution that led to it.

For example, you can teach people programming with higher level languages. But if your goal is to fully understand programming (as a professional programmer), you can start with the oldest discoveries and work your way into more recent years. That way you are able to grasp the full scope, know benefits and drawbacks, etc. You are also less likely to make the same mistakes of the past.


Author here.

This, I think, one of the fundamental challenges of teaching software architecture or other higher-level engineering topics. A lot of architecture boils down to:

1. Here's an obvious simple way to solve a problem, X.

2. If you do X at scale, much later, you will run into pain.

3. So here's Y, which seems weird and non-obvious but solves the same problem as X without the pain.

It's really hard to teach people step 2 when they haven't experienced it first-hand. You can walk them through scenarios, but most scenarios small enough to fit in a reasonable amount of prose feel fake and contrived.

Even when this does work, you can end up with a generation of programmers that cargo cult Y without any real understanding of the original problems it avoids from X. Look at, for example, how "goto" is now a boogeyman in programming well beyond the narrow concrete problems Dijkstra had with it.

For many of the chapters of the book, I try to walk readers through the problems of simpler approaches as well as I can, but it's a continuing challenge. There really is no substitute for experience.


Thanks Bob, I appreciate your response. To be honest, I haven't read the entire book. However, I looked at the table of contents, and it appeared to be a run-down of well known game design patterns. For someone who wants to get educated on those patterns, that's probably fine. For someone new to the topic of game programming, they're probably going to benefit from the style I described, e.g. hand-holding them in creating a game from scratch, progressively going from simple to complex after understanding the pains along the way, introducing new concepts as needed and just-in-time. So this may have been just an issue of understanding who's the audience of the book.

That being said, the point about doing X at scale wasn't my issue. Take for example programming language books and/or documentation. The typical approach in almost every book/guide is teaching you about syntax, data types, control structures, etc. While this is valuable information, it's not usually what a person new to the language is looking for. What they're looking for is (most probably) what is unique about this language in solving specific domains of problems. New to Erlang? You probably should be introduced to a problem that deals with concurrency and reliability, and get walked through an example of how Erlang can solve it elegantly. New to Python? You should probably be introduced to a problem that deals with manipulating data, and get walked through an example of how Python can help you wrangle data easily. Etc.

> For many of the chapters of the book, I try to walk readers through the problems of simpler approaches as well as I can, but it's a continuing challenge.

Please continue to do so. I'm sure the praise you get for your book is well deserved, and part of the reason is your approach to teaching the patterns.

> There really is no substitute for experience.

Agreed. And part of the teaching style I'm advocating for is making the learner "earn" the skill by showing them the way, not the destination.


This is a great point. Kind of off-topic now; do you know of any books that take such an approach? The subject doesn’t matter, as I’m more concerned with the pedagogy in this case.

The one that springs to mind for me is Functional Programming in Scala.


Joe Armstrong does this in Programming Erlang: Software for a Concurrent World. Its extremely effective, and pulled me through each chapter by forcing me to continually look at how the solution could be improved.


For a great example of this, I'd recommend reading The Inner Game of Tennis by Tim Gallwey (or watching the lecture if you can get your hands on it).

It's essentially taking a coaching mentality towards your writing, letting the reader take the steps themselves to feel confident in it, and then only afterwards telling them what they are actually doing (e.g. in that context, properly serving).

It's a fantastic process and the book, of course, explains how it works in the context of teaching tennis.


I have a funny story about the deWiTTERS game loop that I wrote a long time ago (referred to in the article above)

Back then I was doing mobile game development for PocketPC.

After I left that company, some ex-colleague had to do some changes in my code, or port it, I can't remember. So he was looking at that game loop that I implemented, and was thinking "What the hell is he doing here???". So he did a google search to see if he could find something, and immediately stumbled upon an article, written by that same programmer :D.

He told me years later when I saw him, and said "What are the chances that you search something on google because of code you're going through, and find the article that explains it written by the same programmer".

I was still a junior back then, so probably I should have commented my code a bit better (instead of not at all ;)).

I still want to write a revised deWiTTERS game loop article, because the steps in a physics engine could make the extrapolation redundant.


When I google "game loop", I found deWiTTERS Game Loop, http://www.koonsolo.com/news/dewitters-gameloop/ which I still not fully understand.


What is the part that is not clear?


The sconed part "Game Speed dependent on Variable FPS". I'm confused about the parameter of function "update_game()". From the code, I think the time length of "curr_frame_tick - prev_frame_tick" would increase at each timestep beacause of function "display_game()".


Every loop, prev_frame_tick is assigned the old value of curr_frame_tick before curr_frame_tick is updated. That means the value of their difference is the time in ticks it took for the last loop to execute. That difference is used to scale things like physics.

As an example, if we want to move something on screen at a constant rate in pixels per second, the number of pixels to move per update (ie frame) at 60 FPS is half as far as when updating at 30 FPS. The result is that the position at any time is the same regardless of how quickly the computer ran the simulation.


display_game() doesn't change any of these values.

(curr_frame_tick - prev_frame_tick) is the delta time of each loop. So this value is the time it took to do the previous loop.

It doesn't increase each timestep because prev_game_tick is recalculated each step.

Step1 (initial step):

- prev_frame_tick = 0

- curr_frame_tick = 0

- delta = 0

Step2:

- prev_frame_tick = 0

- curr_frame_tick = 200

- delta = 200

Step3:

- prev_frame_tick = 200

- curr_frame_tick = 356

- delta = 156

...


Fair enough. I think I didn't understand the difference between game time and real time before. I though the running time of "display_game()" was the game time (curr_frame_tick - prev_frame_tick). Thanks a lot for your detailed explanation.


Thank you for this article, it really helped me out several times :)


One example of a problem with variable frame rate physics simulation was Quake 3, which allowed you to make otherwise impossible jumps if your frame rate was 125fps. This value exploited the rounding errors in the jump height calculation to get extra jump height. Some custom maps even assumed you'd be running at 125fps and would be unplayable if your hardware couldn't keep up.

Demonstration and explanation here: https://www.youtube.com/watch?v=P13KmJBNn1c

OpenArena added an option for fixed framerate physics, and an option to disable the rounding.


One effect of linking game and real time was seen in Dark Souls on PC (at least it seems like that's what happened): the game was capped at 30fps. Once people hacked out the frame limiter their character's gear degraded at a higher rate.


In DS2 they released the PC version at 60fps, and consoles at 30. The equipment degradation was based on the number of frames a weapon's hitbox spent overlapping another model (walls, enemies, etc). They patched this pretty quick.


After playing around with making a simple, somewhat function programming-style engine [1], I came to the conclusion (from other people's work) that the game loop is really just iterating on a pure function call that gives you the next world state given the previous world state:

  next_world_state = UpdateWorld(inputs, previous_world_state)
Where inputs is all external inputs (user inputs and "time"). How the inputs is updated (and how frequently) is totally decoupled from how the game engine operates. Additionally, from the next_world_state, you can derive what to render to the screen, what audio to play, what text to render, etc. If you want to drop frames, just don't render each world state.

[1] https://github.com/allenu/YokosukaJS


Just read something similar with Urbit: https://urbit.org/docs/introduction/technical-overview/

Taking that concept to an operating system essentially.

> Your urbit is a deterministic computer in the sense that its state is a pure function of its event history. Every event in this history is a transaction; your urbit's state is effectively an ACID database.

> Because each urbit is deterministic we can describe its role appropriately in purely functional terms: it maps an input event and the old urbit state to a list of output actions and the subsequent state. This is the Urbit transition function.


this appears to use the sleep method for the game loop described in the OP article, as opposed to a fixed update interval and interpolated render step.


Space Invaders exploited the render-dependent timing of it's game loop to increase the speed of movement as the kill count increased.

https://en.wikipedia.org/wiki/Space_Invaders#cite_ref-RG-3_1...


Yeah: from careful observation Space Invaders seems to move one alien every frame, hence the fewer aliens the faster it gets. I started playing around building my own version, but it's never got beyond the prototype phase: https://arcade.ly/games/space-invaders. I'd love to be able to use lack of time as an excuse but it's really lack of motivation.


> he thought of using a space theme [...] and created initial bitmap images after the octopus-like aliens. Other alien designs were modeled after squids and crabs.

I find it funny how the thought goes to deep space, yet reaches so close to Earth.


Game loop based systems have trouble using more than one CPU effectively. This is a big problem, since we can now get more CPUs, but not faster ones. The audio guys are happy - they can finally get their own CPU, or a big piece of one, and get out of the game loop. (Audio guys liked the Cell. Nobody else did.) The AI guys are usually running on a much slower schedule than the frame rate, so they're OK with this. The rendering guys think they own the game loop. The physics guys are struggling; they always need more CPU time. The asset loading guys are I/O bound anyway. Back in the main loop, the name of the game is not getting stalled on locks on shared data.

(Somewhere in the Second Life viewers, there's a lock conflict which causes disk delays in loading assets from the local cache to stall input processing in the main loop. All the disk I/O is in other threads, and those threads can talk directly to the vertex buffer memory in the graphics card, so this shouldn't be happening. But it is.)


"Multithreading the Entire Destiny Engine" is a 2015 GDC talk by Bungie's Barry Genova explaining how Bungie turned almost every part of Destiny's engine into a job graph that can be processed in parallel.

https://youtu.be/v2Q_zHG3vqg


The book is overall excellent. I learned way more from it (and had way more fun) than I did ever reading something like the Gang of four or its various explanations.

Best book to learn programming patterns in general if you ask me


I love this book as well. I think part of what makes it so good is that the patterns are discussed in a very domain-specific context and their usage is not overly abstracted. I often find it hard to see why a particular "widget" or "foo/bar" pattern or structure is used/useful, but when you put the examples in a very specific context like this, it's much easier to understand their value and remember why/when/how to use them.

I wish there were other Pattern and Software-Engineering books that discussed things in more domain-specific contexts, but I suspect game development is one of the few domains large enough, and with enough people looking for domain specific literature, to really warrant such a book.


I similarly have difficulty learning a concept when it's presented using real-world metaphors that aren't often actually expressed via code. This is how object oriented programming was taught to me: imagine a door object, which contains methods open and close, and it contains a knob property, which is its own object with functions to turn left and right, and so forth. Once you're familiar with OOP this might seem like a good way to explain the concept, but without a specific application to apply it to, it's difficult to see the purpose.


OOP examples such as these and their instruction in traditional schooling is arguably one of the biggest failures of computer science education of our time. This is literally the last thing object oriented patterns are ever used for (depicting real world objects as members of categories). They are primarily designed for describing systems that are managing the user's interactions in the software rather than representations of real-world physical objects.

The only time these overlap is in video games, which is usually not used as the context for teaching software development when OOP is taught.


The secret subtext of my book is that almost all of the patterns are perfectly useful outside of games too. Very few patterns here are specific to games (though "Game Loop" is one of them).

Maybe it's just me, but if I'm going to read a few thousand words about some piece of software architecture, I'd rather be reading about trolls and magic than employee record databases.


Thank you very much for all your work on "Game Programming Patterns." It's an amazing resource. I was not aware of "Crafting Interpreters" before now. I can't wait to start digging into it.

I've come across very few Design Patterns, and Software Engineering topics in general, that couldn't be taught/explained from the perspective of game development. I'm surprised that it isn't used as a teaching-tool more often then it is. It's an inherently complex domain that most audiences are already quite familiar with; the "why" behind things is either immediately obvious or easily explained. If someone doesn't know what the requirements are for something like an employee record databases, and how such a system might be used, using that as a context for teaching is not much more useful then "class Widget" and "Foo.Bar()".


I couldn't agree more, although I'd take a step further and extend it to way more stuff: options, features, libraries, and even applications. Building up an index of knowledge generally help in deciding what tool or technique to reach for.

I'll often look at stuff and wonder: what is your purpose? In my experience, explanations without context aren't generally very useful. It's much easier to incorporate knowledge when you're first presented with a concrete example of a problem along with its solution, and then you're presented with the abstraction.

One of the most notorious examples I can think of is when someone tries to explain monads. For some reason people often start by providing a long mathematical definition, which is completely useless if you don't even understand the weird words being used. It's worth learning Haskell just for all the new concepts and ideas it'll expose you to, even though the syntax looks very unfamiliar at first.


Awesome comment from the FAQ:

Which version pays you the most?

First of all, thank you for caring about this! Since I self-published, I set the prices so that the royalties are about the same for each format. (I also get the lion’s share of the money since there’s no publisher taking a cut.)

Buy the format you want and I’ll get paid pretty much the same either way. If you want to give me money, but don’t actually want a physical book, consider giving it to a friend or your local library. I get money, you feel good, and someone gets a free book!


Just a friendly reminder to aspiring gamedevs. Global Game Jam 2019 is happening this very weekend. Theme is: What Home Means To You. And there are plenty of teams currently streaming on Twitch. As well as a Discord chat ;)

https://globalgamejam.org/


Extrapolating up to one physics frame is still not a good solution, it will be noticeable.

For example a falling object will clip in the ground for tens of ms of displacement which is definitely visually significant.

A better solution is to either only interpolate and live with the additional frames of input latency (fine for a lot of games) or resimulate the next physics frame with the new player input, and live with the additional CPU overhead.


Glenn Fiedler gives the best solution to this:

https://gafferongames.com/post/fix_your_timestep/

I’ve had a great experience so far following Glenn’s suggested solution.


Yes! This article was one of my main inspirations for the chapter.


Speaking of inspirations, looking at the sample PDF on your site, I'm getting some pretty intense Edward Tufte style vibe. Was that intentional?


Oh, yes. <3 Tufte.


well this is your basic game loop, and serves as an introduction to the topic. there are lot of things that were just skimped, for example you'd still need an event loop to capture input and store them for the process input method, or you risk losing fast key presses.


I've looked into game loop pattern discussions in the past, and (as a hobbyist doing nothing serious in gamedev, just having fun with the occasional small game) I typically find them to be overly-academic and didn't really communicate why I'd want to use a pattern, simply that I "should". I've also spoken with other developers (who, to be fair, were systems and application developers first, not game developers) over-invest themselves in the theory and architectural aspects of game development, rather than ... well, actually making a fun game.

This article presents the most cogent and approachable explanation of the topic I've seen. It's empathetic style reminds me of the excellent "Head First" design patterns book (which if your ego can get past the initially-jarring style, is IMO the best way to fully grok the patterns). Thanks to the author, to to the person who shared it!


Isn't it far better to split these jobs out to different threads?

A rendered frame is just a view on some data. As soon as you couple state updating to rendering you're bound to encounter issues. This is what leads to games like ARMA who's FPS in multiplayer depends heavily on the performance server, which is insane.


> Isn't it far better to split these jobs out to different threads?

Not necessarily. For games one of the things you're trying to minimize is time from user input to response on screen - that has to go through your input system, your animation system, possibly your physics system, and then all the way through the renderer. You need strict control of ordering and buffering. To allow stuff to be offloaded to another thread adds latency and can make things messy to control.

For simpler games, threads here don't help. They just hurt. Extra complexity, and likely extra latency (if only through mistakes and synchronization).

For more complex games, you can often get away with just going "wide" within the game loop. You have threads, but it's not about splitting off "animation" and "physics" jobs, but instead going wide when updating animation or updating physics. It's more granular and the high level coordination still happens in a traditional game loop.

If you want to get really fancy, your game loop starts updating a graph of systems of system jobs instead of a hardcoded list of system updates. If you strictly specify all inputs, modifications, outputs, etc. you can start making it automatically parallel by walking the graph and dispatching jobs that don't conflict with running jobs.

Even then you still have a game loop, you've just offloaded most of it's work to a fancy job system. Not all - you'll probably still have some API calls that only work on the main thread hardcoded into the game loop (e.g. for pumping OS UI messages using system provided APIs that aren't thread safe).


Yes if you can, but interleaving writing state (game update) and reading state (redraw) can get messy. As long as you figure that out you're usually good to go. So for games that are fast enough already, there's no need for introducing potentially subtle threading bugs.


Very accessibly-written and entertaining


We had the exact same problems with building VRS systems in the 90's. A system would runder under DOS written with turbo Pascal. A system would hold 8 cards with 2 lines. The progam had to run in a loop to keep feeding the voice buffers and handle the events from the cards.


Back in the days of CRT monitors, you'd wait for a display refresh loop interrupt to fire, and as you knew that the screen refreshed at a particular number of cycles per second, you knew how fast your game would run.


Back in the days of CRT monitors and DOS, graphic hardware didnt generate vsync interrupts.


Yes it did. I used to use them to keep my games at the right speed.


I should of narrowed my statement to VGA under DOS. You had to either manually poll 3dAh, or best case scenario politely ask VESA (SetDisplayStart) to page flip during vsync for you, but even that wasnt always working (for example Quake had a manual switch and treated it as something experimental). Interrupt was a remnant from CGA/EGA standard support, crapshoot on VGA cards.

https://www.vogons.org/viewtopic.php?f=63&t=58445

https://books.google.pl/books?id=gZ5SDTpMR-MC&pg=PA386&lpg=P...


Implementing a game loop in JavaScript (2011) [0]

[0] https://codeincomplete.com/posts/javascript-pong/


doesn't use render interpolation as the OP article describes




Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: