Sanjay Madhav is a lecturer at the University of Southern California, where he teaches several courses about and related to video game programming. Prior to joining USC full time, he worked as a programmer at several video game developers, including Electronic Arts, Neversoft, and Pandemic Studios. Although he has experience programming a wide range of systems, his primary interest is in gameplay mechanics. Some of his credited games include Medal of Honor: Pacific Assault, Tony Hawk’s Project 8 , Lord of the Rings: Conquest , and The Saboteur .

In 2008, Sanjay began teaching part-time at USC while still working full time in the game industry. After Pandemic Studios was shuttered at the end of 2009, he decided to refocus his efforts on teaching up-and-coming game programmers. His flagship course is an undergraduate-level game programming course that he has taught for more than ten consecutive semesters.

Preface xv

1 Game Programming Overview 1

Evolution of Video Game Programming 2

The Game Loop 5

Time and Games 9

Game Objects 13

Summary 15

Review Questions 16

Additional References 16

2 2D Graphics 19

2D Rendering Foundations 20

Sprites 22

Scrolling 30

Tile Maps 35

Summary 39

Review Questions 39

Additional References 39

3 Linear Algebra for Games 41

Vectors 42

Matrices 58

Summary 62

Review Questions 62

Additional References 63

4 3D Graphics 65

Basics 66

Coordinate Spaces 67

Lighting and Shading 76

Visibility 85

World Transform, Revisited 88

Summary 91

Review Questions 92

Additional References 92

5 Input 93

Input Devices 94

Event-Based Input Systems 99

Mobile Input 105

Summary 108

Review Questions 108

Additional References 109

6 Sound 111

Basic Sound 112

3D Sound 115

Digital Signal Processing 119

Other Sound Topics 122

Summary 124

Review Questions 125

Additional References 125

7 Physics 127

Planes, Rays, and Line Segments 128

Collision Geometry 130

Collision Detection 134

Physics-Based Movement 148

Physics Middleware 153

Summary 154

Review Questions 154

Additional References 155

8 Cameras 157

Types of Cameras 158

Perspective Projections 161

Camera Implementations 164

Camera Support Algorithms 175

Summary 178

Review Questions 178

Additional References 178

9 Artificial Intelligence 179

“Real” AI versus Game AI 180

Pathfinding 180

State-Based Behaviors 192

Strategy and Planning 198

Summary 200

Review Questions 200

Additional References 202

10 User Interfaces 203

Menu Systems 204

HUD Elements 207

Other UI Considerations 217

Summary 221

Review Questions 222

Additional References 222

11 Scripting Languages and Data Formats 223

Scripting Languages 224

Implementing a Scripting Language 229

Data Formats 235

Case Study: UI Mods in World of Warcraft 239

Summary 241

Review Questions 241

Additional References 242

12 Networked Games 243

Protocols 244

Network Topology 250

Cheating 255

Summary 257

Review Questions 257

Additional References 258

13 Sample Game: Side-Scroller for iOS 259

Overview 260

Code Analysis 262

Exercises 267

Summary 268

14 Sample Game: Tower Defense for PC/Mac 269

Overview 270

Code Analysis 273

Exercises 284

Summary 285

A Answers to Review Questions 287

Chapter 1: Game Programming Overview 288

Chapter 2: 2D Graphics 289

Chapter 3: Linear Algebra for Games 290

Chapter 4: 3D Graphics 291

Chapter 5: Input 292

Chapter 6: Sound 294

Chapter 7: Physics 295

Chapter 8: Cameras 295

Chapter 9: Artificial Intelligence 296

Chapter 10: User Interfaces 298

Chapter 11: Scripting Languages and Data Formats 299

Chapter 12: Networked Games 300

B Useful Tools for Programmers 303

Debugger 304

Source Control 309

Diff and Merging Tools 312

Issue Tracking 313

Index 315