Game Programming Knowledge Dump

General Programming

Prerequisites: Basic knowledge of how to write code.

Destination: Somewhere beyond where you’re currently at.

MIT Introductory Software Engineering Course from the 1986. This course dives into the heart of what software development is really about, focusing more on design and approach than technical specifics. Recommended for any level of programmer.

Python Coding Standard. A really solid guideline on how to write legible code, applicable to more than just Python. It often provides compelling arguments for its verdicts, though obviously, you should form your own opinions. Whatever you do, be consistent.

Behavioral Driven Development. This is how you should approach unit tests, always. Relying on unit-testing in this way is a great method to becoming a better software architect. (You are employing unit tests, right?)  Test-Driven Development in general will force you to think about dependency-injection and code modularity when writing your code, which will ultimately lead to a much more flexible and maintainable codebase.  This, in the long-term, leads to much faster development and iteration.

An Argument For Ubiquitous Contract-Signer Relationships. I couldn’t find a resource tackling this issue, so I figured I’d make a quick post describing the general principle. If you’re not familiar with this idea, then trust me, employing it will make your code beautiful!

Intel’s SIMD Intrinsics Guide. If you’re doing any SIMD/SSE/AVX programming, this is a must-have bookmark. If you’re doing any 3D math in your game (you probably are), and you’re in C or C++, you’ll want to either implement or acquire a vector and matrix math library that utilizes SIMD. (You’ll need one that works specifically with 2-to-4-dimensional vectors and affine transforms, not just any old SIMD matrix math library.  Bonus points for supporting vectors of 16 bytes and 8 shorts!) When I implemented mine, this was by far the most crucial resource. Otherwise, get familiar with C++ and its various compilers’ alignment keywords, define some macros, Google extensively, and get cracking! I wish I could give you better resources for this, but sadly, the supply of such resources on the internet is lacking.

Bit Twiddling Hacks, by Sean Eron Anderson. A must-have bookmark if you’re doing lots of bit manipulation or low-level optimization (which you most likely will be if you’re working in graphics, procedural generation, or voxel engines!) I come back to this slightly too often…

Quick Tips and Rules-of-Thumb:

  • YAGNI (You Ain’t Gonna Need It!) When a section of code becomes deprecated, it’s often best to delete it, assuming no one is depending on it. This saves the cost of maintaining it and reduces code bloat. When you delete a giant wall of code, it should be a deeply gratifying feeling.
  • KISS (Keep It Simple Stupid!) It’s easy to get caught up over-engineering a problem because its fun or gratifying, but the result is often code that’s harder to work with, and a huge waste of effort. Don’t rationalize it, just do what’s best for you and your colleagues’ productivity! Being in this mindset can be just as gratifying, I promise.
  • Refactor religiously. Make it part of your development cycle. Know that all creative processes, including programming, are highly iterative! If you’re afraid that something will horribly break in the face of change, that probably means it should be refactored asap.
  • Code should be as self-documenting as possible. If some bit of code cannot be understood by merely reading it, consider refactoring it so that it can be before deciding to add a comment. (Comments themselves often stagnate to the point of uselessness.) A great way to do this is to encapsulate the undesirable portions of code into well named functions.
  • Optimize and engineer as late as possible. When you do these things prematurely, it’s often a waste of time, and the resulting code is harder to maintain and debug than the naive/simpler implementation. Don’t be afraid to have a simple but utterly lacking solution when its perfectly sufficient for the time being!
  • Unit tests are wonderful, though they can be over-utilized. When something is complex, consider writing your test cases first, and then writing your implementation to fulfill it. Frequent unit testing tends to result in highly modular, well-designed APIs, particularly because they require it, and they force you to think of your code from the client’s perspective and not from the implementor’s! They can also reduce the time to a complete implementation dramatically if the requirements are complicated enough.
  • Consider using other peoples’ APIs, and research your options carefully. However, don’t be afraid to reinvent the wheel when others’ APIs cannot possibly do quite what you need. Make your wrapping code flexible enough that you can swap out APIs when necessary with as little pain as possible.
  • The amount of hype a programming language receives is inversely correlated with its real world utility!

General Game Dev

Prerequisites: Beginner

Destination: A broad understanding of what really goes into game dev! And some hopefully provoking ideas!

Fix Your Timestep! A brief overview of a ubiquitous and ideal way to structure your high-level game loop. Everyone from Valve to Id to Mojang uses it.  Literally all of the cool kids.

Persistent Myths About Game Development. This article describes how game development should be executed, with an Agile-ish methodology, in stark contrast to ubiquitous traditionalist methods. Notably, it treats the methodology as something that should also extend to designers. (But did we really need this article to be convinced that design docs are worthless?) Definitely good if you’re either unfamiliar with Agile or unconvinced of its utility. I’ll relink this later.

An Overview of the Various Interpolation Methods. This particular resource has some nice visuals, so I highly recommend it. You’re going to be interpolating between things a lot if you’re writing an engine, especially if you’re working in graphics, movement, animation, or even networking… so familiarize yourself with the various interpolation methods! Consider implementing these methods somewhere in your codebase as you’re reading this.

Quaternions by Euclidean Space. Really solid, math-y overview. You’ll inevitably encounter these in any kind of 3D engine, so learn them well. For interpolating between quats (“slerp”-ing), Euclidean Space’s article is the least erroneous of any implementation I’ve found. (See also the corrections beneath the given implementation.) For efficiency, however, I would defer to Cesium’s implementation. For other forms of quaternion interpolation (important depending on your use case, e.g. for animation), see Jonathan Blow’s article.

Quadtrees on Wikipedia. This is a fairly ubiquitous way of organizing game entities in a 2D or flattened 3D space, and you’ll quickly wind up needing it as the number of entities in your game world increases. Octrees are the 3D variant of this, though it’d likely be overkill depending on the application. If you’re trying to organize data that is static (such as certain terrain geometry), you might also consider other tree structures, but those are likely overkill if you already have a generic quadtree implementation available. Don’t optimize until you’re certain that it’s necessary! Finally, if possible, allow any elements contained in a quadtree to maintain a reference to their containing node in the tree, so you can quickly move those elements without searching through the tree.

Amit’s Game Programming Info. A link dump of invaluable game dev information… similar to this one! His is more condensed, but it’s full of gems, especially with regard to procedural generation and pathfinding. I’m still working my way through them. I’ll relink this later.

AI and Machine Learning

Prerequisites: Beginner

Destination: Intermediate-ish

Post-Mortem: Designing AI-Algorithms for Turn-Based Strategy Games, on Gamasutra. A nice, plain-English article to get you thinking about potential applications for more advanced AI and ad hoc, rule-based ways of applying it.

Intel’s Game AI Overview. Covers the basic methods of constructing a typical video game AI, using rule-based systems, finite-state machines, pathfinding, and more. Doesn’t cover anything in depth, but its a nice primer to get you thinking about the applications. I’m mostly interested in non-traditional game AI, personally, whereas most games use rule-based systems exclusively. Pretty boring!

Amit’s Game Programming Info, specifically the section on Artificial Intelligence. Another link dump, but more condensed than this one. Great resource.

Steering Behaviors for Autonomous Characters. Useful when you need actors in your game to pursue or avoid something, stay along a given track, etc. Basically, whenever something in your game needs to move in a continuous fashion in response to a stimuli.

Pathfinding on Wikipedia. If anything in your game ever needs to find a path to something else in your game, this is how you do it. In particular, you’ll want to read up on the A* pathfinding algorithm, as it’s ubiquitous across game development. There are many variations thereof, so be sure to read up on select the one best suited to your purposes. (In particular, ways of precomputing paths before distributing your game are invaluable if you’re working with a static environment.)

Rules-Based Systems. An incredibly straightforward way of implementing an AI. Conflict-resolution would typically be resolved by some sort of priority determination scheme, which could even by informed by one of the AI training mechanisms you’ll inevitably discover as you go on. There can be some room for optimization here, depending on the complexity of your system.

Genetic Algorithms on Wikipedia. This is a very digestible algorithm for optimizing a point on a very complicated curve, inspired by evolution as observed in nature. Here’s a possibly better introduction. Box Car 2D is an amazing example of GA’s untapped potential with respect to game dev, and will hopefully inspire you to read up on the subject! Extremely fascinating stuff.

Neural Networks on Wikipedia. (Notice how I just keep linking Wikipedia?) Also, here’s a nice academic introduction. Essentially, these are simple models of networks of neurons, as seen in actual living beings, applied to real-world problem domains… one such domain being video games! Specifically, the application is training artificial intelligences to play your game well, either dynamically (as the game is being played) or statically (pre-trained before distribution.) Also, combine this puppy with genetic algorithms and you’ll have a really amazing AI, or even a simulation, in no time! Note that the standard method of training is back-propagation, however. I’ve screwed around with this stuff a lot, as I find it incredibly fascinating.

Decision Trees and Their Training. Essentially, a decision tree is a tree-graph of decisions weighted by probabilities, which can be solved for via several classes of optimization algorithms. If you’re going with a simple rules-based system and the problem has too many variables to be manually well-implemented, this can be a nice alternative.

Procedural Generation

To be continued!

Voxel Engines

To be continued!

Leave a Reply

Your email address will not be published. Required fields are marked *