You are previewing Game Programming Gems 8.

Game Programming Gems 8

Cover of Game Programming Gems 8 by Adam Lake Published by Course Technology PTR
  1. Copyright
  2. Preface
    1. Overview of Content
    2. About the Cover Image
    3. CD-ROM Downloads
  3. Acknowledgments
  4. Contributors
  5. 1. Graphics
    1. Introduction
    2. 1.1. Fast Font Rendering with Instancing
      1. Text-Rendering Basics
      2. Improving Performance
      3. Instancing Quad Geometry
      4. Constant Array Instancing
      5. Additional Considerations
      6. Future Work
      7. Demo
      8. Conclusion
      9. References
    3. 1.2. Principles and Practice of Screen Space Ambient Occlusion
      1. Screen Space Ambient Occlusion
      2. Generating the Source Data
      3. Sampling Process
      4. Sampling Randomization
      5. Ambient Occlusion Post-Processing
      6. Handling Edge Cases
      7. Optimizing Performance
      8. Fake Global Illumination and Artistic Styling
      9. Transparency
      10. Final Results
      11. Conclusion
      12. References
    4. 1.3. Multi-Resolution Deferred Shading
      1. Deferred Shading
      2. Multi-Resolution Deferred Shading
      3. Conclusion and Future Work
      4. References
    5. 1.4. View Frustum Culling of Catmull-Clark Patches in DirectX 11
      1. Background
      2. Culling
      3. Pre-Processing Step
      4. Run-Time Step
      5. Performance
      6. Conclusion
      7. References
    6. 1.5. Ambient Occlusion Using DirectX Compute Shader
      1. The Compute Shader
      2. Screen Space Ambient Occlusion
      3. Compute Shader Implementation Details
      4. Results
      5. Conclusion and Future Work
      6. References
    7. 1.6. Eye-View Pixel Anti-Aliasing for Irregular Shadow Mapping
      1. Background and Problem: Shadow Edge Aliasing
      2. Solution: Adaptive Multi-Sampling of Irregular Shadows
      3. Results and Discussion
      4. Conclusion
      5. Acknowledgements
      6. References
    8. 1.7. Overlapped Execution on Programmable Graphics Hardware
      1. Introduction to Irregular Z-Buffer Shadows
      2. Overview of Programmable Graphics Hardware
      3. Overview of Task-Based Parallelism
      4. Combining Render Graphs and Task Graphs
      5. Combined Dependency Graph
      6. Idle-Free Irregular Z-Buffer Shadows
      7. Conclusion
      8. References
    9. 1.8. Techniques for Effective Vertex and Fragment Shading on the SPUs
      1. The CBE as Part of a Real-World System
      2. The SPEs
      3. Data Management
      4. Vertex/Geometry Shading
      5. Fragment Shading
      6. Further Work
      7. Conclusion
      8. Acknowledgements
      9. References
  6. 2. Physics and Animation
    1. Introduction
    2. 2.1. A Versatile and Interactive Anatomical Human Face Model
      1. Overview
      2. Numerical Simulation
      3. Building the Anatomical Model
      4. Conclusion
      5. References
    3. 2.2. Curved Paths for Seamless Character Animation
      1. Related Work
      2. Finding a Path
      3. Smoothing the Path
      4. Animation Selection
      5. Conclusion
      6. References
    4. 2.3. Non-Iterative, Closed-Form, Inverse Kinematic Chain Solver (NCF IK)
      1. Context
      2. Bone Definition
      3. IK Goal Position
      4. Handling Extreme Deformation
      5. Additional Details
      6. Future Work
      7. Conclusion
      8. References
    5. 2.4. Particle Swarm Optimization for Game Programming
      1. A Few Words on Optimization
      2. The PSO Paradigm and Its Canonical Formulation
      3. Add-Ons to the Classical Formulation
      4. A Note on Randomness
      5. Case Study 1: Typical Benchmarking Functions
      6. Case Study 2: Optimization of Physical Parameters for In-Game Vehicle Simulation
      7. Case Study 3: Physics-Based Animation of Mechanical Systems
      8. Conclusion
      9. References
    6. 2.5. Improved Numerical Integration with Analytical Techniques
      1. Classifying Errors
      2. Kinematics of Constant Acceleration
      3. The Kinematic Integrator
      4. Integral Contributions Due to a Spring Force
      5. Multiple Forces
      6. Integral Contributions of a Pulse
      7. Integral Contributions of Collision Forces
      8. Integral Contributions of Viscous Forces
      9. Integral Contributions of Constraint Forces
      10. Summary
      11. Conclusion
    7. 2.6. What a Drag: Modeling Realistic Three-Dimensional Air and Fluid Resistance
      1. Physics
      2. Solution of the Three-Dimensional Linear Case
      3. Solution of the Three-Dimensional Quadratic Case
      4. Pseudocode
      5. Comparison of Linear versus Quadratic Solutions
      6. Conclusion
      7. References
    8. 2.7. Application of Quasi-Fluid Dynamics for Arbitrary Closed Meshes
      1. Requirements for the Mesh Representing the Object
      2. Physical Rudiments
      3. Pre-Computation Based on a Triangle Mesh
      4. Calculation of the Pressure on the Triangle Surface
      5. Simple Correction of Dynamic Pressure
      6. Conclusion
      7. References
    9. 2.8. Approximate Convex Decomposition for Real-Time Collision Detection
      1. Approximate Convex Decomposition
      2. Hierarchical Approximate Convex Decomposition
      3. Experimental Results
      4. Conclusion
      5. References
  7. 3. AI
    1. Introduction
    2. 3.1. AI Level of Detail for Really Large Worlds
      1. Gradual LOD Example
      2. Graphical LOD versus LOD AI
      3. Simulation at the Full Detail
      4. Toward LOD AI: Hierarchical Behavior
      5. Space Representation
      6. Positions of Objects and NPCs
      7. Reshaping the Membrane
      8. Creating the Structure of the World
      9. Source Code Summary
      10. Conclusion
      11. Acknowledgements
      12. References
    3. 3.2. A Pattern-Based Approach to Modular AI for Games
      1. A Real-World Example: Apartment Shopping
      2. Boolean Decisions
      3. Float-Based Decisions
      4. Conclusion
      5. References
    4. 3.3. Automated Navigation Mesh Generation Using Advanced Growth-Based Techniques
      1. The Algorithms
      2. Post-Processing
      3. Conclusion
      4. References
    5. 3.4. A Practical Spatial Architecture for Animal and Agent Navigation
      1. Fundamental Components of the Spatial Representation System
      2. Navigation System Architecture
      3. Navrep Continuity and Stitching
      4. Handling Locomotion and Turning
      5. Conclusion
      6. Acknowledgements
      7. References
    6. 3.5. Applying Control Theory to Game AI and Physics
      1. Conclusion
      2. References
    7. 3.6. Adaptive Tactic Selection in First-Person Shooter (FPS) Games
      1. A Dynamic Approach to Adaptive Tactic Selection
      2. Overview of the Adaptive Tactic Selection Architecture
      3. Fitness and Weight-Update Functions
      4. Adapting Tactic Selection
      5. Conclusion
      6. References
    8. 3.7. Embracing Chaos Theory: Generating Apparent Unpredictability through Deterministic Systems
      1. The Need for Predictability
      2. Shaking Things Up
      3. A Brief History of Chaos
      4. Exploring Cellular Automata
      5. Leveraging Chaos Theory in Games
      6. Conclusion
      7. References
    9. 3.8. Needs-Based AI
      1. Background
      2. Needs-Based AI Overview
      3. Advertisements and Action Selection
      4. Action Performance
      5. Design Consequences of Needs-Based AI
      6. Conclusion
      7. Acknowledgements
      8. References
    10. 3.9. A Framework for Emotional Digital Actors
      1. Models of Emotion, Mood, and Personality
      2. The Emotional Framework
      3. Conclusion
      4. References
    11. 3.10. Scalable Dialog Authoring
      1. Conversational Agents Today
      2. Overview
      3. Intention Modeling
      4. Cultural Wrappers
      5. Creating Unique Individuals
      6. Conclusion
    12. 3.11. Graph-Based Data Mining for Player Trace Analysis in MMORPGs
      1. Data Logging and Preprocessing
      2. Advertisement Placement in MMORPGs
      3. Building Player Profiles with Clustering
      4. Detecting Bots and Gold Farmers with Classification Models
      5. Conclusion
      6. References
  8. 4. General Programming
    1. Introduction
    2. 4.1. Fast-IsA
      1. Problem Definition
      2. Balanced Class Hierarchies
      3. Eliminating the Tree Traversal
      4. Building a Balanced Tree
      5. Conclusion
    3. 4.2. Registered Variables
      1. Getting Started
      2. Assumptions
      3. The Base Class: RegisteredVar
      4. Single Variable Values versus Array Variable Values
      5. Type-Specific Registered Variable
      6. Setting a Registered Variable Directly
      7. IsA Functionality
      8. Setting a Registered Variable Indirectly
      9. Conclusion
    4. 4.3. Efficient and Scalable Multi-Core Programming
      1. Efficient Multi-Threaded Programming
      2. Scalable Multi-Threaded Programming
      3. Future Work
      4. Optimizations
      5. Conclusion
      6. References
    5. 4.4. Game Optimization through the Lens of Memory and Data Access
      1. Understand the Cache
      2. Pinpoint Problem Areas
      3. Avoid Waste
      4. Shrink the Data
      5. Organize the Data
      6. Manipulate the Cache
      7. Conclusion
      8. References
    6. 4.5. Stack Allocation
      1. Overview
      2. Example Implementation
      3. Index-Based Implementation
      4. POD Types
      5. Known Issues
      6. Advantages and Disadvantages
      7. Conclusion
    7. 4.6. Design and Implementation of an In-Game Memory Profiler
      1. Introduction
      2. Memory Profiling Basics
      3. Function Hooking
      4. Call-Stack Generation
      5. Collecting Statistics
      6. Multi-Thread Issues
      7. The Source Code
      8. Conclusion
      9. References
    8. 4.7. A More Informative Error Log Generator
      1. Definition of RTSI
      2. Potential Uses
      3. Setting Up the Code
      4. Error Logs Redundancy Problem versus Using RTSI
      5. Conclusion
      6. References
    9. 4.8. Code Coverage for QA
      1. Common Approaches
      2. An Analogy: Breakpoint Testing
      3. Code Coverage
      4. Implementation
      5. QA Interface and Workflow
      6. Collecting Results
      7. Possible Expansions
      8. A Post-Mortem
      9. Conclusion
      10. References
    10. 4.9. Domain-Specific Languages in Game Engines
      1. Domain-Specific Languages in Depth
      2. Creating a DSL
      3. Multi-Language Game Engine Development
      4. Integrating DSLs into the Pipeline
      5. Conclusion
      6. References
    11. 4.10. A Flexible User Interface Layout System for Divergent Environments
      1. The Problem
      2. Some Cheap Solutions
      3. A More Flexible Solution
      4. Concatenate Conditional Modifiers and Conditions
      5. Implementation Details of the CM System
      6. Conditional Modifier Condition References
      7. Widget Templates
      8. Proxy Assets
      9. Performance
      10. Problems
      11. Conclusion
      12. References
    12. 4.11. Road Creation for Projectable Terrain Meshes
      1. Roads as Geodesic Curves
      2. Road Grading Techniques for The Sims 3 Worlds
      3. Conclusion
      4. References
    13. 4.12. Developing for Digital Drawing Tablets
      1. Background
      2. Tablet Theory
      3. Tablet Programming
      4. Conclusion
      5. References
    14. 4.13. Creating a Multi-Threaded Actor-Based Architecture Using Intel® Threading Building Blocks
      1. Introduction
      2. Actor-Based Programming
      3. Implementing an Actor Engine
      4. Message-Passing Patterns
      5. Conclusion
      6. References
  9. 5. Networking and Multiplayer
    1. Introduction
    2. 5.1. Secure Channel Communication
      1. Architecture
      2. Network Security
      3. Attacks
      4. Responses
      5. Disciplinary Measures
      6. Examples
      7. Conclusion
      8. References
    3. 5.2. Social Networks in Games: Playing with Your Facebook Friends
      1. RESTful Web Services
      2. The Facebook API
      3. Conclusion
      4. References
    4. 5.3. Asynchronous I/O for Scalable Game Servers
      1. Background
      2. Asynchronous I/O APIs
      3. Results and Analysis
      4. Conclusion
      5. References
    5. 5.4. Introduction to 3D Streaming Technology in Massively Multiplayer Online Games
      1. The Problem
      2. The Solution
      3. The World
      4. The Rendering
      5. The Transport
      6. Predictive Loading
      7. 3DStreamer: Putting Everything Together
      8. Conclusion
  10. 6. Audio
    1. Introduction
    2. 6.1. A Practical DSP Radio Effect
      1. The Effect
      2. Automatic Gain Control
      3. Adding Static
      4. Putting It All Together
      5. Parameter Animation
      6. Conclusion
    3. 6.2. Empowering Your Audio Team with a Great Engine
      1. Audio Code Building Blocks
      2. Sound Parameterization
      3. Mixing
      4. Post-Production
      5. Conclusion
    4. 6.3. Real-Time Sound Synthesis for Rigid Bodies
      1. Modal Analysis and Impulse Responses
      2. From Physics Engine to Contact Sounds
      3. Putting It Together
      4. Conclusion
      5. References
  11. 7. General Purpose Computing on GPUs
    1. Introduction
    2. 7.1. Using Heterogeneous Parallel Architectures with OpenCL
      1. OpenCL Primer
      2. Tips for Optimizing OpenCL C Kernels
      3. Optimizing Memory-Bound OpenCL Kernels
      4. OpenCL Command Profiling
      5. Conclusion
      6. References
    3. 7.2. PhysX GPU Rigid Bodies in Batman: Arkham Asylum
      1. Requirements
      2. Shape Representation
      3. Dynamics Algorithm
      4. Pipeline
      5. Transform Spheres into World Space
      6. Sphere-Sphere Collision Detection
      7. Sphere-Mesh Collision Detection
      8. Evaluate Force Fields
      9. Calculate Unconstrained Velocities
      10. Generate Constraints
      11. Solver
      12. Update Positions
      13. GPU Implementation
      14. CUDA Voxelizer
      15. Spatial Data Structures
      16. Solver
      17. Conclusion
      18. Acknowledgements
      19. References
    4. 7.3. Fast GPU Fluid Simulation in PhysX
      1. Particle Systems
      2. Fluids
      3. Robust Particle Collisions
      4. Fluid Simulation with Smoothed Particle Hydrodynamics
      5. Fluid Simulation Algorithm
      6. Fluid Rendering
      7. Performance
      8. Acknowledgements
      9. References
  12. Color Plate
O'Reilly logo

Chapter 3.4. A Practical Spatial Architecture for Animal and Agent Navigation

Michael Ramsey—Blue Fang Games, LLC.

 

“Not so many years ago, the word ‘space’ had a strictly geometrical meaning: the idea evoked was simply that of an empty area.”

 
 --Henri Lefebvre

Game literature is inundated with various techniques to facilitate navigation in an environment. However, many of them fail to take into account the primary unifying medium that animals and agents use as locomotion in the real world. And that unifying medium is space [Lefebvre97]. The architectonics[1] of space relative to an animal’s or agent’s motion in a game environment is the motivation for this gem. Traditional game development focuses on modeling what is physically ...

The best content for your career. Discover unlimited learning on demand for around $1/day.