You are previewing Core Techniques and Algorithms in Game Programming.
O'Reilly logo
Core Techniques and Algorithms in Game Programming

Book Description

To even try to keep pace with the rapid evolution of game development, you need a strong foundation in core programming techniques-not a hefty volume on one narrow topic or one that devotes itself to API-specific implementations. Finally, there's a guide that delivers! As a professor at the Spanish university that offered that country's first master's degree in video game creation, author Daniel Sanchez-Crespo recognizes that there's a core programming curriculum every game designer should be well versed in-and he's outlined it in these pages! By focusing on time-tested coding techniques-and providing code samples that use C++, and the OpenGL and DirectX APIs-Daniel has produced a guide whose shelf life will extend long beyond the latest industry trend. Code design, data structures, design patterns, AI, scripting engines, 3D pipelines, texture mapping, and more: They're all covered here-in clear, coherent fashion and with a focus on the essentials that will have you referring back to this volume for years to come.

Table of Contents

  1. Copyright
    1. Dedication
  2. About the Author
  3. About the Technical Reviewer
  4. Acknowledgments
  5. Tell Us What You Think
  6. Introduction
    1. What You Will Learn
    2. What You Need to Know
    3. How This Book Is Organized
      1. Part I: Gameplay Programming
      2. Part II: Engine Programming
      3. Part III: Appendices
    4. Conventions
  7. 1. A Chronology of Game Programming
    1. Phase I: Before Spacewar
    2. Phase II: Spacewar to Atari
    3. Phase III: Game Consoles and Personal Computers
      1. Game Consoles and Game Developers
      2. Personal Computers
    4. Phase IV: Shakedown and Consolidation
    5. Phase V: The Advent of the Game Engine
    6. Phase VI: The Handheld Revolution
    7. Phase VII: The Cellular Phenomenon
    8. Phase VIII: Multiplayer Games
    9. In Closing
  8. 2. Game Architecture
    1. Real-Time Software
      1. Real-Time Loops
    2. The Game Logic Section
      1. Player Update
      2. World Update
    3. The Presentation Section
      1. World Rendering
      2. NPC Rendering
      3. The Player
      4. Caveat: Networked Games
    4. The Programming Process
      1. Stages
        1. Preproduction: Where Do Ideas Come From?
        2. Discussing Feature Sets
        3. Production: Milestones Are King
        4. Maintenance
    5. In Closing
  9. 3. Data Structures and Algorithms
    1. Types, Structures, and Classes
    2. Data Structures
      1. Static Arrays
      2. Linked Lists
      3. Doubly-Linked Lists
      4. Queues
      5. Stacks
      6. Deques
      7. Tables
        1. Hash Tables
        2. Multi-Key Tables
      8. Trees
        1. Tree Types and Uses
          1. Binary Trees
          2. N-ary Trees
          3. Quadtrees and Octrees
          4. Tries
        2. Tree Traversal Operations
      9. Priority Queues
      10. Graphs
    3. The Standard Template Library
      1. Containers
        1. Vector
        2. List
        3. Deque
        4. Sets and Multisets
        5. Map and Multimap
        6. Hash_set, Hash_multiset, Hash_map, and Hash_multimap
      2. Iterators
    4. In Closing
  10. 4. Design Patterns
    1. Design Patterns Defined
    2. Some Useful Programming Patterns
      1. Singleton
      2. Strategy
      3. Factory
      4. Spatial Index
        1. Spatial Index as a List
        2. Spatial Index as a Regular Grid
        3. Spatial Index as a Quadtree/Octree
      5. Composite
      6. Flyweight
    3. Usability Patterns
      1. Shield
      2. State
      3. Automatic Mode Cancellation
      4. Magnetism
      5. Focus
      6. Progress
    4. In Closing
  11. 5. User Input
    1. The Keyboard
      1. Keyboard with DirectInput
    2. Mouse
      1. Mouselook
    3. Joysticks
      1. Response Curves
    4. Hardware Abstraction
    5. Force Feedback
    6. In Closing
  12. 6. Fundamental AI Technologies
    1. Context
    2. Structure of an AI System
      1. Sensing the World
      2. Memory
      3. Analysis/Reasoning Core
      4. Action/Output System
    3. Specific Technologies
      1. Finite State Machines
        1. An Example
          1. AI Specification
          2. Graphical Layout
          3. Laying Down Some Code
        2. Parallel Automata
        3. Synchronized FSMs
        4. Nondeterministic Automata
      2. Rule Systems
        1. Implementation
          1. Decision Trees
          2. Symbolic Rule Systems
          3. User-Defined Facts
      3. Planning and Problem Solving
        1. State-Space Search
      4. Biology-Inspired AI
        1. Genetic Programming
        2. Generating Populations
        3. Evolutionary Computation
          1. Fitness Testing
          2. Mating, Mutations, and Plateaus
    4. In Closing
  13. 7. Action-Oriented AI
    1. On Action Games
    2. Choreographed AIs
      1. Implementation
    3. Object Tracking
      1. Eye Contact: 2D Hemiplane Test
      2. 3D Version: Semispaces
    4. Chasing
      1. Chase 2D: Constant Speed
      2. Predictive Chasing
    5. Evasion
    6. Patrolling
    7. Hiding and Taking Cover
    8. Shooting
      1. Infinite-Speed Targeting
      2. Real-World Targeting
        1. Version A: The Still Shooter
        2. Version B: The Tracker
      3. Machine Guns
    9. Putting It All Together
      1. Parallel Automata
      2. AI Synchronization
    10. In Closing
      1. Platform Games
      2. Shooters
      3. Fighting Games
      4. Racing Titles
  14. 8. Tactical AI
    1. Tactical Thinking Explained
      1. Path Finding
        1. Crash and Turn
        2. Dijkstra's Algorithm
        3. A*
        4. Region-Based A*
        5. Interactive-Deepening A*
        6. A Note on Human Path Finding
      2. Group Dynamics
        1. Boids
        2. Formation-Based Movement
    2. Military Analysis: Influence Maps
      1. Data Structure
      2. Some Useful Tests
    3. Representing Tactics
    4. In Closing
  15. 9. Scripting
    1. Building a Scripting Language
      1. Parsing Simple Languages
      2. Parsing Structured Languages
    2. Embedded Languages
      1. Learning Lua
        1. Programming
        2. Integration
        3. User-Defined Functions
        4. Real-World Lua Coding
      2. Java Scripting
        1. Java Native Interface
    3. Socket-Based Scripting
    4. In Closing
  16. 10. Network Programming
    1. How the Internet Really Works
    2. The Programmer's Perspective: Sockets
    3. Clients
      1. A Minimal TCP Client
        1. Connection
        2. Data Transfer
        3. Closing Sockets
      2. A Minimal UDP Client
    4. A Simple TCP Server
    5. Multiclient Servers
      1. Concurrent, Connection-Oriented Servers
      2. Iterative, Connection-Oriented Servers
    6. UDP Servers
    7. Preventing Socket Blocks
    8. Designing Client-Server Games
    9. Massively Multiplayer Games
      1. Data Extrapolation
      2. Hierarchical Messaging
      3. Spatial Subdivision
      4. Send State Changes Only
      5. Working with Server Clusters
      6. Dynamic Servers and the Braveheart Syndrome
    10. In Closing
  17. 11. 2D Game Programming
    1. On Older Hardware
    2. Data Structures for 2D Games
      1. Sprite-Based Characters
    3. Mapping Matrices
      1. Tile Tables
        1. Format of the Tiles
        2. Number of Tiles
    4. 2D Game Algorithms
      1. Screen-Based Games
      2. Two- and Four-Way Scrollers
      3. Multilayered Engines
      4. Parallax Scrollers
      5. Isometric Engines
      6. Page-Swap Scrollers
    5. Special Effects
      1. Palette Effects
      2. Stippling Effects
      3. Glenzing
      4. Fire
    6. In Closing
  18. 12. 3D Pipeline Overview
    1. A First Look
    2. Fundamental Data Types
      1. Vertices
      2. Indexed Primitives
        1. Quantization
      3. Color
        1. Alpha
      4. Texture Mapping
    3. Geometry Formats
    4. A Generic Graphics Pipeline
      1. Clipping
        1. Triangle Clipping
        2. Object Clipping
        3. Bounding Spheres
        4. Bounding Boxes
      2. Culling
        1. Object Culling
      3. Occlusion Testing
      4. Resolution Determination
        1. Discrete Level of Detail Policies
        2. Continuous Level of Detail Policies
      5. Transform and Lighting
      6. Rasterization
    5. In Closing
  19. 13. Indoors Rendering
    1. General Analysis
    2. Occluder-Based Algorithms
    3. Binary Space Partition Algorithms
      1. Construction
      2. View-Dependent Sorting
      3. Hierarchical Clipping
      4. Occlusion Detection
      5. Rendering
    4. Portal Rendering
      1. Optical Effects Using Portals
    5. Hierarchical Occlusion Maps
    6. Hybrid Approaches
      1. Portal-Octree Hybrid
      2. Quadtree-BSP Hybrid
    7. Hardware-Assisted Occlusion Tests
    8. In Closing
  20. 14. Outdoors Algorithms
    1. Overview
    2. Data Structures for Outdoors Rendering
      1. Heightfields
      2. Quadtrees
      3. Binary Triangle Trees
    3. Geomipmapping
    4. ROAM
      1. Pass One: Construct the Variance Tree
      2. Pass Two: Mesh Reconstruction
      3. Optimizations
    5. Chunked LODs
    6. A GPU-Centric Approach
    7. Outdoors Scene Graphs
    8. In Closing
  21. 15. Character Animation
    1. Analysis
    2. Explicit Versus Implicit Methods
    3. Explicit Animation Techniques
      1. Frame Animation
      2. Keyframe Animation
      3. Tagged Interpolation
    4. Implicit Animation Overview
      1. Forward Kinematics
      2. Math of Skeletal Animation
      3. Hardware-Assisted Skeletal Animation
    5. Prop Handling
    6. A Note on Vehicles
    7. Limb Slicing
    8. Facial Animation
    9. Inverse Kinematics
      1. Analytic IK
      2. Cyclic Coordinate Descent
    10. Blending Forward and Inverse Kinematics
    11. In Closing
  22. 16. Cinematography
    1. First-Person Shooters
    2. Handling Inertia
    3. Flight Simulators and Quaternions
      1. Popular Operations
    4. Third-Person Cameras
    5. Cinematic Cameras: Camera Styles
    6. Cinematic Cameras: Placement Algorithms
      1. Selecting the Camera Target
      2. Selecting the Relevant Information
      3. Selecting View Angles
    7. Agent-Based Approaches
    8. In Closing
  23. 17. Shading
    1. Real-World Illumination
      1. A Simple Rendering Equation
      2. Per-Vertex and Per-Pixel Lighting
    2. Light Mapping
      1. Diffuse Light Mapping
      2. Specular Light Mapping
      3. Global Illumination Using Light Maps
        1. Implementing Light Mapping: OpenGL
        2. Multipass Version
      4. Implementing Light Mapping: DirectX
      5. Creating Light Maps
        1. Light Map Computation: Phong
        2. Light Map Computation: Ray Tracing
          1. Advanced Light Maps Using Ray Tracing
          2. Light Map Computation: Radiosity
        3. Storing Light Maps
    3. The BRDF
      1. Average Vector
      2. Shadows
        1. Shadow Maps
        2. Stencil Shadows
    4. Nonphotorealistic Rendering
      1. Pencil Rendering
      2. Outlined Drawing
      3. Stroked Outlines
      4. Cel Shading
      5. Painterly Rendering
    5. In Closing
  24. 18. Texture Mapping
    1. Types of Textures
      1. Texture Mapping
      2. XYZ mapping
      3. Cylindrical Mapping
      4. Spherical Mapping
      5. Texture Mapping a Triangle
    2. Tiling and Decals
    3. Filtering
    4. Mipmapping
    5. Texture Optimization
      1. Texture Compression
      2. Texture Caching and Paging
    6. Multipass Techniques
    7. Multitexture
    8. Texture Arithmetic and Combination
    9. Detail Textures
    10. Environment Mapping
    11. Bump Mapping
      1. Emboss Bump Mapping
      2. Dot3 Bump Mapping
    12. Gloss Mapping
    13. In Closing
  25. 19. Particle Systems
    1. Anatomy of a Particle System
      1. Local Versus Global Particle Systems
    2. The Particle Data Structure
      1. A Generic Particle System
      2. Spawning Particles
      3. Particle Behavior
      4. Particle Extinction
      5. Rendering Particles
        1. Compute Particles Cheaply
        2. Use Blending Modes Appropriately
        3. Animated Textures
        4. Chained/Hierarchical Systems
        5. Visual Parameters as Functions of Time
    3. Some Notes on Architecture
    4. Speed-Up Techniques
      1. Avoid Malloc and Free
      2. Spatial Indexing
      3. LOD Particle Systems
      4. Shader-Based Particle Systems
    5. In Closing
  26. 20. Organic Rendering
    1. Nature and Complexity
    2. Trees
      1. Billboards
      2. Image-Based Methods
      3. Parallel IBR Method
      4. Orthogonal IBR method
    3. Grass
      1. Layered Grass
      2. Statistical Distribution Algorithms
    4. Clouds
      1. Skyboxes and Domes
      2. Billboarded Clouds
      3. Volumetric Clouds
    5. Oceans
      1. Realistic Ocean Geometry
      2. Ocean Appearance
      3. Caustics
    6. In Closing
  27. 21. Procedural Techniques
    1. Procedural Manifesto
    2. Renderman
    3. Real-Time Shading Languages
      1. Current Languages
      2. Cg
      3. HLSL
      4. GL2 Shading Language
    4. Types of Shaders
      1. A Collection of Shaders
      2. Geometry Effects
      3. Lighting
    5. Texture Mapping
    6. Particle Systems
    7. Animation
      1. Procedural Texturing
    8. Special Effects
    9. In Closing
  28. 22. Geometrical Algorithms
    1. Point Inclusion Tests
      1. Point-in-Sphere
      2. Point-in-AABB
      3. Point-in-Convex Polygon
      4. Point-in-Polygon (Convex and Concave): Jordan Curve Theorem
      5. Point-in-Convex Object
      6. Point-in-Object (Jordan Curve Theorem)
      7. Point-in-Object (3DDDA)
    2. Ray Intersection Tests
      1. Ray-Plane
      2. Ray-Triangle
      3. Ray-AABB Test
      4. Ray-Sphere Test
      5. Ray-Convex Hull
      6. Ray-General Object (3DDDA)
    3. Moving Tests
      1. Sphere: Sphere
    4. Point Versus Triangle Set Collision (BSP-Based)
    5. Mesh Versus Mesh (Sweep and Prune Approach)
    6. Computing a Convex Hull
      1. 2D Solution
      2. 3D Solution
    7. Triangle Reduction
      1. Vertex Collapsing
      2. Edge Collapsing
      3. Progressive Meshes
      4. Nonconservative Triangle Reduction
    8. In Closing
  29. A. Performance Tuning
    1. Analysis Techniques
      1. Timing
      2. Memory Footprints
    2. Analysis Tools
      1. Detecting Bottlenecks
    3. General Optimization Techniques
      1. Choose Your Enemy
      2. Precompute Everything
      3. Simplify Your Math
      4. Store Data Efficiently
      5. Forget Malloc() and Free()
      6. Be Linear
      7. Watch Out for Pointers
    4. Application
    5. Efficient Data Transfer
    6. Tuning the Geometry Pipeline
    7. Tuning the Rasterizer Stage
    8. Other Optimization Tools
    9. In Closing
  30. B. OpenGL
    1. Philosophy
    2. Basic Syntax
    3. Immediate Mode Rendering
    4. Transformations
      1. Concatenation of Transforms
      2. Hierarchical Transforms
    5. Camera Model
    6. Lighting
    7. Texturing
    8. Working in RGBA Mode
    9. Display Lists
    10. Vertex Arrays
      1. Using Regular Vertex Arrays
      2. Compiled Vertex Arrays
      3. Server-Side Vertex Arrays
      4. Vertex Array Range
      5. Vertex Array Object
      6. Vertex Buffer Object
    11. OpenGL Extensions
    12. Efficiency Considerations
    13. Geometric Representation
      1. Geometry Rendering
      2. Avoid Unneeded State Changes
      3. Discard Early
    14. In Closing
  31. C. Direct3D
    1. History
    2. Booting Direct3D
    3. Handling Geometry
    4. Indexed Primitives
    5. User Pointer Primitives
    6. Efficient Geometry Delivery
    7. Flexible Vertex Formats
    8. Matrices, Cameras, and Transforms
    9. Working with Texture Maps
    10. Lighting
    11. Render States
    12. The Extension Library
      1. ID3DXMesh
      2. ID3DXPMesh
      3. ID3DXFont
    13. Animation Helpers
    14. In Closing
  32. D. Some Math Involved
    1. Distances
      1. Distance Between Two Points
      2. Distance Between Two Lines
      3. Distance from a Point to a Line
      4. Distance from a Point to a Plane
      5. Distance Between Two Planes
    2. Trigonometry
    3. Vector Math
      1. Modulo
      2. Dot Product
      3. Cross Product
    4. Matrices
      1. Matrix Addition
      2. Matrix Transposition
      3. Matrix-Matrix Multiplication
      4. Determinant of a Matrix
      5. Inverse of a Matrix
      6. Matrices for Geometry
      7. Translation
      8. Scaling
      9. Rotation
      10. Basis Matrices
      11. Concatenation of Transforms
  33. E. Further Reading
      1. Chapter 1: Chronology of Game Programming
      2. Chapter 2: Game Architecture
      3. Chapter 3: Data Structures and Algorithms
      4. Chapter 4: Design Patterns
      5. Chapter 5: User Input
      6. Chapters 6, 7, and 8: Fundamental AI Technologies, Action-Oriented AI, and Tactical AI
      7. Chapter 9: Scripting
      8. Chapter 10: Network Programming
      9. Chapter 11: 2D Programming
      10. Chapter 12: 3D Pipeline Overview
      11. Chapter 13: Indoors Rendering
      12. Chapter 14: Outdoors Algorithms
      13. Chapter 15: Character Animation
      14. Chapter 16: Cinematography
      15. Chapter 17: Shading
      16. Chapter 18: Texture Mapping
      17. Chapter 19: Particle Systems
      18. Chapter 20: Organic Rendering
      19. Chapter 21: Procedural Techniques
      20. Chapter 22: Geometrical Algorithms
      21. Appendix A: Performance Tuning
      22. Appendix B: OpenGL
      23. Appendix C: Direct3D
      24. Appendix D: Some Math Involved