Game Programming Algorithms and Techniques: A Platform-Agnostic Approach (2014)
Preface
It wasn’t long ago that the knowledge necessary to program commercial video games was only available to a small number of game industry veterans. In that bygone era, learning about the actual algorithms that were used in AAA games was akin to learning some dark and forbidden knowledge (hence titles such as Michael Abrash’s seminal Graphics Programming Black Book). If one wanted to pursue a formal education in game programming, the choices were more or less limited to a handful of specialized trade schools. But over the past ten years, video game education has changed dramatically. Several top universities now offer courses and degrees in video game programming, and more join the ranks every single year.
A side effect of this explosion of video game curriculum is that the expectations for new hires in the industry have risen dramatically. In the early 2000s, all that was expected from junior programmers was a solid computer science background and a demonstrable passion for creating video games. The hope was that with this solid foundation, strong candidates would learn the more advanced game programming techniques on the job. Today, with so many excellent places to get a more games-focused education, an increasing number of companies now expect their junior programmers to have experience with the breadth of topics relevant to programming games.
Why Another Game Programming Book?
The expansion of video game curriculum has also increased the need for books designed with a university setting in mind. However, the majority of game programming books currently on the market target one of two types of readers: hobbyists who want to learn a little bit about making games or professionals who already have years of game industry experience. Both types of books can be frustrating in an academic setting. The hobbyist books may not be academically rigorous enough for a university, and the industry-targeted books will often sail well over the heads of inexperienced students.
One of the courses I teach at the University of Southern California is ITP 380: Video Game Programming. The students who enter the class are typically in their second or third year and already know the basics of programming. Some of the students also have experience in prototyping games using engines such as GameMaker and Unity, but ITP 380 is the students’ first real exposure to programming video games. My hope is that this book will perfectly complement my course and any courses like it at other universities. Although the primary target audience is students in a university setting, anyone who is interested in learning about programming games should find this book extremely valuable.
A unique characteristic of this book is that the first 12 chapters are 100% platform and framework agnostic. This means that irrespective of programming language or target platform, the vast majority of the book will be entirely applicable to most 2D and 3D games. This separates this book from most other titles on the market, which use a specific version of a framework that usually becomes obsolete within a couple of years. By being agnostic, this book should maintain its relevance for a longer period of time. This is also helpful for a university setting because different schools may choose to use different languages and frameworks. That being said, the value of code samples is indisputable. Because of this, the last two chapters are overviews of two different games written in two different frameworks, and code samples are provided for these games.
Who Should Read This Book?
This book assumes that the reader already knows how to program in an object-oriented language (such as C++, C#, or Java) and is familiar with standard data structures such as linked lists, binary trees, and hash tables. These topics usually are covered in the first two semesters of a standard computer science curriculum, so anyone who has completed such coursework should be fine. Furthermore, having some exposure to topics in calculus will help readers grasp the concepts discussed in the linear algebra and physics chapters.
Although not a requirement, it is also helpful if the reader has prior experience in the basics of game design, or at the very least is familiar with games. At times, this book will discuss programming mechanics for specific genres, so knowing the references will be very helpful. Having some experience with prototyping games using tools such as GameMaker might also be helpful, but is by no means a requirement.
Though this book is intended for an academic setting, it should be useful for anyone who already knows general programming but is interested in professionally programming games. Topics are always presented through a very practical and application-focused lens, unlike some decidedly academic books.
Finally, because this book has a broad coverage of several different game programming topics, it may prove useful for a junior programmer who wants to brush up on different aspects of game programming. That being said, a seasoned game developer may not find that much in the way of new information in this book.
How This Book Is Organized
The first 12 chapters of this book are an overview of many of the algorithms and techniques used in game programming. These topics run the gamut from 2D and 3D graphics, physics, artificial intelligence, cameras, and more. Although Chapters 1 through 12 are designed to be read sequentially, it is possible to go out of order to some degree. The graph in Figure P.1 demonstrates the dependencies between the chapters—so at the very least, no chapter should be read prior to its dependencies being read.
Figure P.1 Dependency graph for Chapters 1–12.
The last two chapters of the book present sample game case studies that were created to illustrate many of the algorithms and techniques covered in the first 12 chapters. The two sample games are a 2D side-scroller for iOS devices (written in Objective-C using cocos2d) and a 3D tower defense game for PC/Mac/Linux (written in C# using XNA/MonoGame). The full source code for these two case studies is available online on this book’s website: http://gamealgorithms.net.
Book Features and Conventions
This section describes some of the features used in the book and the conventions followed for items such as code and equations.
Sidebars
At certain points in this book, you will find sidebars and notes. This section contains examples of both.
Sidebar
Sidebars are brief discussions of how a particular algorithm or technique was dealt with in actual shipped games. In some instances, these might be personal anecdotes based on projects I worked on in the industry. In other cases, they will be stories about other games. In any event, these asides are designed to give further insight into how the concept in question might be considered when you’re actually creating a game.
Note
Notes are intended to be a bit more fun and tangential. Although they may not have as much pedagogical value, they still might provide further insight into the topic in question.
Pseudocode
In order to maintain language-neutrality, algorithms will often be presented in pseudocode form. The syntax used for the pseudocode has similarity with the scripting language Lua, though there are also clear influences from C/C++ as well as C#. Code snippets will be presented in fixed-font blocks, like so:
function Update(float deltaTime)
foreach Object o in world
// Comment
o.Update(deltaTime)
loop
end
This book utilizes syntax highlighting similar to many IDEs. Keywords appear in blue, comments are in green, class names are in teal, and variables are italicized. Member functions and variables are accessed with a dot in all instances.
In some cases, the pseudocode may be interspersed with prose explaining the code further. In these cases, it will be clear that it’s not the end of the code snippet. Furthermore, in cases where this is done, the full code will be presented at the end of the section with a numbered code listing such as Listing P.1.
Listing P.1 Sample Numbered Code Listing
function Update(float deltaTime)
foreach Object o in world
// Comment
if o is alive
o.Update(deltaTime)
end
loop
end
Note that the preceding pseudocode simply states to check whether the Object “is alive” rather than explicitly calling a particular function. This shortcut will be used in instances where the meaning is clear.
Finally, in some cases, parts of the code may be omitted to save space. This will be done sparingly, usually only when it’s a repeat of previously shown code. The format for omitted code will be a comment followed by ellipses on the subsequent line:
function Update(float deltaTime)
// Update code
...
end
Equations
Certain chapters (particularly the ones on linear algebra, 3D rendering, and physics) will present concepts directly in equation form. This is only done when a particular concept is more clear as an equation instead of in pseudocode. Equations will typically be centered and appear on their own line, like so:
f(x) = a + b
Companion Website
This book features a companion website at http://gamealgorithms.net. Of particular note, this site provides access to the full source code for the game case studies in Chapter 13, “Sample Game: Side-Scroller for iOS,” and Chapter 14, “Sample Game: Tower Defense for PC/Mac,” as well as any errata for the book. Finally, the site also has a forum where readers can post questions regarding both the book and game programming in general.