Tricks of the Windows video Game Programming---part1

Tricks of the Windows video Game ProgrammingPART I Windows Programming Foundations 71 Journey into the Abyss 9A Little History........................................................................................9Designing Games ..................................................... .............................13Types of Games ....................................................................................13Brainstorming........................................................................................14The Design Document and Storyboards................................................15Making the Game Fun ..........................................................................16The Components of a Game..................................................................16Section 1: Initialization....................................................................17Section 2: Enter Game Loop............................................................17Section 3: Retrieve Player Input ......................................................17Section 4: Perform AI and Game Logic ..........................................17Section 5: Render Next Frame ........................................................18Section 6: Synchronize Display ......................................................18Section 7: Loop................................................................................18Section 8: Shutdown ........................................................................18General Game Programming Guidelines ..............................................21Using Tools............................................................................................26C/C++ Compilers ............................................................................262D Art Software................................................................................26Sound Processing Software..............................................................263D Modelers ....................................................................................26Music and MIDI Sequencing Programs ..........................................27Setting Up to Get Down—Using the Compiler ....................................27An Example: FreakOut..........................................................................29Summary................................................................................................462 The Windows Programming Model 47The Genesis of Windows ......................................................................48Early Windows Versions ..................................................................48Windows 3.x ....................................................................................48Windows 95......................................................................................49Windows 98......................................................................................50Windows NT ....................................................................................50Basic Windows Architecture:Win9X/NT........................................50Multitasking and Multithreading ..........................................................51Getting Info on the Threads ............................................................52The Event Model..............................................................................530072313618 FM 10/26/99 9:32 AM Page viviTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS Programming the Microsoft Way: Hungarian Notation........................55Variable Naming ..............................................................................56Function Naming..............................................................................56Type and Constant Naming..............................................................57Class Naming....................................................................................57Parameter Naming............................................................................58The World’s Simplest Windows Program..............................................58It All Begins with WinMain() ..........................................................59Dissecting the Program....................................................................60Choosing a Message Box ................................................................63Real-World Windows Applications (Without Puck)..............................66The Windows Class ..............................................................................66Registering the Windows Class ............................................................74Creating the Window ............................................................................75The Event Handler ................................................................................77The Main Event Loop............................................................................84Making a Real-Time Event Loop..........................................................89Opening More Windows........................................................................90Summary................................................................................................933 Advanced Windows Programming 95Using Resources....................................................................................96Putting Your Resources Together ....................................................98Using Icon Resources ......................................................................99Using Cursor Resources ................................................................102Creating String Table Resources....................................................106Using Sound .WAV Resources ........................................................108Last, But Not Least—Using the Compiler to Create .RC Files ....114Working with Menus ..........................................................................116Creating a Menu ............................................................................116Loading a Menu..............................................................................119Responding to Menu Event Messages ..........................................122Introduction to GDI ............................................................................128The WM_PAINT Message Once Again ..............................................128Video Display Basics and Color....................................................133RGB and Palletized Modes............................................................135Basic Text Printing ........................................................................137Handling Important Events..................................................................143Window Manipulation....................................................................143Banging on the Keyboard ..............................................................150Squeezing the Mouse......................................................................158Sending Messages Yourself ................................................................161Summary..............................................................................................1630072313618 FM 10/26/99 9:32 AM Page viiviiCONTENTS4 Windows GDI, Controls, and Last-Minute Gift Ideas 165Advanced GDI Graphics......................................................................166Under the Hood with the Graphics Device Context......................166Color, Pens, and Brushes................................................................167Working with Pens ........................................................................168Painting with Brushes ....................................................................172Points, Lines, Polygons, and Circles ..................................................173Straight to the Point........................................................................173Getting a Line on Things................................................................175Getting Rectangular........................................................................177Round and Round She Goes—Circles ..........................................180Polygon, Polygon,Wherefore Art Thou, Polygon? ......................181More on Text and Fonts ......................................................................182Timing Is Everything ..........................................................................184The WM_TIMER Message ..................................................................184Low-Level Timing..........................................................................187Playing with Controls..........................................................................190Buttons............................................................................................191Sending Messages to Child Controls ............................................195Getting Information ............................................................................197The T3D Game Console......................................................................205Summary..............................................................................................210PART II DirectX and 2D Fundamentals 2115 DirectX Fundamentals and the Dreaded COM 213DirectX Primer ....................................................................................214The HEL and HAL ........................................................................216The DirectX Foundation Classes in Depth ....................................216COM: Is It the Work of Microsoft… or Demons?..............................218What Exactly Is a COM Object?....................................................219More on Interface IDs and GUIDs ................................................223Building a Quasi-COM Object ......................................................224A Quick Recap of COM ................................................................226A Working COM Program ............................................................226Working with DirectX COM Objects..................................................231COM and Function Pointers ..........................................................232Creating and Using DirectX Interfaces..........................................236Querying for Interfaces..................................................................237The Future of COM ............................................................................238Summary..............................................................................................2390072313618 FM 10/26/99 9:32 AM Page viiiviiiTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS 6 First Contact: DirectDraw 241The Interfaces of DirectDraw..............................................................242Interface Characteristics ................................................................242Using the Interfaces Together ........................................................244Creating a DirectDraw Object ............................................................245Error Handling with DirectDraw....................................................246Getting an Interface Lift ................................................................247Cooperating with Windows ................................................................250Getting into the Mode of Things ........................................................255The Subtleties of Color........................................................................259Building a Display Surface..................................................................263Creating a Primary Surface............................................................264Attaching the Palette......................................................................272Plotting Pixels ................................................................................272Cleaning Up....................................................................................284Summary..............................................................................................2857 Advanced DirectDraw and Bitmapped Graphics 287Working with High-Color Modes........................................................28816-Bit High-Color Mode................................................................289Getting the Pixel Format................................................................29024/32-Bit High-Color Mode ..........................................................299Double Buffering ................................................................................301Surface Dynamics................................................................................307Page Flipping ......................................................................................311Using the Blitter ..................................................................................317Using the Blitter for Memory Filling ............................................320Copying Bitmaps from Surface to Surface....................................328Clipper Fundamentals..........................................................................332Clipping Pixels to a Viewport ........................................................332Clipping Bitmaps the Hard Way....................................................334Making a DirectDraw Clip with IDirectDrawClipper..................339Working with Bitmaps ........................................................................345Loading .BMP files..........................................................................345Working with Bitmaps....................................................................352Loading an 8-Bit Bitmap................................................................353Loading a 16-Bit Bitmap................................................................354Loading a 24-Bit Bitmap................................................................355Last Word on Bitmaps....................................................................356Offscreen Surfaces ..............................................................................356Creating Offscreen Surfaces ..........................................................356Blitting Offscreen Surfaces............................................................358Setting Up the Blitter......................................................................359Color Keys......................................................................................360Source Color Keying......................................................................3610072313618 FM 10/26/99 9:32 AM Page ixixCONTENTSDestination Color Keying ..............................................................364Using the Blitter (Finally!) ............................................................365Bitmap Rotation and Scaling ..............................................................366Discrete Sampling Theory ..................................................................368Color Effects........................................................................................373Color Animation in 256-Color Modes ..........................................373Color Rotation in 256-Color Modes..............................................379Tricks with RGB Modes ................................................................381Manual Color Transforms and Lookup Tables....................................381The New DirectX Color and Gamma Controls Interface....................382Mixing GDI and DirectX ....................................................................383Getting the Lowdown on DirectDraw ................................................386The Main DirectDraw Object ........................................................386Surfing on Surfaces........................................................................388Playing with Palettes......................................................................389Using DirectDraw in Windowed Modes..............................................390Drawing Pixels in a Window..........................................................392Finding the Real Client Area (51)..................................................395Clipping a DirectX Window ..........................................................397Working with 8-Bit Windowed Modes..........................................398Summary..............................................................................................4008 Vector Rasterization and 2D Transformations 401Drawing Lines......................................................................................402Bresenham’s Algorithm..................................................................403Speeding Up the Algorithm............................................................409Basic 2D Clipping................................................................................411Computing the Intersection of Two Lines Using the Point Slope Form ..................................................................................413Computing the Intersection of Two Lines Using the General Form ........................................................................416Computing the Intersection of Two Lines Using the Matrix Form ..........................................................................416Clipping the Line............................................................................419The Cohen-Sutherland Algorithm..................................................420Wireframe Polygons............................................................................427Polygon Data Structures ................................................................428Drawing and Clipping Polygons....................................................430Transformations in the 2D Plane ........................................................432Translation......................................................................................433Rotation..........................................................................................435Scaling............................................................................................445Introduction to Matrices......................................................................446The Identity Matrix........................................................................448Matrix Addition..............................................................................4490072313618 FM 10/26/99 9:32 AM Page xxTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS Matrix Multiplication ....................................................................449Transformations Using Matrices....................................................452Translation ..........................................................................................454Scaling..................................................................................................455Rotation................................................................................................455Solid Filled Polygons ..........................................................................458Types of Triangles and Quadrilaterals............................................459Drawing Triangles and Quadrilaterals............................................461Triangular Deconstruction Details ................................................464The General Case of Rasterizing a Quadrilateral..........................472Triangulating Quads ......................................................................473Collision Detection with Polygons......................................................478Proximity AKA Bounding Sphere/Circle ......................................478Bounding Box ................................................................................481Point Containment..........................................................................484More on Timing and Synchronization ................................................486Scrolling and Panning..........................................................................488Page Scrolling Engines ..................................................................488Homogeneous Tile Engines............................................................489Sparse Bitmap Tile Engines ..........................................................494Fake 3D Isometric Engines..................................................................496Method 1: Cell-Based, Totally 2D ................................................496Method 2: Full-Screen-Based, with 2D or 3D Collision Networks......................................................................498Method 3: Using Full 3D Math, with a Fixed Camera View ........500The T3DLIB1 Library ........................................................................500The Engine Architecture ................................................................500Basic Definitions............................................................................501Working Macros ............................................................................502Data Types and Structures..............................................................503Global Domination ........................................................................506The DirectDraw Interface ..............................................................5072D Polygon Functions....................................................................5112D Graphic Primitives....................................................................513Math and Error Functions..............................................................517Bitmap Functions............................................................................519Palette Functions............................................................................522Utility Functions ............................................................................525The BOB (Blitter Object) Engine........................................................527Summary..............................................................................................5359 Uplinking with DirectInput and Force Feedback 537The Input Loop Revisited....................................................................538DirectInput Overture............................................................................539The Components of DirectInput ....................................................541The General Steps for Setting Up DirectInput ..............................5420072313618 FM 10/26/99 9:32 AM Page xixiCONTENTSData Acquisition Modes ................................................................544Creating the Main DirectInput Object............................................544The 101-Key Control Pad ..............................................................546Problem During Reading: Reacquisition........................................554Trapping the Mouse........................................................................556Working the Joystick......................................................................561Massaging Your Input ....................................................................576Going Deeper with Force Feedback....................................................579The Physics of Force Feedback......................................................580Setting Up Force Feedback............................................................580A Force Feedback Demo................................................................581Writing a Generalized Input System:T3DLIB2.CPP ............................582The T3D Library at a Glance ........................................................588Summary..............................................................................................58810 Sounding Off with DirectSound and DirectMusic 589Sound Programming on the PC ..........................................................589And Then There Was Sound…............................................................590Digital versus MIDI—Sounds Great, Less Filling..............................594Digital Sound—Let the Bits Begin................................................594Synthesized Sound and MIDI........................................................596It’s MIDI Time!..............................................................................597Sound Hardware..................................................................................598Wave Table Synthesis ....................................................................598Wave Guide Synthesis....................................................................598Digital Recording: Tools and Techniques............................................599Recording Sounds ..........................................................................600Processing Your Sounds ................................................................600DirectSound on the Mic ......................................................................601Starting Up DirectSound......................................................................602Understanding the Cooperation Level............................................604Setting the Cooperation Level........................................................605Primary and Secondary Sound Buffers ..............................................606Working with Secondary Buffers ..................................................606Creating Secondary Sound Buffers................................................607Writing Data to Secondary Buffers................................................610Rendering Sounds................................................................................612Playing a Sound..............................................................................612Stopping a Sound............................................................................612Controlling the Volume..................................................................612Freaking with the Frequency..........................................................613Panning in 3D ................................................................................614Making DirectSound Talk Back..........................................................614Reading Sounds from Disk..................................................................616The .WAV Format ............................................................................616Reading .WAV Files ........................................................................6170072313618 FM 10/26/99 9:32 AM Page xiixiiTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS DirectMusic: The Great Experiment ..................................................622DirectMusic Architecture ....................................................................622Starting Up DirectMusic......................................................................624Initializing COM............................................................................624Creating the Performance ..............................................................625Adding a Port to the Performance..................................................626Loading a MIDI Segment....................................................................626Creating the Loader........................................................................627Loading the MIDI File ..................................................................627Manipulating MIDI Segments ............................................................630Playing a MIDI Segment................................................................630Stopping a MIDI Segment..............................................................631Checking the Status of a MIDI Segment ......................................631Releasing a MIDI Segment............................................................631Shutting Down DirectMusic ..........................................................631A Little DirectMusic Example ......................................................632The T3DLIB3 Sound and Music Library ..............................................632The Header ....................................................................................633The Types ......................................................................................633Global Domination ........................................................................634The DirectSound API Wrapper......................................................635The DirectMusic API Rapper—Get It?..........................................640Summary..............................................................................................643PART III Hard Core Game Programming 64511 Algorithms, Data Structures, Memory Management, and Multithreading 647Data Structures ....................................................................................648Static Structures and Arrays ..........................................................648Linked Lists....................................................................................649Algorithmic Analysis ..........................................................................657Recursion ............................................................................................659Trees ....................................................................................................662Building BSTs................................................................................666Searching BSTs..............................................................................668Optimization Theory............................................................................671Using Your Head ............................................................................671Mathematical Tricks ......................................................................672Fixed-Point Math............................................................................673Unrolling the Loop ........................................................................677Look-Up Tables..............................................................................678Assembly Language ......................................................................679Making Demos ....................................................................................680Prerecorded Demos........................................................................680AI-Controlled Demos ....................................................................6820072313618 FM 10/26/99 9:32 AM Page xiiixiiiCONTENTSStrategies for Saving the Game ..........................................................682Implementing Multiple Players ..........................................................683Taking Turns ..................................................................................683Split-Screen Setups ........................................................................684Multithreaded Programming Techniques ............................................685Multithreaded Programming Terminology ....................................686Why Use Threads in a Game?........................................................687Conjuring a Thread from the Plasma Pool ....................................689Sending Messages from Thread to Thread ....................................697Waiting for the Right Moment ......................................................702Multithreading and DirectX ..........................................................709Advanced Multithreading ..............................................................711Summary..............................................................................................71112 Making Silicon Think with Artificial Intelligence 713Artificial Intelligence Primer ..............................................................714Deterministic AI Algorithms................................................................715Random Motion..............................................................................716Tracking Algorithms ......................................................................717Anti-Tracking: Evasion Algorithms ..............................................722Patterns and Basic Control Scripting ..................................................722Basic Patterns ................................................................................723Patterns with Conditional Logic Processing..................................727Modeling Behavioral State Systems....................................................729Elementary State Machines............................................................730Adding More Robust Behaviors with Personality..........................734Modeling Memory and Learning with Software ................................736Planning and Decision Trees ..............................................................740Coding Plans ..................................................................................742Implementing a Real Planner ........................................................745Pathfinding ..........................................................................................747Trial and Error................................................................................748Contour Tracing..............................................................................749Collision Avoidance Tracks............................................................749Waypoint Pathfinding ....................................................................750A Racing Example..........................................................................753Robust Pathfinding ........................................................................754Advanced AI Scripting ........................................................................759Designing the Scripting Language ................................................759Using the C/C++ Compiler............................................................762Artificial Neural Networks..................................................................767Genetic Algorithms..............................................................................770Fuzzy Logic ........................................................................................772Normal Set Theory ........................................................................773Fuzzy Set Theory............................................................................7740072313618 FM 10/26/99 9:32 AM Page xivxivTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS Fuzzy Linguistic Variables and Rules............................................776Fuzzy Manifolds and Membership ................................................779Fuzzy Associative Matrices............................................................783Processing the FAM with the Fuzzified Inputs..............................787Warm and Fuzzy ............................................................................794Building Real AI for Games................................................................794Summary..............................................................................................79513 Playing God: Basic Physics Modeling 797Fundamental Laws of Physics ............................................................798Mass (m) ........................................................................................799Time (t) ..........................................................................................799Position (s)......................................................................................800Velocity (v) ....................................................................................802Acceleration (a)..............................................................................804Force (F) ........................................................................................807Forces in Higher Dimensions ........................................................808Momentum (P)................................................................................809The Physics of Linear Momentum: Conservation and Transfer ........810Modeling Gravity Effects....................................................................813Modeling a Gravity Well................................................................815Modeling Projectile Trajectories....................................................818The Evil Head of Friction....................................................................821Basic Friction Concepts..................................................................821Friction on an Inclined Plane (Advanced) ....................................823Basic Ad Hoc Collision Response ......................................................828Simple x,y Bounce Physics............................................................828Computing the Collision Response with Planes of Any Orientation ..........................................................................830An Example of Vector Reflection..................................................834Intersection of Line Segments........................................................835Real 2D Object-to-Object Collision Response (Advanced)................841Resolving the n-t Coordinate System..................................................846Simple Kinematics ..............................................................................853Solving the Forward Kinematic Problem ......................................854Solving the Inverse Kinematic Problem ........................................858Particle Systems ..................................................................................859What Every Particle Needs ............................................................859Designing a Particle Engine ..........................................................860The Particle Engine Software ........................................................861Generating the Initial Conditions ..................................................866Putting the Particle System Together ............................................869Playing God: Constructing Physics Models for Games......................870Data Structures for Physics Modeling............................................870Frame-Based Versus Time-Based Modeling..................................871Summary..............................................................................................8730072313618 FM 10/26/99 9:32 AM Page xvxvCONTENTS14 Putting It All Together: You Got Game! 875The Initial Design of Outpost..............................................................876The Story........................................................................................876Designing the Gameplay................................................................877The Tools Used to Write the Game ....................................................877The Game Universe: Scrolling in Space..............................................878The Player’s Ship: “The Wraith” ........................................................880The Asteroid Field ..............................................................................882The Enemies........................................................................................884The Outposts ..................................................................................885The Predator Mines........................................................................886The Gunships..................................................................................888The Power-Ups....................................................................................891The HUDS ..........................................................................................892The Particle System ............................................................................896Playing the Game ................................................................................896Compiling Outpost ..............................................................................897Compilation Files ..........................................................................897Runtime Files..................................................................................898Epilogue ..............................................................................................898PART IV Appendixes 901A What’s on the CD 903B Installing DirectX and Using the C/C++ Compiler 907Using the C/C++ Compiler..................................................................908C Math and Trigonometry Review 911Trigonometry ......................................................................................911Vectors..................................................................................................915Vector Length ................................................................................916Normalization ................................................................................917Scalar Multiplication......................................................................917Vector Addition ..............................................................................918Vector Subtraction..........................................................................919The Inner Product, or the “Dot” Product ......................................919The Cross Product..........................................................................921The Zero Vector..............................................................................923Position Vectors..............................................................................923Vectors as Linear Combinations ....................................................9240072313618 FM 10/26/99 9:32 AM Page xvixviTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS D C++ Primer 925What Is C++? ......................................................................................925The Minimum You Need to Know About C++ ..................................928New Types, Keywords, and Conventions............................................929Comments ......................................................................................929Constants........................................................................................929Referential Variables ......................................................................929Creating Variables On-the-Fly........................................................930Memory Management..........................................................................931Stream I/O............................................................................................932Classes..................................................................................................934The New Struct in Town ................................................................934Just a Simple Class ........................................................................935Public Versus Private......................................................................936Class Member Functions (A.K.A. Methods) ................................937Constructors and Destructors ........................................................938Writing a Constructor ....................................................................939Writing a Destructor ......................................................................941The Scope Resolution Operator ..........................................................943Function and Operator Overloading....................................................945Summary..............................................................................................947E Game Programming Resources 949Game Programming Sites....................................................................949Download Points..................................................................................9502D/3D Engines ....................................................................................950Game Programming Books..................................................................951Microsoft DirectX Multimedia Exposition..........................................951Usenet Newsgroups ............................................................................951Keeping Up with the Industry: Blues News........................................952Game Development Magazines ..........................................................952Game Web Site Developers ................................................................953Xtreme Games LLC ............................................................................953F ASCII Tables 955Index 961 .............................13Types of Games ....................................................................................13Brainstorming........................................................................................14The Design Document and Storyboards................................................15Making the Game Fun ..........................................................................16The Components of a Game..................................................................16Section 1: Initialization....................................................................17Section 2: Enter Game Loop............................................................17Section 3: Retrieve Player Input ......................................................17Section 4: Perform AI and Game Logic ..........................................17Section 5: Render Next Frame ........................................................18Section 6: Synchronize Display ......................................................18Section 7: Loop................................................................................18Section 8: Shutdown ........................................................................18General Game Programming Guidelines ..............................................21Using Tools............................................................................................26C/C++ Compilers ............................................................................262D Art Software................................................................................26Sound Processing Software..............................................................263D Modelers ....................................................................................26Music and MIDI Sequencing Programs ..........................................27Setting Up to Get Down—Using the Compiler ....................................27An Example: FreakOut..........................................................................29Summary................................................................................................462 The Windows Programming Model 47The Genesis of Windows ......................................................................48Early Windows Versions ..................................................................48Windows 3.x ....................................................................................48Windows 95......................................................................................49Windows 98......................................................................................50Windows NT ....................................................................................50Basic Windows Architecture:Win9X/NT........................................50Multitasking and Multithreading ..........................................................51Getting Info on the Threads ............................................................52The Event Model..............................................................................530072313618 FM 10/26/99 9:32 AM Page viviTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS Programming the Microsoft Way: Hungarian Notation........................55Variable Naming ..............................................................................56Function Naming..............................................................................56Type and Constant Naming..............................................................57Class Naming....................................................................................57Parameter Naming............................................................................58The World’s Simplest Windows Program..............................................58It All Begins with WinMain() ..........................................................59Dissecting the Program....................................................................60Choosing a Message Box ................................................................63Real-World Windows Applications (Without Puck)..............................66The Windows Class ..............................................................................66Registering the Windows Class ............................................................74Creating the Window ............................................................................75The Event Handler ................................................................................77The Main Event Loop............................................................................84Making a Real-Time Event Loop..........................................................89Opening More Windows........................................................................90Summary................................................................................................933 Advanced Windows Programming 95Using Resources....................................................................................96Putting Your Resources Together ....................................................98Using Icon Resources ......................................................................99Using Cursor Resources ................................................................102Creating String Table Resources....................................................106Using Sound .WAV Resources ........................................................108Last, But Not Least—Using the Compiler to Create .RC Files ....114Working with Menus ..........................................................................116Creating a Menu ............................................................................116Loading a Menu..............................................................................119Responding to Menu Event Messages ..........................................122Introduction to GDI ............................................................................128The WM_PAINT Message Once Again ..............................................128Video Display Basics and Color....................................................133RGB and Palletized Modes............................................................135Basic Text Printing ........................................................................137Handling Important Events..................................................................143Window Manipulation....................................................................143Banging on the Keyboard ..............................................................150Squeezing the Mouse......................................................................158Sending Messages Yourself ................................................................161Summary..............................................................................................1630072313618 FM 10/26/99 9:32 AM Page viiviiCONTENTS4 Windows GDI, Controls, and Last-Minute Gift Ideas 165Advanced GDI Graphics......................................................................166Under the Hood with the Graphics Device Context......................166Color, Pens, and Brushes................................................................167Working with Pens ........................................................................168Painting with Brushes ....................................................................172Points, Lines, Polygons, and Circles ..................................................173Straight to the Point........................................................................173Getting a Line on Things................................................................175Getting Rectangular........................................................................177Round and Round She Goes—Circles ..........................................180Polygon, Polygon,Wherefore Art Thou, Polygon? ......................181More on Text and Fonts ......................................................................182Timing Is Everything ..........................................................................184The WM_TIMER Message ..................................................................184Low-Level Timing..........................................................................187Playing with Controls..........................................................................190Buttons............................................................................................191Sending Messages to Child Controls ............................................195Getting Information ............................................................................197The T3D Game Console......................................................................205Summary..............................................................................................210PART II DirectX and 2D Fundamentals 2115 DirectX Fundamentals and the Dreaded COM 213DirectX Primer ....................................................................................214The HEL and HAL ........................................................................216The DirectX Foundation Classes in Depth ....................................216COM: Is It the Work of Microsoft… or Demons?..............................218What Exactly Is a COM Object?....................................................219More on Interface IDs and GUIDs ................................................223Building a Quasi-COM Object ......................................................224A Quick Recap of COM ................................................................226A Working COM Program ............................................................226Working with DirectX COM Objects..................................................231COM and Function Pointers ..........................................................232Creating and Using DirectX Interfaces..........................................236Querying for Interfaces..................................................................237The Future of COM ............................................................................238Summary..............................................................................................2390072313618 FM 10/26/99 9:32 AM Page viiiviiiTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS 6 First Contact: DirectDraw 241The Interfaces of DirectDraw..............................................................242Interface Characteristics ................................................................242Using the Interfaces Together ........................................................244Creating a DirectDraw Object ............................................................245Error Handling with DirectDraw....................................................246Getting an Interface Lift ................................................................247Cooperating with Windows ................................................................250Getting into the Mode of Things ........................................................255The Subtleties of Color........................................................................259Building a Display Surface..................................................................263Creating a Primary Surface............................................................264Attaching the Palette......................................................................272Plotting Pixels ................................................................................272Cleaning Up....................................................................................284Summary..............................................................................................2857 Advanced DirectDraw and Bitmapped Graphics 287Working with High-Color Modes........................................................28816-Bit High-Color Mode................................................................289Getting the Pixel Format................................................................29024/32-Bit High-Color Mode ..........................................................299Double Buffering ................................................................................301Surface Dynamics................................................................................307Page Flipping ......................................................................................311Using the Blitter ..................................................................................317Using the Blitter for Memory Filling ............................................320Copying Bitmaps from Surface to Surface....................................328Clipper Fundamentals..........................................................................332Clipping Pixels to a Viewport ........................................................332Clipping Bitmaps the Hard Way....................................................334Making a DirectDraw Clip with IDirectDrawClipper..................339Working with Bitmaps ........................................................................345Loading .BMP files..........................................................................345Working with Bitmaps....................................................................352Loading an 8-Bit Bitmap................................................................353Loading a 16-Bit Bitmap................................................................354Loading a 24-Bit Bitmap................................................................355Last Word on Bitmaps....................................................................356Offscreen Surfaces ..............................................................................356Creating Offscreen Surfaces ..........................................................356Blitting Offscreen Surfaces............................................................358Setting Up the Blitter......................................................................359Color Keys......................................................................................360Source Color Keying......................................................................3610072313618 FM 10/26/99 9:32 AM Page ixixCONTENTSDestination Color Keying ..............................................................364Using the Blitter (Finally!) ............................................................365Bitmap Rotation and Scaling ..............................................................366Discrete Sampling Theory ..................................................................368Color Effects........................................................................................373Color Animation in 256-Color Modes ..........................................373Color Rotation in 256-Color Modes..............................................379Tricks with RGB Modes ................................................................381Manual Color Transforms and Lookup Tables....................................381The New DirectX Color and Gamma Controls Interface....................382Mixing GDI and DirectX ....................................................................383Getting the Lowdown on DirectDraw ................................................386The Main DirectDraw Object ........................................................386Surfing on Surfaces........................................................................388Playing with Palettes......................................................................389Using DirectDraw in Windowed Modes..............................................390Drawing Pixels in a Window..........................................................392Finding the Real Client Area (51)..................................................395Clipping a DirectX Window ..........................................................397Working with 8-Bit Windowed Modes..........................................398Summary..............................................................................................4008 Vector Rasterization and 2D Transformations 401Drawing Lines......................................................................................402Bresenham’s Algorithm..................................................................403Speeding Up the Algorithm............................................................409Basic 2D Clipping................................................................................411Computing the Intersection of Two Lines Using the Point Slope Form ..................................................................................413Computing the Intersection of Two Lines Using the General Form ........................................................................416Computing the Intersection of Two Lines Using the Matrix Form ..........................................................................416Clipping the Line............................................................................419The Cohen-Sutherland Algorithm..................................................420Wireframe Polygons............................................................................427Polygon Data Structures ................................................................428Drawing and Clipping Polygons....................................................430Transformations in the 2D Plane ........................................................432Translation......................................................................................433Rotation..........................................................................................435Scaling............................................................................................445Introduction to Matrices......................................................................446The Identity Matrix........................................................................448Matrix Addition..............................................................................4490072313618 FM 10/26/99 9:32 AM Page xxTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS Matrix Multiplication ....................................................................449Transformations Using Matrices....................................................452Translation ..........................................................................................454Scaling..................................................................................................455Rotation................................................................................................455Solid Filled Polygons ..........................................................................458Types of Triangles and Quadrilaterals............................................459Drawing Triangles and Quadrilaterals............................................461Triangular Deconstruction Details ................................................464The General Case of Rasterizing a Quadrilateral..........................472Triangulating Quads ......................................................................473Collision Detection with Polygons......................................................478Proximity AKA Bounding Sphere/Circle ......................................478Bounding Box ................................................................................481Point Containment..........................................................................484More on Timing and Synchronization ................................................486Scrolling and Panning..........................................................................488Page Scrolling Engines ..................................................................488Homogeneous Tile Engines............................................................489Sparse Bitmap Tile Engines ..........................................................494Fake 3D Isometric Engines..................................................................496Method 1: Cell-Based, Totally 2D ................................................496Method 2: Full-Screen-Based, with 2D or 3D Collision Networks......................................................................498Method 3: Using Full 3D Math, with a Fixed Camera View ........500The T3DLIB1 Library ........................................................................500The Engine Architecture ................................................................500Basic Definitions............................................................................501Working Macros ............................................................................502Data Types and Structures..............................................................503Global Domination ........................................................................506The DirectDraw Interface ..............................................................5072D Polygon Functions....................................................................5112D Graphic Primitives....................................................................513Math and Error Functions..............................................................517Bitmap Functions............................................................................519Palette Functions............................................................................522Utility Functions ............................................................................525The BOB (Blitter Object) Engine........................................................527Summary..............................................................................................5359 Uplinking with DirectInput and Force Feedback 537The Input Loop Revisited....................................................................538DirectInput Overture............................................................................539The Components of DirectInput ....................................................541The General Steps for Setting Up DirectInput ..............................5420072313618 FM 10/26/99 9:32 AM Page xixiCONTENTSData Acquisition Modes ................................................................544Creating the Main DirectInput Object............................................544The 101-Key Control Pad ..............................................................546Problem During Reading: Reacquisition........................................554Trapping the Mouse........................................................................556Working the Joystick......................................................................561Massaging Your Input ....................................................................576Going Deeper with Force Feedback....................................................579The Physics of Force Feedback......................................................580Setting Up Force Feedback............................................................580A Force Feedback Demo................................................................581Writing a Generalized Input System:T3DLIB2.CPP ............................582The T3D Library at a Glance ........................................................588Summary..............................................................................................58810 Sounding Off with DirectSound and DirectMusic 589Sound Programming on the PC ..........................................................589And Then There Was Sound…............................................................590Digital versus MIDI—Sounds Great, Less Filling..............................594Digital Sound—Let the Bits Begin................................................594Synthesized Sound and MIDI........................................................596It’s MIDI Time!..............................................................................597Sound Hardware..................................................................................598Wave Table Synthesis ....................................................................598Wave Guide Synthesis....................................................................598Digital Recording: Tools and Techniques............................................599Recording Sounds ..........................................................................600Processing Your Sounds ................................................................600DirectSound on the Mic ......................................................................601Starting Up DirectSound......................................................................602Understanding the Cooperation Level............................................604Setting the Cooperation Level........................................................605Primary and Secondary Sound Buffers ..............................................606Working with Secondary Buffers ..................................................606Creating Secondary Sound Buffers................................................607Writing Data to Secondary Buffers................................................610Rendering Sounds................................................................................612Playing a Sound..............................................................................612Stopping a Sound............................................................................612Controlling the Volume..................................................................612Freaking with the Frequency..........................................................613Panning in 3D ................................................................................614Making DirectSound Talk Back..........................................................614Reading Sounds from Disk..................................................................616The .WAV Format ............................................................................616Reading .WAV Files ........................................................................6170072313618 FM 10/26/99 9:32 AM Page xiixiiTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS DirectMusic: The Great Experiment ..................................................622DirectMusic Architecture ....................................................................622Starting Up DirectMusic......................................................................624Initializing COM............................................................................624Creating the Performance ..............................................................625Adding a Port to the Performance..................................................626Loading a MIDI Segment....................................................................626Creating the Loader........................................................................627Loading the MIDI File ..................................................................627Manipulating MIDI Segments ............................................................630Playing a MIDI Segment................................................................630Stopping a MIDI Segment..............................................................631Checking the Status of a MIDI Segment ......................................631Releasing a MIDI Segment............................................................631Shutting Down DirectMusic ..........................................................631A Little DirectMusic Example ......................................................632The T3DLIB3 Sound and Music Library ..............................................632The Header ....................................................................................633The Types ......................................................................................633Global Domination ........................................................................634The DirectSound API Wrapper......................................................635The DirectMusic API Rapper—Get It?..........................................640Summary..............................................................................................643PART III Hard Core Game Programming 64511 Algorithms, Data Structures, Memory Management, and Multithreading 647Data Structures ....................................................................................648Static Structures and Arrays ..........................................................648Linked Lists....................................................................................649Algorithmic Analysis ..........................................................................657Recursion ............................................................................................659Trees ....................................................................................................662Building BSTs................................................................................666Searching BSTs..............................................................................668Optimization Theory............................................................................671Using Your Head ............................................................................671Mathematical Tricks ......................................................................672Fixed-Point Math............................................................................673Unrolling the Loop ........................................................................677Look-Up Tables..............................................................................678Assembly Language ......................................................................679Making Demos ....................................................................................680Prerecorded Demos........................................................................680AI-Controlled Demos ....................................................................6820072313618 FM 10/26/99 9:32 AM Page xiiixiiiCONTENTSStrategies for Saving the Game ..........................................................682Implementing Multiple Players ..........................................................683Taking Turns ..................................................................................683Split-Screen Setups ........................................................................684Multithreaded Programming Techniques ............................................685Multithreaded Programming Terminology ....................................686Why Use Threads in a Game?........................................................687Conjuring a Thread from the Plasma Pool ....................................689Sending Messages from Thread to Thread ....................................697Waiting for the Right Moment ......................................................702Multithreading and DirectX ..........................................................709Advanced Multithreading ..............................................................711Summary..............................................................................................71112 Making Silicon Think with Artificial Intelligence 713Artificial Intelligence Primer ..............................................................714Deterministic AI Algorithms................................................................715Random Motion..............................................................................716Tracking Algorithms ......................................................................717Anti-Tracking: Evasion Algorithms ..............................................722Patterns and Basic Control Scripting ..................................................722Basic Patterns ................................................................................723Patterns with Conditional Logic Processing..................................727Modeling Behavioral State Systems....................................................729Elementary State Machines............................................................730Adding More Robust Behaviors with Personality..........................734Modeling Memory and Learning with Software ................................736Planning and Decision Trees ..............................................................740Coding Plans ..................................................................................742Implementing a Real Planner ........................................................745Pathfinding ..........................................................................................747Trial and Error................................................................................748Contour Tracing..............................................................................749Collision Avoidance Tracks............................................................749Waypoint Pathfinding ....................................................................750A Racing Example..........................................................................753Robust Pathfinding ........................................................................754Advanced AI Scripting ........................................................................759Designing the Scripting Language ................................................759Using the C/C++ Compiler............................................................762Artificial Neural Networks..................................................................767Genetic Algorithms..............................................................................770Fuzzy Logic ........................................................................................772Normal Set Theory ........................................................................773Fuzzy Set Theory............................................................................7740072313618 FM 10/26/99 9:32 AM Page xivxivTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS Fuzzy Linguistic Variables and Rules............................................776Fuzzy Manifolds and Membership ................................................779Fuzzy Associative Matrices............................................................783Processing the FAM with the Fuzzified Inputs..............................787Warm and Fuzzy ............................................................................794Building Real AI for Games................................................................794Summary..............................................................................................79513 Playing God: Basic Physics Modeling 797Fundamental Laws of Physics ............................................................798Mass (m) ........................................................................................799Time (t) ..........................................................................................799Position (s)......................................................................................800Velocity (v) ....................................................................................802Acceleration (a)..............................................................................804Force (F) ........................................................................................807Forces in Higher Dimensions ........................................................808Momentum (P)................................................................................809The Physics of Linear Momentum: Conservation and Transfer ........810Modeling Gravity Effects....................................................................813Modeling a Gravity Well................................................................815Modeling Projectile Trajectories....................................................818The Evil Head of Friction....................................................................821Basic Friction Concepts..................................................................821Friction on an Inclined Plane (Advanced) ....................................823Basic Ad Hoc Collision Response ......................................................828Simple x,y Bounce Physics............................................................828Computing the Collision Response with Planes of Any Orientation ..........................................................................830An Example of Vector Reflection..................................................834Intersection of Line Segments........................................................835Real 2D Object-to-Object Collision Response (Advanced)................841Resolving the n-t Coordinate System..................................................846Simple Kinematics ..............................................................................853Solving the Forward Kinematic Problem ......................................854Solving the Inverse Kinematic Problem ........................................858Particle Systems ..................................................................................859What Every Particle Needs ............................................................859Designing a Particle Engine ..........................................................860The Particle Engine Software ........................................................861Generating the Initial Conditions ..................................................866Putting the Particle System Together ............................................869Playing God: Constructing Physics Models for Games......................870Data Structures for Physics Modeling............................................870Frame-Based Versus Time-Based Modeling..................................871Summary..............................................................................................8730072313618 FM 10/26/99 9:32 AM Page xvxvCONTENTS14 Putting It All Together: You Got Game! 875The Initial Design of Outpost..............................................................876The Story........................................................................................876Designing the Gameplay................................................................877The Tools Used to Write the Game ....................................................877The Game Universe: Scrolling in Space..............................................878The Player’s Ship: “The Wraith” ........................................................880The Asteroid Field ..............................................................................882The Enemies........................................................................................884The Outposts ..................................................................................885The Predator Mines........................................................................886The Gunships..................................................................................888The Power-Ups....................................................................................891The HUDS ..........................................................................................892The Particle System ............................................................................896Playing the Game ................................................................................896Compiling Outpost ..............................................................................897Compilation Files ..........................................................................897Runtime Files..................................................................................898Epilogue ..............................................................................................898PART IV Appendixes 901A What’s on the CD 903B Installing DirectX and Using the C/C++ Compiler 907Using the C/C++ Compiler..................................................................908C Math and Trigonometry Review 911Trigonometry ......................................................................................911Vectors..................................................................................................915Vector Length ................................................................................916Normalization ................................................................................917Scalar Multiplication......................................................................917Vector Addition ..............................................................................918Vector Subtraction..........................................................................919The Inner Product, or the “Dot” Product ......................................919The Cross Product..........................................................................921The Zero Vector..............................................................................923Position Vectors..............................................................................923Vectors as Linear Combinations ....................................................9240072313618 FM 10/26/99 9:32 AM Page xvixviTRICKS OF THE WINDOWS GAME PROGRAMMING GURUS D C++ Primer 925What Is C++? ......................................................................................925The Minimum You Need to Know About C++ ..................................928New Types, Keywords, and Conventions............................................929Comments ......................................................................................929Constants........................................................................................929Referential Variables ......................................................................929Creating Variables On-the-Fly........................................................930Memory Management..........................................................................931Stream I/O............................................................................................932Classes..................................................................................................934The New Struct in Town ................................................................934Just a Simple Class ........................................................................935Public Versus Private......................................................................936Class Member Functions (A.K.A. Methods) ................................937Constructors and Destructors ........................................................938Writing a Constructor ....................................................................939Writing a Destructor ......................................................................941The Scope Resolution Operator ..........................................................943Function and Operator Overloading....................................................945Summary..............................................................................................947E Game Programming Resources 949Game Programming Sites....................................................................949Download Points..................................................................................9502D/3D Engines ....................................................................................950Game Programming Books..................................................................951Microsoft DirectX Multimedia Exposition..........................................951Usenet Newsgroups ............................................................................951Keeping Up with the Industry: Blues News........................................952Game Development Magazines ..........................................................952Game Web Site Developers ................................................................953Xtreme Games LLC ............................................................................953F ASCII Tables 955Index 961