Game Programming Patterns | Hacker News Reader

Game Programming Patterns

gameprogrammingpatterns.com

265 pointsGuiA64 comments

Most lists of design patterns (including but not limited to the GoF and this site) are written with the noblest of intentions, and contain a lot of insights and interesting solutions. Patterns can provide specific solutions to specific problems, and also a common vocabulary for developers to talk about these problems and solutions.

Unfortunately, for the past 18 years I have seen repeatedly (in the game industry and outside) that they tend to be used as shopping lists by developers who can't (or don't have time to) think, design and architect properly. The result of such approach to development, let's call it Pattern Oriented Design, are bloated, overengineered and underperforming systems that are still harder to write, document, test and evolve, than the disorganized messes they replaced.

So, nice work, but beware programmers: you must first understand the problem you are trying to solve, before you go shopping for a solution.

The old adage says "When you hold a hammer, everything looks like a nail."

I'd say: learn the patterns, and then forget about them. And when you'll work on an actual problem, the one pattern that is relevant to your problem will come naturally as a solution.

My tentative feel so far on patterns in games is that they're more useful for understanding a design than for constructing one, since as you note pattern-oriented design tends to end up pretty messy. But if you have a design, it can provide a useful vocabulary for talking about what's in it, or how it differs from an alternate design.

I'm currently working on a paper trying to analyze the X-Com remake through design patterns, and it seems to be working reasonably well so far. The pattern language gives some hooks for talking about what specifically was kept or changed in the remake. However, for that project we're using more design-oriented rather than programming-oriented patterns, from this project: http://gdp2.tii.se/

(There used to be a book, but it's out of print: http://www.amazon.com/gp/product/1584503548/ref=as_li_ss_tl?...)

This is one of my concerns too. I've seen patterns be overused almost as much as underused. It's a shame too, because the original Design Patterns book actually goes out of its way to tell you not to use patterns unless they are really a good fit. Unfortunately, remarkably few people have actually read the original book.

If you look at the chapter outline, I'm planning to have an introductory section on "How to Use Patterns (and How Not to Abuse Them)" where I'll try to mitigate this. Also, each chapter has a "Keep in Mind" section that focuses on telling you when a pattern might not be a good fit.

It's what the book /says/, but in practice it's not what the book /encourages/: a bit like alcohol or sports car TV ads, which all say "drink/drive responsibly". Your own introduction suggests patterns as a cure for bad design and architecture:

"I started trying to find books about how to organize programs. Fast-forward several years and a friend hands me a new book: Design Patterns: Elements of Reusable Object-Oriented Software. Finally! The book I’d been looking for since I was a teenager."

"But the architecture that this brilliant code hung from was often an afterthought. [...] if they ever cracked open Design Patterns at all, never got past Singleton."

I'm sure most cases of badly architected code you have ran into were caused by insufficient time and/or attention devoted to design and architecture. Now the question is, do you think if these coders had the same time/attention but knew patterns, the result would be better? How would it compare to these same coders without patterns but with more time/attention?

In that sense, metaphor alert a book of design patterns is to programming what a dictionary is to writing: useful, but mostly orthogonal to the quality of the output.

> I'm sure most cases of badly architected code you have ran into were caused by insufficient time and/or attention devoted to design and architecture. Now the question is, do you think if these coders had the same time/attention but knew patterns, the result would be better?

Yes, I do. I've seen a number of times where a smart developer burned hours half-way reinventing from scratch some crude architectural pattern that they could have spent five minutes looking up in a book. Worse, if they had looked it up, they may have learned some of the documented pitfalls that come with it instead of stumbling right into them.

I agree there are few things worse than a codebase jam-packed with inappropriate design patterns. Unfortunately, one of the few things that is worse is a code base where the programmers have clearly never learned about any design patterns at all.

Yes, I would rather that instead of lists of patterns, people would focus on design principles, and just use the patterns as examples of theose principles in practice.

I agree with you completely. I've encountered a lot of architects and recruiters who seem to put a lot of focus on knowing design patterns, to a point where they seem to forget that you don't always need to employ a well known design pattern.

A lot of people seem to think, for instance, that the GoF design patterns are the only design patterns. They just memorize the list, but fail to understand when and why (not) to use them. To me, any frequently employed construction is a design pattern, including but not limited to the classical examples.

> To me, any frequently employed construction is a design pattern, including but not limited to the classical examples.

The GoF emphatically agrees with you. They considered their book a starting point, not the final word.

I've have to make a confession: Almost every time I use a pattern it makes my code more complex and harder to understand. I've used visitor, composite, singleton, all sorts of factories, decorator, proxy, state, strategy, etc.

You have a problem, then you realize, "I think this is what the x pattern is for. How does that pattern work, again?" You then google it and try to implement it correctly. Almost by definition, you're not implementing the most obvious solution. If you were, you probably wouldn't have to google it. It'd be better to implement the simplest solution that could possibly work.

I think design patterns may be good as a communication tool, and no more. It's faster to say, "factory" than to describe the pattern's implementation. But code maintainability is way higher priority than using a pattern and in my experience pattern implementation and code maintainability are mutually exclusive.

Design patterns are a thing that are useful only when you've essentially rediscovered them for yourself in natural solutions.

I developed games as a kid for many years, and I developed solutions to some problems that I identified later as patterns while reading the GoF book.

However, if I had read the GoF book in the first place and tried to forcefully implement patterns just based on reading about them in a book, I'd have done a miserable job.

I actually had to tweet this:

  Almost by definition, you're not implementing the most 
  obvious solution. If you were, you probably wouldn't have 
  to google it

Thank you

A pattern: deterministic game state, updated only by player input.

It's used for multiplayer synchronization. Instead of sending thousands of objects, it's enough to send mouse clicks and keystrokes.

"1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond" http://www.gamasutra.com/view/feature/3094/1500_archers_on_a...

It's also used for game replays.

Also one of the hardest patterns to do right (explained somewhere else)... one small glitch in the world state and the state goes out of sync.

Yes, these are very subtle. For example, floating point computation has different precision depending on the machine. This might lead to small differences in the game state, which grow over time (chaos theory yay). It is really hard to hunt such bugs. The fix might look like this:

  - double result = x * y * z;
  + double tmp = x * y;
  + double result = tmp * z;

The intermediate value x*y is rounded to double precision afterwards, whereas it had machine precision before.

(disclaimer: second hand war story from OpenTTD, might not be entirely accurate)

Indeed, if determinism is very important, fixed-point arithmetics should be preferred over floating point arithmetics - at least in the game engine, for the rendering floating point should be fine.

Note that fixed-point arithmetics is almost identical to integer arithmetics, thus easy to implement. If you define your physical units small enough (e.g. velocity as pixels/ms instead of pixels/s), then you can use integer arithmetics right away without any confusion.

One minor drawback is that you don't have easy access to cos(), sin(), sqrt(), etc. without going through floating point. However, you usually don't need those in the game engine anyway. For instance, instead of "sqrt(xx + yy) < r", just write "xx + yy < r*r".

The major drawback is that you now might have to deal with integer overflows (and underflows). You should deal with them in floating point, too, but these are more unlikely there. One might think that this won't destroy determinism if you are using e.g. always 32 bit integers on all platforms, but note that some kinds of (signed) underflows or overflows are technically undefined, at least in the C standard, so some compilers might do optimizations that lead to different underflow/overflow results than expected.

Floating point arithmetic is deterministic if you are careful enough:

> "I work at Gas Powered Games and i can tell you first hand that floating point math is deterministic. You just need the same instruction set and compiler and of course the user’s processor adheres to the IEEE754 standard, which includes all of our PC and 360 customers. The engine that runs DemiGod, Supreme Commander 1 and 2 rely upon the IEEE754 standard."

See http://gafferongames.com/networking-for-game-programmers/flo...

This is an interesting article (well, in large part collection of quotes/resources) on the interaction of deterministic synchronization and floating-point: http://gafferongames.com/networking-for-game-programmers/flo...

There seem to be conflicting opinions from game developers about whether you can coax determinism out of IEEE 754 floating point, if you're careful about it. From what I've read, the IEEE 754-2008 revision is supposed to take the goal of reproducible results more seriously as well, but I'm not sure how widely implemented or reliable its efforts in that department are.

x87's 80-bit floats should be avoided for deterministic game state, not to mention how much faster SSE generally is.

I had a problem in flash where iterating over a dictionary, order being different on different platforms, so updating all the game objects would happen in different orders.

But it always worked on my computer!

I once used determinism as an AI tool: ran a copy of the physics simulation to 'look into the future' and predict the movement of what visually looks like a chaotic system. This prediction could then be fed to some AI agents and give the appearance of 'intuition'.

That sounds brilliant. If you want to write more about how that worked, I would like to read it.

This was for a basketball game that will remain unnamed; I was not around when the game was released, and it's been many years since then, so I don't know if this stayed or not.

I wrote a 99% deterministic physics system for the ball trajectory during shots and passes, which gave the ball an incredibly natural behaviour. When a shot was taken, the system simulated up until the ball went below the rim's height, so it knew if the shot would hit or miss, and where was the best position to go for the rebound.

Once in a while the prediction would fail. Determinism is freaking hard, but luckily the game didn't rely on it for networking or anything else.

While debugging I also made the experiment of feeding this into the announcers and color commentary. The result was funny and disturbing in equal parts, definitely not a good idea.

I love big long articles on the main loop. It's one of those wonderful problems that seems like it ought to be easy but turns out to have lots of subtle (and important) complications.

The early GPU Gems books might be of interest to you. They are full of stuff like frame timing subtleties and interesting ways to solve common game loop problems. These days, you can probably get them for less than $50 each, too.

GPU Gems is available online for free, courtesy of Nvidia: http://developer.nvidia.com/object/gpu_gems_home.html

Agreed, the closest I have come to writing a game, was to write a server-side simulation engine that interfaced with a rather limited console web-app for communicating with the simuation (think fire chief on a radio communicating with units and dispatch).

One of the biggest flaws when I was brought in, is that each avatar (unit/man/truck/etc) was setup with it's own thread that handled its' own move event timer. The issue was that a few dozen avatars in a simulation combined with dozens of simulations on a server would lead to thousands of threads each causing memory swaps, with the need for locking to avoid race conditions and other contention issues.

It wasn't a real-time interface, so a second plus or minus to responses wasn't a huge deal. I refactored the avatars to work of a central loop. The only place with common interaction was a message queue for inbound/outbound messages to the various clients to the engine instances.

This cut down on a lot of the cpu contention and similar issues. This would have been less of an issue for something simple on a single computer, but running many such simulations on a single computer, you come into different problems.

It was actually fun to work around this.

Very well written. I was a bit skeptic, so I went directly into Singleton pattern that many get wrong... All I can say that this is some of the best and cleanest explanation why Singleton is an anti-pattern, and also what do use instead.

Thanks! When I was at EA, I swear every source file had like five singletons in it. It was terrible. I was highly motivated to write that chapter at the time.

But lets talk about Singletons just for a sec. I am currently writing a game and I do have 2 singletons. My director class (that controls initialization and instantiation of all the things I need) and my main game scene (when the user presses Play from the menu). To me this made perfect sense.

But I can see how singletons get out of hand, but could also make sense to the developer to do so. (Meaning the developer thinks it makes sense to over use when it might not)

How do you approach the fact that maybe your game scene, layers on that scene, HUDS, all would just have a single instance ever?

I have read that singletons are used a lot in games and well games are playable (meaning they run and work) so do you ever apply "if it ain't broke" philosophy?

Your site will be very useful to a lot of people. Singleton alone.

Sure, I'm not saying never ever ever use Singletons, just try to limit them. Most games and apps I've seen, even well-written ones, still have a little static state floating around. The idea is just to constrain it, know what problems it causes, and be deliberate about it.

A must have architectural pattern for such a list: "Entity Component System" http://en.wikipedia.org/wiki/Entity_component_system

Must has: http://gameprogrammingpatterns.com/component.html

Not to take away from the value of component systems, but I find them remarkably tedious to code with.

In Unity 3D they work well because the component attachments are driven by the visual interface. Your coding happens inside components, and is then linked up in the scene visually.

The second game engine I implemented used an entity component system, and I found myself not wanting to use it. Attaching and building components in code just to do trivial things was tiresome.

I think such a system is valuable for a game that's already designed, prototyped and ready to be implemented cleanly, but it's not a great pattern for prototyping/rapid game development.

It's almost like you need one set of patterns for game prototyping (messy, hacky, and immediate operations), and an orthogonal set of patterns for final game implementation.

Well, my personal pov is that for certain prototyping requirements component systems are actually a good fit because they make it easy to rewire thinks quickly and to easily plugin/replace strategies (as in strategy object). In this regard it is ver yrelated to the DCI pattern (http://en.wikipedia.org/wiki/Data,_context_and_interaction). Also, components/systems fall much easier into place when using a functional programming approach.

Conceptually, I think it is harder and kind of a pain to code for at first. But one of the advantages I've found using it is the ability to completely decouple the state of game objects from the code that manipulates them. This gives you the following (rarely mentioned) benefits:

1. Saving game state is trivial (as is replaying it, like in a rewind or time-travel)

2. For garbage-collected environments, it's easy to completely avoid GC pauses by re-using old game state objects.

3. Adding existing functionality to any object is trivial.

#2 was the biggest win for me. I made some small bullet-hell style shoot-em-ups in C# that would pause for GC until I reworked the game into a component system where all game objects were stored in a table, and each row in the table contained all columns for all possible objects properties.

So when a bullet went offscreen, the row its state was stored in became available for the next game object (bullet, alien, etc.) The only step necessary was to wire that row to the various components that would control the game object. The GC pauses disappeared, and this made changing the game and prototyping extremely easy. I'd imagine this would simplify memory management in C++ in the same manner.

I also really enjoyed have things like "AffectedByGravity" as a component and the ability add objects arbitrarily into it, instead of some hackish inheritance chain.

I mostly agree with you, I just found that trivial things — like drawing sprites — became cumbersome.

In my case it involved adding the transform component, the sprite render component, any movement components (usually custom subclasses for the specific game) and then adding that node into the graph.

When I wanted to hack away quickly on ideas I found I avoided my own engine because of all the typing it took just to get something up on the screen and moving. Or I found myself creating simple wrappers on top of the component system that killed the flexibility for the sake of brevity and readability.

In my personal experience coding with components did something to stop the creative, messy part of my brain that just wanted to see things on the screen and moving as soon as possible.

Yeah, I see that. The reason I think what I did became so easy is that I took the component model to the absolute extreme. There were no objects at all, just a table of state data and a collection of functions you could add to an "entity."

I think most implementations mix and match some sort of OO and that would get messy quick. What I did worked great for the particular bullet-hell style shmup I was making. I don't know how well it would work with other types of games, particularly those with game entities that had a ton of state that wasn't shared.

With the bullet-hell game, an enemy shared a lot of state with the main character and bullets. An RPG might be a different story.

I've oscillated back and forth between the different entity paradigms numerous times. In my most recent try I moved towards a design that is essentially an inversion of typical component strategy to put less emphasis on components as unique structures, since in so many cases, they're a repackaging of an existing data type.

To do this, I have some generic container types that are extensions of common ones(list, bag, etc.) to be aware of entities and clean up after them. Instances of the generics are subsequently parametrized with the data I need. The top level entities hold the minimum of information needed to do despawning.

It's had some success in use, but I'm not ready to say it's a major improvement.

I was reading a couple of good articles about this yesterday:

http://piemaster.net/2011/07/entity-component-primer/

http://piemaster.net/2011/07/entity-component-artemis/

It looks interesting and well written. However I would prefer to read it when it is complete or at least more complete.

I wouldn't hold your breath. When I last used this site in 2010 [1] it wasn't that much less complete.

Still, what is has is very useful and I'd suggest giving it a read.

[1] http://web.archive.org/web/20100131082252/http://gameprogram...

It was on hiatus for a couple of years: I left the game industry, moved across the country, and had a couple of kids. But I'm back to working on it now and I hope I can get it finished.

Hi! Wow, very nice to meet the author. Most of this was written after I'd already finished my game, but the Object Pool article was part of the inspiration for my memory pool class [1]. Thanks for everything you've written, it has helped more people than you probably know.

[1] https://github.com/karlgluck/Evidyon/blob/master/Source/comm...

That's great to hear! I'm glad you got some use out of it. Feedback like this is the only thing that gives the book a chance of being finished. I'm generally terrible at staying focused on one thing but hearing stuff like this really helps.

I only just found it, read the "Game Loop" chapter and it's great stuff! I like how you clearly enumerate the pros and cons of several approaches. And even if an approach was already familiar to me, that made it very useful providing new ways of thinking and comparing about it.

So please do keep it up :)

"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."

I've borrowed many of the game loop and other game programming principles when developing code for controlling external equipment like robots and radio transceivers. It's a better model than some of the crazy state machine code I'd written in the past.

I just read the component chapter and its the clearest article on components I've read so far, I wish I had read this 2yrs ago!

BTW in my game I do some component communication by having a GetComponent method on GameObject that takes a component identifier and returns the component. This is a compromise between messaging and direct reference and I think many engines offer this :)

Thanks!

Hi, It's great to hear that you are back on it! I stumbled on this page a couple of years ago and was saddened to see it wasn't getting updated. Thank you for this great piece of writing.

If you ever do finish it, go and wrap it in a book via some online self publishing platforms. I'll be the first one to buy a copy.

Or, if you're not interested in making some money out of it, maybe turn it into wiki style website, so that other people could chip in and you would moderate the submitted text.

> go and wrap it in a book via some online self publishing platforms.

That's what I'm thinking right now. I actually really really look forward to doing layout on a book. I used to be a designer before I was a programmer.

> maybe turn it into wiki style website, so that other people could chip in and you would moderate the submitted text.

Sometime soon, I'll probably try to get the source repo public and up on github. Then I can take pull requests and let people file issues to fix bugs/errors in the book.

I have to do some sanitizing of the repo first, and figure out a license, but it's on my TODO list.

I've read through about half of the on-line content and I'm impressed, I would gladly pay for a completed version, particularly if it was available to read on a kindle.

So, please consider finding a way to make this project worth your while as I really want to see this completed.

I was hoping to see how to deal with Path finding and interpolation.

Do you run the pathfinding and set the position in each game tick, or does the pathfinding has it's own tick.

There are two stages: first, the path is found. Second, the path is followed.

To find the path often takes longer than one update tick. The old way to handle distributing the job over multiple ticks was threads; the new way is coroutines.

The only thing that should be interpolated is rendering. Pathfinding is part of AI, which, like physics, is part of the "business rules" side of the game, and therefore should be running at a constant rate, which has to be tuned to not eat too much CPU time on slower computers and defines the minimum specs for running the game.

If you don't care if everyone's opponents are equally smart, you can always glance at the clock each time through the loop/level of recursion and cut off the pathfinding if it's taking too long. If you're planning all of the routes through a map (at least on a macro scale - hierarchical, highway-like pathfinding saves a lot of time if you can stand the occasional quirks of its behavior) at runtime, you might be able to set up a system that steals a few cycles whenever there's time left over while the previous area is being played and then only blocks if it still isn't done when needed. But at that point, why not compute those paths really ahead of time (at map build) and then load them in as part of a map file?

I'm going to jump on the bandwagon and say that these are very well written - clear and concise, but they still retain authorial voice, and the examples work as intended. I found them of interest even though I work in general systems, but not games.

But, one question: in the "Subclass Sandbox" (http://gameprogrammingpatterns.com/subclass-sandbox.html) chapter, shouldn't the activate member function be public? That is, isn't that function the interface to the outside world? As written, the Superpower abstract class has no external interface.

I find most pattern texts rather weird, this one is no exception. They start out with a super convoluted OOD, then refactor to something better but still fairly ridiculous. Case in point the Type Object Pattern, ridiculous straw man design refactored to something cleaner but still more complicated than necessary. If you find yourself working on a team and some one purposes the starting point you must be dead because you are in one of the inner circles of hell.

I remember reading through that website when I was researching game object systems. Very useful resource!

Here's my implementation of a component-based game object system, if interested:

https://github.com/surjikal/cbgos-experiment

Now if only there was an annotated encyclopedia of discrete approximations to accompany this...

Would love to see a version of this tuned for a language like Erlang.

Type Object aka the Strategy Pattern.

It's surprising that the singleton is there - from what I have read on altdevblogaday and other gamedev websites it seems that game developers have long since moved past that antipattern. Honestly, I wouldn't have re-iterated the GoF patterns at all: there is already plenty of literature covering them.

Otherwise, quite informative.

If you'd bothered to click through to that chapter, you'd have seen that it's actually a lengthy dissertation on why singletons are a bad idea, including seductive patterns that are actually singletons in disguise and a couple better alternatives for when global state is really unavoidable.

If you had actually read the article about the Singleton, you would have seen that it discourages its use and explains in great detail what's wrong with the pattern and why you should stay away from it.

+1 to this site for tackling this overused anti-pattern.

Reply on news.ycombinator.com