Game Programming Algorithms and Techniques

Game Programming Algorithms and Techniques

English | 2014 | ISBN: 978-0-321-94015-5 | 350 Pages | PDF | 10 MB

Game Programming Algorithms and Techniques is a detailed overview of many of the important algorithms and techniques used in video game programming today. Designed for programmers who are familiar with object-oriented programming and basic data structures, this book focuses on practical concepts that see actual use in the game industry.
Sanjay Madhav takes a unique platform- and framework-agnostic approach that will help develop virtually any game, in any genre, with any language or framework. He presents the fundamental techniques for working with 2D and 3D graphics, physics, artificial intelligence, cameras, and much more.
Each concept is illuminated with pseudocode that will be intuitive to any C#, Java, or C++ programmer, and has been refined and proven in Madhav’s game programming courses at the University of Southern California. Review questions after each chapter help solidify the most important concepts before moving on.
Madhav concludes with a detailed analysis of two complete games: a 2D iOS side-scroller (written in Objective-Cusing cocos2d) and a 3D PC/Mac/Linux tower defense game (written in C# using XNA/ MonoGame). These games illustrate many of the algorithms and techniques covered in the earlier chapters, and the full source code is available at
Coverage includes

  • Game time management, speed control, and ensuring consistency on diverse hardware
  • Essential 2D graphics techniques for modern mobile gaming
  • Vectors, matrices, and linear algebra for 3D games
  • 3D graphics including coordinate spaces, lighting and shading, z-buffering, and quaternions
  • Handling today’s wide array of digital and analog inputs
  • Sound systems including sound events, 3D audio, and digital signal processing
  • Fundamentals of game physics, including collision detection and numeric integration
  • Cameras: first-person, follow, spline, and more
  • Artificial intelligence: pathfinding, state-based behaviors, and strategy/planning
  • User interfaces including menu systems and heads-up displays
  • Scripting and text-based data files: when, how, and where to use them
  • Basics of networked games including protocols and network topology

3D Graphics

… The set of algorithms necessary to draw 3D objects into a 2D color buffer are collectively known as software rasterization , and most courses in computer graphics spend some amount of time discussing this aspect of 3D graphics. But modern computers have dedicated graphics hardware, known as the graphics processing unit (GPU), that knows how to draw basic building blocks such as points, lines, and triangles.

Because of this, modern games do not need to implement software rasterization algorithms. The focus is instead on giving the graphics card the data it needs to render the 3D scene in the desired manner, using libraries such as OpenGL and DirectX. And if further customization is necessary, custom micro-programs, known as shaders , can be applied to this data as well. But once this data is put together, the graphics card will take it and draw it on the screen for you. The days of coding out Bresenham’s line-drawing algorithm are thankfully gone.

One thing to note is that in 3D graphics, it’s often necessary to use approximations. This is because there simply isn’t enough time to compute photorealistic light. Games are not like CG films, where hours can be spent to compute one single frame. A game needs to be drawn 30 or 60 times per second, so accuracy must be compromised in favor of performance. A graphical error that is the result of an approximation is known as a graphical artifact , and no game can avoid artifacts entirely.

Networked games


Imagine you are mailing a physical letter via the postal service. At a minimum, there is an envelope that has the addresses that define both where the letter is from and where it is going. Usually there also is some sort of stamp affixed to the letter, as well. Inside the envelope is the actual data you wanted to transmit—the letter itself. A packet can be thought of a digital envelope that is sent over a network. A packet has addresses and other relevant information in its header , and then the actual data payload it’s sending out.

For envelopes, there is a fairly standardized method of addressing. The from address goes in the top-left corner, the destination address is in the middle right, and the stamp goes in the top-right corner. This seems to be the norm in most countries. But for networked data transmission, there are several different protocols , or rules that define how the packet must be laid out and what must happen in order to send it. Networked games today typically use one of two protocols for gameplay: TCP or UDP. Some games also might use a third protocol, ICMP, for some limited non-gameplay features. This section discusses these different protocols and when they might see use.


IP, or Internet Protocol , is the base protocol that must be followed to send any data over the Internet. Every protocol mentioned in this chapter, whether ICMP, TCP, or UDP, must additionally follow Internet Protocol in order to transmit data. This is even if the data is going to be transmitted over a local network. This is due to the fact that in a modern network, all machines on a local network will be assigned a specific local address that can be used to identify a particular local machine via IP.

The Internet Protocol header has a large number of fields, as shown in Figure 12.1 . I won’t cover what most of the elements in the header mean, but countless resources online go over what each and every part of this header (and all the other headers in this chapter) refers to.

Sample Game: Side-Scroller for IOS



The Objective-C language was originally developed in the early 1980s with the goal of adding object-oriented concepts to C. It was developed around roughly the same time as C++, though at different laboratories by different researches. Objective-C really was not used very much until NeXT, a company started by Steve Jobs, licensed the language for their new platform. Although NeXT never really gained that much popularity, as part of Jobs’ return to Apple in 1996, NeXT came with him. The NeXT operating system was then used as the base for Mac OS X, and later the iOS operating system. Today, all GUI programs developed for the Mac and any iOS device must use Objective-C on at least some level.

There are some notable differences been C++ and Objective-C, most notably Objective-C technically does not have the concept of member functions. Rather, classes are sent messages and then respond to them—this means that all messages must be passed and processed dynamically, whereas in C++ member functions are only dynamic if the virtual keyword is utilized. Even though they aren’t technically member functions, during this chapter I will still refer to them as such because the terminology is more familiar.

The syntax for message passing in Objective-C might be a little odd for someone used to the C++/Java language style. To call a member function in C++, one might use the following:

Sample Game: Tower Deffense for PC/MAC



Microsoft developed C# (pronounced C sharp ) in order to have a language that was similar to C++ or Java, but enabled rapid development of Windows applications on the .NET framework. Like Java, C# is not compiled directly into native code, but into a byte code that can then run on a virtual machine. At first, there was only a virtual machine that could run on PCs, but now there are open-source implementations of the C# virtual machine on many different platforms.

Though there initially were many similarities between C# and Java, over time the languages have diverged pretty dramatically. But because it is syntactically very much related to both C++ and Java, the language is still relatively easy to pick up for someone experienced in either of these languages. Over time, C# has become the language of choice for rapidly developing GUI apps for Windows. Because of this and other reasons, C# is a very popular choice for game development tools—engines such as the newer versions of Frostbite (used for the Battlefield series) use C# heavily in their toolchain.