Core Techniques and

Algorithms in Game
Programming

Daniel Sanchez-Crespo Dalmau

800 E. 96th Street, Indianapolis, Indiana 46240

An Imprint of Pearson Education
Boston • Indianapolis • London • Munich <• New York • San Francisco
i Core Techniques, and Algorithms in Game Programming

Table of Contents

Introduction xxv

Parti Gameplay Programming

Chapter 1 A Chronology of Game Programming 1

Phase I: Before Spacewar 1
Phase II: Spacewar to Atari 5
Phase III: Game Consoles and Personal Computers 8
Game Consoles and Game Developers 8
Personal Computers 11
Phase IV: Shakedown and Consolidation 13
Phase V: The Advent of the Game Engine 16
Phase VI: The Handheld Revolution 22
Phase VII: The Cellular Phenomenon 24
Phase VIII: Multiplayer Games 25
In Closing 27

Chapter 2 Game Architecture 29

Real-Time Software 29
Real-Time Loops 31"
i The Game Logic Section \ 37
Player Update 37
World Update 39
The Presentation Section 42
World Rendering 43
NPC Rendering 44
The Player 45
Caveat: Networked Games 47
The Programming Process 48
Stages 48
In Closing 60
 Table of Contents ~ vii

Chapter 3 Data Structures and Algorithms 61

Types, Structures, and Classes 61
Data Structures 64
Static Arrays 64
Linked Lists 67
Doubly-Linked Lists 68
Queues 69
Stacks 70
Deques 71
Tables 72
Trees 77
Priority Queues 84
Graphs 85
The Standard Template Library 88
Containers 90
Iterators 95
In Closing 96

Chapter 4 Design Patterns 97

Design Patterns Defined 98
Some Useful Programming Patterns 99
Singleton 99
Strategy 100
Factory 103
Spatial Index 106
Composite 111
Flyweight 115
Usability Patterns 117
Shield 117
State 118
Automatic Mode Cancellation 118
Magnetism 119
Focus 119
Progress 120
In Closing 120

Chapter 5 User Input 121

The Keyboard 121
Keyboard with Directlnput 124
viii Core Techniques and Algorithms in Game Programming

Mouse 130
Mouselook 132
Joysticks 134
Response Curves 138
Hardware Abstraction 141
Force Feedback 144
In Closing 147

Chapter 6 Fundamental Al Technologies 149

Context 150
Structure of an Al System 151
Sensing the World 152
Memory 153
Analysis/Reasoning Core 154
Action/Output System 154
Specific Technologies 155
Finite State Machines 155
Rule Systems 169
Planning and Problem Solving 180
Biology-Inspired Al 183
In Closing 190

Chapter 7 Action-Oriented Al 191

On Action Games 192
Choreographed Als 192
Implementation 194
Object Tracking 195
Eye Contact: 2D Hemiplane Test 195
3D Version: Semispaces 197
Chasing 199
Chase 2D: Constant Speed 199
Predictive Chasing 200
Evasion 203
Patrolling 203
Hiding and Taking Cover 204
Shooting 206
Infinite-Speed Targeting 206
Real-World Targeting 207
Machine Guns 209
 Table of Contents * ix

Putting It All Together 211

Parallel Automata 211
Al Synchronization 212
In Closing 214
Platform Games 214
Shooters 216
Fighting Games 217
Racing Titles 218

Chapter 8 Tactical Al 219

Tactical Thinking Explained 219
Path Finding 221
Group Dynamics 237
Military Analysis: Influence Maps 241
Data Structure 242
Some Useful Tests 243
Representing Tactics 244
In Closing 248

Chapter 9 Scripting 249

Building a Scripting Language 251
Parsing Simple Languages 251
Parsing Structured Languages 259
Embedded Languages 264
Learning Lua 264
lava Scripting 272
Socket-Based Scripting 276
In Closing 279

Chapter 10 Network Programming 281

Flow the Internet Really Works 282
The Programmer's Perspective: Sockets 284
Clients 285
A Minimal TCP Client 286
A Minimal UDP Client 290
A Simple TCP Server 293
Multichent Servers 296
Concurrent, Connection-Oriented Servers 296
Iterative, Connection-Oriented Servers 299
Core Techniques and Algorithms in Game Programming

UDP Servers 301

Preventing Socket Blocks 302
Designing Client-Server Games 304
Massively Multiplayer Games 306
Data Extrapolation 306
Hierarchical Messaging 308
Spatial Subdivision 309
Send State Changes Only 310
Working with Server Clusters 312
Dynamic Servers and the Braveheart Syndrome 313
In Closing 315

Part II Engine Programming

Chapter 11 2D Game Programming 317

On Older Hardware 317
Data Structures for 2D Games 320
Sprite-Based Characters 320
Mapping Matrices 323
Tile Tables 324
2D Game Algorithms 326
Screen-Based Games 326
Two- and Four-Way Scrollers 327
Multilayered Engines 330
Parallax Scrollers 332
Isometric Engines 334
Page-Swap Scrollers 336
Special Effects 338
Palette Effects 338
Stippling Effects 343
Glenzing 344
Fire 345
In Closing 347

Chapter 12 3D Pipeline Overview 349

A First Look 350
Fundamental Data Types 351
Vertices 351
Indexed Primitives 352
 Table of Contents " xi

Color 356
Texture Mapping 358
Geometry Formats " 359
A Generic Graphics Pipeline 360
Clipping 361
Culling 368
Occlusion Testing 371
Resolution Determination 373
Transform and Lighting 379
Rasterization 380
In Closing 383

Chapter 13 Indoors Rendering 385

General Analysis 385
Occluder-Based Algorithms 386
Binary Space Partition Algorithms 388
Construction 388
View-Dependent Sorting 398
Hierarchical Clipping 400
Occlusion Detection 401
Rendering 403
Portal Rendering 404
Optical Effects Using Portals 408
Hierarchical Occlusion Maps 410
Flybrid Approaches 412
Portal-Octree Hybrid " 412
Quadtree-BSP Hybrid 413
Harciware-Assisted Occlusion Tests 414
In Closing 418

Chapter 14 Outdoors Algorithms 419

Overview 419
Data Structures for Outdoors Rendering 421
Heigh tfields 421
Quadtrees 423
Binary Triangle Trees 424
xii Core Techniques and Algorithms in Game Programming

Geomipmapping 425
ROAM 429
Pass One: Construct the Variance Tree " 429
Pass Two: Mesh Reconstruction 431
Optimizations 434
Chunked LODs 436
A GPU-Centric Approach 440
Outdoors Scene Graphs 443
In Closing 445

Chapter 15 Character Animation 447

Analysis 447
Explicit Versus Implicit Methods 448
Explicit Animation Techniques . 450
Frame Animation 450
Keyframe Animation 451
Tagged Interpolation 454
Implicit Animation Overview 460
Forward Kinematics 462
Math of Skeletal Animation 464
Hardware-Assisted Skeletal Animation 467
Prop Flandling 470
A Note on Vehicles 472
Limb Slicing 473
Facial Animation ~" 474
Inverse Kinematics 477
Analytic IK 477
Cyclic Coordinate Descent 480
Blending Forward and Inverse Kinematics 482
In Closing 483

Chapter 16 Cinematography 485

First-Person Shooters 486
Flandling Inertia 488
Flight Simulators and Quaternions 490
Popular Operations 491
Third-Person Cameras 495
 Table of Contents xiii

Cinematic Cameras: Camera Styles 500

Cinematic Cameras: Placement Algorithms 506
Selecting the Camera Target 507
Selecting the Relevant Information 508
Selecting View Angles 510
Agent-Based Approaches 512
In Closing 513

Chapter 17 Shading 515

Real-World Illumination 516
A Simple Rendering Equation 517
Per-Vertex and Per-Pixel Lighting 521
Light Mapping 522
Diffuse Light Mapping 523
Specular Light Mapping 523
Global Illumination Using Light Maps 524
Implementing Light Mapping: DirectX 525
Creating Light Maps 527
Storing Light Maps 538
The BRDF 541
Average Vector 547
Shadows 548
Nonphotorealistic Rendering 559
Pencil Rendering 560
Outlined Drawing 561
Stroked Outlines 562
Cel Shading 563
Painterly Rendering 564
In Closing 564

Chapter 18 Texture Mapping 565

Types of Textures 566
Texture Mapping 567
XYZ Mapping 568
Cylindrical Mapping 568
Spherical Mapping 569
Texture Mapping a Triangle 570
Tiling and Decals 571
Filtering 572
xiv Core Techniques and Algorithms in Game Programming

Mipmapping 573
Texture Optimization 575
Texture Compression 577
Texture Caching and Paging 578
Multipass Techniques 580
Multitexture 584
Texture Arithmetic and Combination 585
Detail Textures 593
Environment Mapping 594
Bump Mapping 595
Emboss Bump Mapping 596
Dot3 Bump Mapping 597
Gloss Mapping 599
In Closing 600

Chapter 19 Particle Systems 601

Anatomy of a Particle System 602
Local Versus Global Particle Systems 603
The Particle Data Structure 603
A Generic Particle System 605
Spawning Particles 605
Particle Behavior 608
Particle Extinction 612
Rendering Particles 613
Some Notes on Architecture 617
Speed-Up Techniques 619
Avoid Malloc and Free 619
Spatial Indexing 620
LOD Particle Systems 621
Shader-Based Particle Systems 623
In Closing 624

Chapter 20 Organic Rendering 625

Nature and Complexity 626
Trees 627
Billboards 627
Image-Based Methods 630
 .Table of Contents " xv

Parallel IBR Method 630

Orthogonal IBR method 632
Grass 636
Layered Grass 636
Statistical Distribution Algorithms 638
Clouds 640
Skyboxes and Domes 641
Billboarded Clouds 642
Volumetric Clouds 642
Oceans 643
Realistic Ocean Geometry 644
Ocean Appearance 644
Caustics 646
In Closing 650

Chapter 21 Procedural Techniques 651

Procedural Manifesto 652
Renderman 654
Real-Time Shading Languages 658
Current Languages 659
Cg 660
HLSL 660
GL2 Shading Language 660
Types of Shaders 661
A Collection of Shaders 662
Geometry Effects 662
Lighting 664
Texture Mapping 667
Particle Systems 671
Animation 673
Procedural Texturing 676
Special Effects 680
In Closing 682

Chapter 22 Geometrical Algorithms 683

Point Inclusion Tests 683
Point-in-Sphere 684
Point-in-AABB 684
Point-in-Convex Polygon 686
xvi Core Techniques and Algorithms in Game Programming

Point-in-Polygon (Convex and Concave): Jordan

Curve Theorem 687
Point-in-Convex Object " 688
Point-in-Object (Jordan Curve Theorem) 689
Point-in-Object (3DDDA) 689
Ray Intersection Tests 691
Ray-Plane 691
Ray-Triangle 692
Ray-AABB Test 693
Ray-Sphere Test 693
Ray-Convex Hull 695
Ray-General Object (3DDDA) 695
Moving Tests 695
Sphere: Sphere 696
Point Versus Triangle Set Collision (BSP-Based) 699
Mesh Versus Mesh (Sweep and Prune Approach) 699
Computing a Convex Hull 701
2D Solution 701
3D Solution 701
Triangle Reduction 703
Vertex Collapsing 703
Edge Collapsing 704
Progressive Meshes 704
Nonconservative Triangle Reduction 706
In Closing 708

Part III Appendices

Appendix A Performance Tuning 709

Analysis Techniques 709
Timing 710
Memory Footprints 712
Analysis Tools 715
Detecting Bottlenecks 716
General Optimization Techniques 719
Choose Your Enemy 720
Precompute Everything 720
Simplify Your Math 721
Store Data Efficiently 722
 Table of Contents' xvii

Forget MallocO and Free() 723

Be Linear 724
Watch Out for Pointers - 724
Application 725
Efficient Data Transfer 727
Tuning the Geometry Pipeline 731
Tuning the Rasterizer Stage 733
Other Optimization Tools 735
In Closing 735

Appendix B OpenGL . 737

Philosophy 737
Basic Syntax 738
Immediate Mode Rendering 741
Transformations 744
Concatenation of Transforms 747
Hierarchical Transforms 748
Camera Model 749
Lighting 752
Texturing 757
Working in RGBA Mode 763
Display Lists 765
Vertex Arrays 767
Using Regular Vertex Arrays \ 769
Compiled Vertex Arrays 771
Server-Side Vertex Arrays 771
Vertex Array Range 772
Vertex Array Object 772
Vertex Buffer Object 773
OpenGL Extensions 774
Efficiency Considerations 775
Geometric Representation 775
Geometry Rendering 776
Avoid Unneeded State Changes 777
Discard Early 777
In Closing 778
xviii Core Techniques and Algorithms in Game Programming

Appendix C Direct3D 779

History 779
Booting Direct3D 781
Handling Geometry 785
Indexed Primitives 787
User Pointer Primitives 788
Efficient Geometry Delivery 789
Flexible Vertex Formats 790
Matrices, Cameras, and Transforms 792
Working with Texture Maps 794
Lighting 795
Render States 799
The Extension Library 799
ID3DXMesh 799
ID3DXPMesh 800
ID3DXFont 800
Animation Helpers 801
In Closing 802

Appendix D Some Math Involved 803

Distances 803
Distance Between Two Points 803
Distance Between Two Lines 804
Distance from a Point to a Line --^ 805
Distance from a Point to a Plane 805
Distance Between Two Planes 805
Trigonometry 806
Vector Math 807
Modulo 807
Dot Product 807
Cross Product 807
Matrices 808
Matrix Addition 808
Matrix Transposition 809
Matrix-Matrix Multiplication 809
Determinant of a Matrix 809
Inverse ol a Matrix 810
 r
Table of Contents xix

Matrices for Geometry 811

Translation 811
Scaling - • 812
Rotation 812
Basis Matrices 813
Concatenation of Transforms 816

Appendix E Further Reading 817

Chapter 1: Chronology of Game Programming 817
Chapter 2: Game Architecture 817
Chapter 3: Data Structures and Algorithms 818
Chapter 4: Design Patterns 818
Chapter 5: User Input 81.8
Chapters 6, 7, and 8: Fundamental Al Technologies,
Action-Oriented Al, and Tactical Al 818
Chapter 9: Scripting 819
Chapter 10: Network Programming 820
Chapter 11: 2D Programming 820
Chapter 12: 3D Pipeline Overview 820
Chapter 13: Indoors Rendering 821
Chapter 14: Outdoors Algorithms .. 821
Chapter 15: Character Animation 822
Chapter 16: Cinematography 822
Chapter 17: Shading \ 822
Chapter 18: Texture Mapping 823
Chapter 1.9: Particle Systems 823
Chapter 20: Organic Rendering 823
Chapter 21: Procedural Techniques 823
Chapter 22: Geometrical Algorithms 824
Appendix A: Performance Tuning 824
Appendix B: OpenGL 825
Appendix C: Direct3D 825
Appendix D: Some Math Involved 825

Index 827