Game Programming Patterns

http://gameprogrammingpatterns.com/

by GuiA • 13 years ago

265 64 13 years ago

gameprogrammingpatterns.com

Ellipsis753• 13 years ago

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

karl_gluck3• 13 years ago

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

munificent9• 13 years ago

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.

exemd• 13 years ago

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.

asperous• 13 years ago

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.

qznc• 13 years ago

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)

idunno246• 13 years ago

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!

Jare4• 13 years ago

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

MartinCron• 13 years ago

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

krakensden• 13 years ago

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.

karl_gluck3• 13 years ago

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.

vilya• 13 years ago

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

tracker1• 13 years ago

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.

seivan• 13 years ago

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.

mtinkerhess• 13 years ago

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.

GeneralMayhem2• 13 years ago

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?

robertkrahn012• 13 years ago

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

munificent9• 13 years ago

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

interpol_p2• 13 years ago

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.

robertkrahn012• 13 years ago

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.

drblast2• 13 years ago

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.

chipsy• 13 years ago

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.

lucaspiller• 13 years ago

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/

zamalek• 13 years ago

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.

GeneralMayhem2• 13 years ago

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.

ndepoel• 13 years ago

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.

benjamincburns• 13 years ago

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

babuskov2• 13 years ago

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.

munificent9• 13 years ago

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.

jason_slack• 13 years ago

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.

jwmoz• 13 years ago

Type Object aka the Strategy Pattern.

Jare4• 13 years ago

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.

epsylon2• 13 years ago

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.

mjn2• 13 years ago

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?...)

munificent9• 13 years ago

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.

Jare4• 13 years ago

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.

philbarr• 13 years ago

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.

sspiff• 13 years ago

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.

munificent9• 13 years ago

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.

tieTYT• 13 years ago

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.

GuiA• 13 years ago

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.

lifeisstillgood• 13 years ago

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

stonemetal• 13 years ago

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.

scott_s• 13 years ago

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.

Scramblejams• 13 years ago

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

nickporter• 13 years ago

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

Game Programming Patterns

Related Stories