Transcription
Game ProgrammingAlgorithms andTechniques
This page intentionally left blank
Game ProgrammingAlgorithms andTechniquesA Platform-Agnostic ApproachSanjay MadhavUpper Saddle River, NJ Boston Indianapolis San FranciscoNew York Toronto Montreal London Munich Paris MadridCapetown Sydney Tokyo Singapore Mexico City
Many of the designations used by manufacturers and sellers to distinguish theirproducts are claimed as trademarks. Where those designations appear in this book,and the publisher was aware of a trademark claim, the designations have beenprinted with initial capital letters or in all capitals.The author and publisher have taken care in the preparation of this book, but makeno expressed or implied warranty of any kind and assume no responsibility for errorsor omissions. No liability is assumed for incidental or consequential damages inconnection with or arising out of the use of the information or programs containedherein.For information about buying this title in bulk quantities, or for special salesopportunities (which may include electronic versions; custom cover designs; andcontent particular to your business, training goals, marketing focus, or brandinginterests), please contact our corporate sales department at corpsales@pearsoned.com or (800) 382-3419.For government sales inquiries, please contact governmentsales@pearsoned.com.For questions about sales outside the U.S., please contact international@pearsoned.com.Visit us on the Web: informit.com/awLibrary of Congress Control Number: 2013950628Copyright 2014 Pearson Education, Inc.All rights reserved. Printed in the United States of America. This publication isprotected by copyright, and permission must be obtained from the publisher priorto any prohibited reproduction, storage in a retrieval system, or transmission in anyform or by any means, electronic, mechanical, photocopying, recording, or likewise.To obtain permission to use material from this work, please submit a written requestto Pearson Education, Inc., Permissions Department, One Lake Street, Upper SaddleRiver, New Jersey 07458, or you may fax your request to (201) 236-3290.Screenshot from Jetpack Joyride 2011 Halfbrick Studios. Used with permission.Editor-in-ChiefMark TaubExecutive EditorLaura LewinDevelopment EditorChris ZahnManaging EditorKristy HartProject EditorElaine WileyCopy EditorBart ReedIndexerWordWise Publishing ServicesProofreaderJess DeGabrieleTechnical ReviewersAlexander BoczarDustin DarcyJeff WoffordEditorial AssistantOlivia BasegioCover DesignerChuti PrasersithScreenshot from Jazz Jackrabbit 2 1998 Epic Games, Inc. Used with permission.CompositorNonie RatcliffScreenshot from Quadrilateral Cowboy 2013 Blendo Games LLC. Used withpermission.GraphicsLaura RobbinsScreenshot 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 withpermission from Microsoft.Image in Figure 2-10 courtesy of denis pc/fotolia.Images in Figures 4-4, 8-5, and 8-6 courtesy of York/fotolia.ISBN-13: 978-0-321-94015-5ISBN-10: 0-321-94015-6Text printed in the United States on recycled paper at R.R. Donnelley inCrawfordsville, IN. First printing: December 2013
To my family for supporting me and to all my studentsfor not driving me crazy (yet).
This page intentionally left blank
ContentsPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1Game Programming Overview . . . . . . . . . . . . . . . . .1Evolution of Video Game Programming . . . . . . . . . . . . . . . . 2The Game Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Time and Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9Game Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . 1622D Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192D Rendering Foundations. . . . . . . . . . . . . . . . . . . . . . . . 20Sprites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22Scrolling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Tile Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . 393Linear Algebra for Games . . . . . . . . . . . . . . . . . . . 41Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
viiiCONTENTS43D Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66Coordinate Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67Lighting and Shading . . . . . . . . . . . . . . . . . . . . . . . . . . . 76Visibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85World Transform, Revisited. . . . . . . . . . . . . . . . . . . . . . . . 88Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . . 925Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93Input Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94Event-Based Input Systems. . . . . . . . . . . . . . . . . . . . . . . . 99Mobile Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 1096Sound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111Basic Sound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1123D Sound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .115Digital Signal Processing . . . . . . . . . . . . . . . . . . . . . . . . .119Other Sound Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . 122Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 1257Physics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127Planes, Rays, and Line Segments . . . . . . . . . . . . . . . . . . . 128Collision Geometry. . . . . . . . . . . . . . . . . . . . . . . . . . . . 130Collision Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134Physics-Based Movement. . . . . . . . . . . . . . . . . . . . . . . . 148
CONTENTSPhysics Middleware . . . . . . . . . . . . . . . . . . . . . . . . . . . 153Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 1558Cameras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157Types of Cameras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158Perspective Projections . . . . . . . . . . . . . . . . . . . . . . . . . 161Camera Implementations. . . . . . . . . . . . . . . . . . . . . . . . 164Camera Support Algorithms . . . . . . . . . . . . . . . . . . . . . . 175Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 1789Artificial Intelligence . . . . . . . . . . . . . . . . . . . . . 179“Real” AI versus Game AI . . . . . . . . . . . . . . . . . . . . . . . . 180Pathfinding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180State-Based Behaviors. . . . . . . . . . . . . . . . . . . . . . . . . . 192Strategy and Planning . . . . . . . . . . . . . . . . . . . . . . . . . . 198Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 20210User Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . 203Menu Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204HUD Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207Other UI Considerations. . . . . . . . . . . . . . . . . . . . . . . . . 217Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 222ix
xCONTENTS11Scripting Languages and Data Formats . . . . . . . . . 223Scripting Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 224Implementing a Scripting Language. . . . . . . . . . . . . . . . . 229Data Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235Case Study: UI Mods in Worldof Warcraft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 24212Networked Games. . . . . . . . . . . . . . . . . . . . . . . 243Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244Network Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250Cheating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257Review Questions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257Additional References . . . . . . . . . . . . . . . . . . . . . . . . . . 25813Sample Game: Side-Scroller for iOS . . . . . . . . . . . . 259Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260Code Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26814Sample Game: Tower Defense for PC/Mac . . . . . . . . 269Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270Code Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285AAnswers to Review Questions. . . . . . . . . . . . . . . . 287Chapter 1: Game Programming Overview . . . . . . . . . . . . . 288Chapter 2: 2D Graphics . . . . . . . . . . . . . . . . . . . . . . . . . 289
CONTENTSChapter 3: Linear Algebra for Games. . . . . . . . . . . . . . . . . 290Chapter 4: 3D Graphics . . . . . . . . . . . . . . . . . . . . . . . . . 291Chapter 5: Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292Chapter 6: Sound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294Chapter 7: Physics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295Chapter 8: Cameras. . . . . . . . . . . . . . . . . . . . . . . . . . . . 295Chapter 9: Artificial Intelligence. . . . . . . . . . . . . . . . . . . . 296Chapter 10: User Interfaces . . . . . . . . . . . . . . . . . . . . . . . 298Chapter 11: Scripting Languages and Data Formats . . . . . . . 299Chapter 12: Networked Games . . . . . . . . . . . . . . . . . . . . 300BUseful Tools for Programmers . . . . . . . . . . . . . . . 303Debugger. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304Source Control. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309Diff and Merging Tools . . . . . . . . . . . . . . . . . . . . . . . . . 312Issue Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315xi
ACKNOWLEDGMENTSEven though my name might be the only one on the cover, this book simply would not havebeen possible without the help and support of many other individuals. I’d first like to thankmy mom and dad for their support throughout the years as I pursued my education and thencareer. I’d also like to thank my sister Nita for going along with all the crazy and creative thingswe 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. Itstarts with Laura Lewin, my executive editor, who has backed the premise of the book since dayone. She and assistant editor Olivia Basegio have provided very useful guidance throughout thewriting 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 rev
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 creat- ing video games. The hope was that with this solid .
