Sanjay Madhav - Game Programming Algorithms and Techniques A Platform-Agnostic Approach

ePUB is an open, industry-standard format for eBooks. However, support of ePUB and its many features varies across reading devices and applications. Use your device or app settings to customize the presentation to your liking. Settings that you can customize often include font, font size, single or double column, landscape or portrait mode, and figures that you can click or tap to enlarge. For additional information about the settings and features on your reading device or app, visit the device manufacturers Web site.

Many titles include programming code or configuration examples. To optimize the presentation of these elements, view the eBook in single-column, landscape mode and adjust the font size to the smallest setting. In addition to presenting code and configurations in the reflowable text format, we have included images of the code that mimic the presentation found in the print book; therefore, where the reflowable format may compromise the presentation of the code listing, you will see a Click here to view code image link. Click the link to view the print-fidelity code image. To return to the previous page viewed, click the Back button on your device or app.

A Platform-Agnostic Approach

Sanjay Madhav

Upper Saddle River, NJ Boston Indianapolis San Francisco
New York Toronto Montreal London Munich Paris Madrid
Capetown Sydney Tokyo Singapore Mexico City

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals.

The author and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein.

For information about buying this title in bulk quantities, or for special sales opportunities (which may include electronic versions; custom cover designs; and content particular to your business, training goals, marketing focus, or branding interests), please contact our corporate sales department at or (800) 382-3419.

For government sales inquiries, please contact .

For questions about sales outside the U.S., please contact .

Visit us on the Web: informit.com/aw

Library of Congress Control Number: 2013950628

Copyright 2014 Pearson Education, Inc.

All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, One Lake Street, Upper Saddle River, New Jersey 07458, or you may fax your request to (201) 236-3290.

Screenshot from Jetpack Joyride 2011 Halfbrick Studios. Used with permission.

Screenshot from Jazz Jackrabbit 2 1998 Epic Games, Inc. Used with permission.

Screenshot from Quadrilateral Cowboy 2013 Blendo Games LLC. Used with permission.

Screenshot from Skulls of the Shogun 2013 17-BIT. Used with permission.

Screenshot from Unreal Engine 3 2005 Epic Games, Inc. Used with permission.

Screenshot from Unreal Tournament 3 2007 Epic Games, Inc. Used with permission.

Screenshots from Microsoft Visual Studio 2010 2010 Microsoft. Used with permission from Microsoft.

Image in courtesy of denis_pc/fotolia.

Images in courtesy of York/fotolia.

ISBN-13: 978-0-321-94015-5

ISBN-10: 0-321-94015-6

Text printed in the United States on recycled paper at R.R. Donnelley in Crawfordsville, IN. First printing: December 2013

Editor-in-Chief
Mark Taub

Executive Editor
Laura Lewin

Development Editor
Chris Zahn

Managing Editor
Kristy Hart

Project Editor
Elaine Wiley

Copy Editor
Bart Reed

Indexer
WordWise Publishing Services

Proofreader
Jess DeGabriele

Technical Reviewers
Alexander Boczar
Dustin Darcy
Jeff Wofford

Editorial Assistant
Olivia Basegio

Cover Designer
Chuti Prasersith

Compositor
Nonie Ratcliff

Graphics
Laura Robbins

To my family for supporting me and to all my students
for not driving me crazy (yet).

Even though my name might be the only one on the cover, this book simply would not have been possible without the help and support of many other individuals. Id first like to thank my mom and dad for their support throughout the years as I pursued my education and then career. Id also like to thank my sister Nita for going along with all the crazy and creative things we did when we were younger, and for providing great advice when we became older.

The team at Pearson also has been a pleasure to work with throughout the writing process. It starts with Laura Lewin, my executive editor, who has backed the premise of the book since day one. She and assistant editor Olivia Basegio have provided very useful guidance throughout the writing process. The editorial and production teams, especially Chris Zahn, have also been stellar in helping make the book ready for production, including art, copy editing, and typesetting.

I also want to acknowledge the technical reviewers who blocked time out of their busy schedules to help ensure the accuracy of the bookAlexander Boczar, Dustin Darcy, and Jeff Wofford. Their feedback has been invaluable, and Im confident that the book is technically sound because of it.

My colleagues at USC, especially those in the Information Technology Program, have really shaped who I am as an instructor. Id especially like to thank the current director of the department, Michael Crowley, as well as the director who first hired me as a part-time lecturer, Ashish Soni. Id also like to thank Michael Zyda for establishing and leading the Computer Science (Games) program at USC. My lab assistants over the years, most notably Xin Liu and Paul Conner, have also been immensely helpful.

Finally, Id like to thank Jason Gregory for his mentorship that dates back almost ten years. Without his guidance, I may have never ended up in the game industry, and almost certainly would never have ended up following in his footsteps and teaching at USC. He has taught me so much about games and teaching games over the years, and for that Im grateful.

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 Hawks Project 8, Lord of the Rings: Conquest