Last Inner Product

12 August 2014

Programming in games has always been a discipline that embraces rapid change. Very few people code the same kinds of systems in the same ways they coded 15 years ago; fewer still expect to code the same kinds of systems in the same ways they’re coding now in 15 years’ time. And the pace of change in ever-increasing. Radical change is around every corner. That being said, we should take care not to throw out all the hard-earned lessons of the past and take time to examine how they are still applicable and relevant today. 

I have chosen a few of those old lessons to share with you and my thoughts on them. Not everyone will agree with my choices or my opinions on those choices. But if I only said things that everyone agreed with, I wouldn't really be saying anything at all. I invite you to take the time to draw your own conclusions.

“The ultimate weapon of game programmers is context. You know the needs of your game and can tailor the memory manager accordingly.”
- Brian Hixon, Daniel Martin, Rob Moore, Greg Schaefer, Richard Wifall "Play by Play: Effective Memory Management" GameDeveloper Magazine February 2002

There are very few problems that cannot be better solved by having better context. It remains a common programmer error to attempt to make solutions too generic, to try to solve all problems instead of simply the one at hand. In doing so, nine times out of ten, a programmer will add additional contraints to the problem that will in fact make the solution worse in all cases.

“The obvious next step is to take this technique and put it in your game today. I want to be clear about this: I want better water in games, better lava, better liquid in general, and I want it now. All joking aside, though, I don't want to imply that you could actually drop this into your engine in an hour and a half; there are admittedly some obstacles with this technique.”
- Brian Sharp "Moving Fluid: The Conclusion of a Two-part Series about Implicit Surfaces" GameDeveloper Magazine August 2000

Ten years ago Brian Sharp called for better fluids and better special effects. Today that call remains. While there have been some improvements and a few clever implementations, it remains that we do not devote nearly enough time or resources to giving these effects a proper treatment in most games. Partially that's due to the above, that we try to find over-general solutions to problems that deserve a specific solution. But mostly it's due to the same reason it was due to ten years ago: it doesn't make enough difference to the final game.

“If all of Doom was written in assembler and the programmer could manage the overhead correctly, Carmack theorizes it would only make the game 15% faster. And, although the main raycasting trace in Wolfenstein was written in assembly language, Carmack says he could write Wolfenstein faster in C because of today's better algorithm technology.”
- Alexander Antoniades "Monsters from the Id: The Making of Doom" GameDeveloper Magazine Premier 1994

Notwithstanding the nonsense phrase "algorithm technology," I would suggest this claim would be largely unchanged today. Compilers and optimization approaches have not improved all that significantly. There remains a significant percentage of cases where it's very easy to write an assembly routine that is much more performant than its C or C++ equivalent. Mostly due knowledge about the data (context) which the compiler cannot know or ABI constraints. That said, one thing has changed: The gap between instruction performance and memory performance is much, much wider. The biggest optimization opportunities are in proper management of data. Instruction-level performance is still important and will remain so for some time. A great deal of code is still written in assembly and that will remain true. However, in a world where the abstraction tax is readily paid through scripting languages and javascript UIs, the bar for improving performance is much lower now than it's ever been.

“Do not call a separate pixel-plotting routine in image-drawing code. Use inline code or functions instead. Think about how many calls it takes to draw one screen or image.”
- Matt Pritchard "Ten Techniques for Faster Image Drawing" GameDeveloper Magazine February 1995

Where there is one, there are many. That's more true today than it's ever been. And it's always been true. However, it's also true that more than ever before (given the spectactularly disatrous success of object-oriented programming), the actual data models and transformation costs are ignored by programmers and dozens or even hundreds of routines are assigned to individual "objects" which all "act" independently and conspire to sabotage performance, maintainability, testability and good sense.

“For frequently drawn images, use specific routines with hard-coded values instead of general-purpose routines. You can choose the variables you encode as constants and remove functionality that you don't need.”
- Matt Pritchard "Ten Techniques for Faster Image Drawing" GameDeveloper Magazine February 1995

Another reminder that "generic" is not a goal. The work of programmers is to transform data from one form to another. Sometimes the same tool can be used many times to do that. Sometimes it's much, much better to solve the more specific problem with a more specific solution. The goal is to solve the problem well. No player is going to give you kudos because you re-used a class in an innapropriately generic way.

“If you don't like math, well, computer graphics is math for the most part, so I'm not sure what to tell you. My goal is to describe the math in an accessible way, but I'm not going to hide the fact that math underlies everything about computer graphics, especially three dimensional computer graphics.”
- Chris Hecker "Perspective Texture Mapping, Part II: Rasterization" GameDeveloper Magazine JUNE/JULY 1995

Math remains at the heart of what we do. It's as important today as it was in 1995 to understand at least the fundamentals. But more than that, we have learnt that you simply cannot hide it. Not just from programmers, but from all game developers. Artists cannot write good shaders without understanding at least the fundamentals of algebra, trigonometry, and geometry. And the efforts to hide that from them has more often than not ended in poor results if not tears. Designers cannot design good systems without understanding statistics and algebra at the very least, and those that do not often end up with very poor systems. Instead of trying to hide the mathy bits, it's usually better to teach it instead.

“The processor cache is usually an object of great fear, wonder, and misunderstanding. A friend of mine named Terje Mathisen says, "All programming can be thought of as an exercise in caching." Although Terje isn't talking specifically about the processor cache, this is a rule to live by when you're trying to optimize on modern processors. If we apply this idea to the processor cache and memory bandwidth, it means, "Figure out how to put your important data in the cache and keep it there." This may seem obvious, but keeping your data in the cache is more difficult than you might think.”
- Chris Hecker "Memory Miscellanea" GameDeveloper Magazine OCTOBER/NOVEMBER 1995

The importance of hardware caches and understanding how to best utilize them has never been more important. There is simply no good excuse not to deeply understand whatever caching and data transfer hardware may exist on your devices. It's simply poor practice to not design your data and systems around that knowledge as best you can. The most likely bottleneck in any game is the accumulated time spent waiting for data. And it's usually spread so deeply through the fundamental design choices and and abstractions in the systems that it cannot be fixed late in production without a re-write, which late in production, is impossible to justify. So good stuff that would be valuable to the play experience ends up getting cut.

“The solution is easy. Keep two heaps. One heap is used to satisfy static allocation requests, and one for cached requests. You can simulate this with one heap by allocating the static requests at the bottom of the heap (growing up) and the cached requests at the top of the heap (growing down).”
- Jonathan Clark "Object Cache Management" GameDeveloper Magazine FEBRUARY/MARCH 1996

Over the last 20 years a lot of effort has been put into garbage collection and dynamic memory management and other types of "managed memory" systems based on one totally erroneous assumption: that managing memory is hard. Managing memory is no harder than managing any other kind of finite resource. It's the same as managing time within the frame, or scheduling out a project. The solution is easy. It's always been easy. Analyze what kind of data you have, what kinds of patterns of access and allocation are required and divide it up into categories of similar things. Accessed together? Stored together. Lots of small items? Combine them. Unpredictable lifetimes? Keep that separate from the stuff that has predictable lifetimes. Many of the managed memory cures that have come into recent popularity are a great deal worse than the disease of simply managing your memory ever has been.

“A helpful debug tool is to zero out all freed memory. Then, whenever a reference to memory that is supposed to be free is used, a crash is likely to result and you can track it down easily.”
- Jonathan Clark "Object Cache Management" GameDeveloper Magazine FEBRUARY/MARCH 1996

Another tip: Fill memory with a recognizable sentinal. "0xdeadbeef" is a popular choice. And since many allocations are aligned and have some unused area at the end, fill that too. That way, if you ever do accidentally stomp that area, you can test for it.

“One set of issues is with the workflow in creating procedural textures: It can be difficult to find the right person for the job, since building texture procedurally is effectively its own discipline.”
- Sean Barrett "Hybrid Procedural Textures" GameDeveloper Magazine October 2004

While most of us still rely very heavily on pre-created textures, they are mixed very heavily in shaders. The world of hybrid procedural textures has come to pass and it is very evident it has become its own discipline. Although I'd really like to see more "procedure" in game textures. We could do a lot more to indicate things for the player, provide clues and signals and realtime feedback if we weren't so generally concerned with trying to make things look "real" - A brick on a real building isn't likely to change while you're looking at it very much. But there's no good reason why a "brick" in a game needs the same constraint.

“Bugs in software generally arise from complexity in control flow and complexity of state. A design that requires more "if" statements is likely to have more bugs from incorrect conditionals; designs with more variables offer more opportunities to fail to maintain invariants between them. Programs with little flow control or state, e.g. scripts, offer few chances for bugs.”
- Sean Barrett "Opening Doors" GameDeveloper Magazine September 2004

Another often ignored advantage to understanding what your source data is and what you need to transform it into (and simply doing that), is that it usually simplifies state checks and control flow by at least an order of magnitude. The more code has to work out what data is and what it's supposed to become at runtime, the more chances you've introduced a bug.

“Gathering data solves only half the problem; to be useful, the data must be viewed by a human.”
- Sean Barrett "Interactive Profiling Revisited" GameDeveloper Magazine August 2004

Probably the most singificant advancement of the last twenty years in games has been the realization of the importance of usability. Not just in the game interface (although those have gotten much better too), but in all aspects of development. That APIs are just interfaces for programmers and should be usability tested. That the usability of game creation tools has a direct impact on the quality of the game. And that all the data in the world isn't much use if you don't know what specific action should be taken based on it.

“Ideally, we would like all character motions to be generated dynamically at runtime: If AI-controlled characters want to sit down, they figure out how to move their muscles to get over to the chairs and place their butts firmly upon them. This is a very difficult thing to do, as a general problem it is far out of our reach.”
- Jonathan Blow "Experiments I'd Like to Work On" GameDeveloper Magazine June/July 2004

The argument among totally dynamic, motion capture, hand-animated and hybrid animation models hasn't changed much. But I'm certain of one thing, the ideal is not that everything is generated dynamically at runtime. That doesn't matter one bit. The ideal is that characters animate as the player expects them to animate. That the characters behave as the players expect them to behave. Sometimes very realistically, sometimes not at all. The ideal is that you can meet (or dare I hope, one day, exceed) the players' expectations for believability given the constraints of cost and resources. However you do it.

“If you read non-sequentially from the disc, the data rate will drop to zero whenever the laser moves to a new location. In designing your game, you must somehow work around this problem. It’s possible to cover up the seeks by playing previously buffered sound and video, but you could also display a static screen (text, for example) to distract the player.”
- Dan Teven and Vincent Lee "Optimizing CD-ROM Performance under DOS/4GW" GameDeveloper Magazine AUGUST/SEPTEMBER 1996

While the problems of optical media have haunted us through CD, DVD and Bluray and we may hope to see the end of it one day, the larger problem will never change. You cannot design a system as complex as a game from end to end without understanding the constraints of how your data is transferred. From the source, whether that's optical media, HTTP server or harddrive, to the various data caches, register files and DMA engines. To design code first and not data first is to ignore the fundamental problem of programming real games on real hardware.

“The main point here is that you cannot expect the compiler to do much work for you beyond a rote translation of the code you write into native machine code. (With the incredible code generation bugs I’ve found, you sometimes can’t even expect this.)”
- Chris Hecker "More Compiler Results, and What To Do About It" GameDeveloper Magazine AUGUST/SEPTEMBER 1996

The compiler is a tool. A programmer's work is not to write code. A programmer's work is to solve problems. Those problems are solved by transforming data. That data is transformed by code. The compiler is just a convinient tool in that chain. The programmer ultimately is responsible for making sure the problem is actually solved, and not understanding the tools and limitations of those tools will make that job much harder and the programmer less effective.

“The best-established algorithm for the general searching of optimal paths is A* (pronounced “A-star”). This heuristic search ranks each node by an estimate of the best route that goes through that node.”
- W. Bryan Stout "Smart Moves: Intelligent Path-Finding" GameDeveloper Magazine OCTOBER/NOVEMBER 1996

In the intervening time I wish we would have spent less time worrying about the best paths and a lot more time worrying about good, believable paths.

“It seems that we are dizzily cloning the clones of old clones. Wouldn’t it be better in the long run to take the time to design something original once in a while?”
- Chris Crawford "Weeds and Oaks" GameDeveloper Magazine JUNE 1997

I dare to say with the popularity of game jams and the indie scene, more original games were made in the last year than total in the twenty years before. But the popularity of the "clones of old clones" hasn't waned one bit. If anything, it's clear that there are even fewer really popular genres now than ever before. While we should absolutely push the experimental edge, what we shouldn't forget is that people are comfortable with the familiar. The bigger the change you want to make, the more grounded in the familiar it needs to be in order for people to build a mental bridge from where they are to where you want to take them. That's as true for our game designs as it is for our game tools.  

“One of the biggest mistakes I’ve made in product design is asking engineers, “Can it be done?” Unless you’re asking a First-class programmer, the question is useless. More specifcally, responses fall into one of three categories: (Lousy programmer) “Sure, that’s no problem.” (Mediocre programmer) “Nope. Can’t be done.” (First-class programmer) “I could do it like this and it’ll take two weeks. Or I could make a slight modication like this and it’ll take five hours.””
- Tzvi Freeman "Creating a Great Design Document" GameDeveloper Magazine August 1997

Of course it can be done. That's a silly question. I don't know many programmers that at don't believe they couldn't find a solution to a problem given enough time. The "first-class programmer" is not the one that can give a producer an off-the-cuff time estimate though. A first-class programmer can only do that if he's already done it before. And most of the time, we're not solving exactly the same problem as we've solved before - there are always new constraints that make the problem very different - otherwise, we'd all still be using SNES game engines. A first-class programmer will be able to tell you what he doesn't understand about the problem, what the risks are as he does understand them, and what he'll need to do in order to get an understanding to at least have a test model running. Or at the very least, figure out some way to scale the problem to fit in the time available. 

“One of the most important things that I’ve learned in the past few years is that the number of hours you work does not necessarily correlate to your productivity. Productivity is based on the work that you accomplish, not the hours that you work.”
- Brian Hook "So Long and Thanks for the Rail Gun" GameDeveloper Magazine February 1998

Counting hours is as bad as counting lines of code. It's a nonsensical metric. But how do you measure real accomplishment, insight and quality? How do you measure the things you didn't have to do because someone did it right in the first place? How do you measure the time that was saved because someone didn't make a braindead decision because they were too rushed to think it through? We haven't made a whole lot of provable progress on those metrics yet. But let's keep trying!

“Remember, however, that the quicker the motion, the greater the quality loss, because the area of newly-exposed polygons (which are now carrying erroneous textures) will be larger. Teleportation, therefore, is problematic because all textures will be unexpected.”
- Jonathan Blow "Implementing a Texture Caching System" GameDeveloper Magazine April 1998

The techniques of texture caching and pre-loading haven't changed much, really. And the more general lesson is equally still applicable: You cannot properly design game systems without knowing the constraints of your (most relevant) data. A seemingly simple change e.g. Character can teleport anywhere or move 10x as fast, can dramatically change the problem and therefore dramatically change the solution required. There aren't many generic one-size-fits-all solutions in the space of making games and the all too common attempts to create them are a fool's errand. "Future proof" is the perpetual motion machine of video game programming. 

“We’ve got to bring entertainment to the places where most people socialize. I travel a lot. I see games in sports bars, but not in hotel lobbies. I see fast food locations without games. I see coffee bars with no games, and many chain restaurants with no games or amusements. In most of these locations, a pinball machine would look strange, but a countertop web terminal with easy touch screen menus and game play would not.”
- Nolan Bushnell "A Product Whose Time Has Come…Again" GameDeveloper Magazine July 1997

I love that we have gone from a time not so long ago where there were so many places where games were not present, to games being present in virtually everyone's pocket. There is no place without games because people bring their games with them wherever they go. The final frontier for games is with our poorest kin, those that cannot afford the smartphones and tablets that many of us take for granted now. Looking forward to the next twenty years, I hope that everyone, everywhere will have games to play and to learn and to make, wherever they are.

“It’s getting pretty bad for some guys out there. First, women wanted the remote. Then there was Title IX and that equal pay thing. But now it’s getting serious, because we want your mouse, and we want it now... A man practically has to elbow his wife and daughters aside to get some quality time with his flight simulator these days.”
- Nancie S. Martin "Take the Y Out of Computer Games" GameDeveloper Magazine SEPTEMBER 1997

Women had a tough time of it then. Women still have a tough time of it today. Not just women players, but women game developers. The difference between then and now, I think, is that some of us men are much more aware of it and would really like to do something to improve that situation. The industry as a whole can vary from slightly biased to outright masogonistic, but never totally fair toward women. Someday I'd like to see an industry that's fair, open and inviting toward all people. Not for the sake of diversity, or of the different perspectives or ideas that could influence our games for the better, but because its right. I'd like to see an industry where great women programmers aren't rare and a world where I get a chance to work with them.

“While you can pick up a book such as Bjarne Stroustrup’s Design and Evolution of C++ to help you understand why C++ is such a screwed up language, it still doesn’t address the issue that C++ is a screwed up language. It’s constantly evolving, getting bigger and uglier, and pretty soon it’s going to implode under its own weight.”
- Brian Hook "How I Spent My Summer Vacation, or What I Learned While Working on QUAKE 2" GameDeveloper Magazine January 1998

Oh, boy. If anything it's gotten so much worse.