|
Game Programming Gems 5
With every new volume, the Game Programming Gems series continues to provide a road map through the vast array of development challenges facing todays game programmers. With the wisdom of many industry experts, Gems 5 includes 62 newly unearthed gems that were polished up for your reading pleasure. These gems are filled with practical insights and
techniques that will solve your current problems and help inspire future games. You and your team need to develop for todays platforms, while preparing for the new technology looming on the horizon and with the tools provided here, you can! So dig into this new collection and put it to work.
CONTENTS:
v
Contents
Foreword. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Preface. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv
About the Cover Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix
Contributor Bios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi
SECTION 1 GENERAL PROGRAMMING . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
William E. Damon III
1.1 Context-Sensitive HUDs for Editors. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Adam Martin, Grex Games
1.2 Parsing Text Data in Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Aurelio Reis
1.3 Component Based Object Management . . . . . . . . . . . . . . . . . . . . . . . 25
Bjarne Rene, Circle Studio ltd
1.4 Using Templates for Reflection in C++ . . . . . . . . . . . . . . . . . . . . . . . . 39
Dominic Filion, Artificial Mind & Movement
1.5 Sphere Trees for Speedy BSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Dominic Filion, Artificial Mind & Movement
1.6 Improved Frustum Culling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Frank Puig Placeres
1.7 Generic Pager . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Ignacio Incera Cruz
1.8 Large-Scale Stack-Based State Machines. . . . . . . . . . . . . . . . . . . . . . 93
James Boer
1.9 CSG Construction Using BSP Trees . . . . . . . . . . . . . . . . . . . . . . . . . 103
Octavian Marius Chincisan
1.10 Building Lua into Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Matthew Harmon, eV Interactive Corporation
1.11 Improving Freelists with Policy Based Design. . . . . . . . . . . . . . . . . . 129
Nathan Mefford
1.12 A Real-Time Remote Debug Message Logger . . . . . . . . . . . . . . . . . . 143
Patrick Duquette, Microds Canada Inc.
1.13 A Transparent Class Saving and Loading Trick . . . . . . . . . . . . . . . . . 149
Patrick Meehan
1.14 An Effective Cache-Oblivious Implementation of the ABT Tree . . . . 159
Sebastien Schertenleib, Swiss Federal Institute of Technology (EPFL),
Virtual Reality Lab (VRlab)
1.15 Visual Design of State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Scott Jacobs
1.16 A Generic Component Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Warrick Buchanan
1.17 Choose Your Path - A Menu System . . . . . . . . . . . . . . . . . . . . . . . . . 189
Wendy Jones
SECTION 2 MATHEMATICS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Eric Lengyel, Naughty Dog Inc.
2.1 Using Geometric Algebra for Computer Graphics . . . . . . . . . . . . . . . 201
Chris Lomont
2.2 Minimal Acceleration Hermite Curves . . . . . . . . . . . . . . . . . . . . . . . . 225
Tony Barrera, Barrera Kristiansen AB; Anders Hast, Creative Media Lab,
University of Gvle; and Ewert Bengtsson, Centre for Image Analysis,
Uppsala University
2.3 Spline-Based Time Control for Animation . . . . . . . . . . . . . . . . . . . . . 233
James M. Van Verth, Red Storm Entertainment
2.4 Faster Quaternion Interpolation Using Approximations. . . . . . . . . . . 247
Andy Thomason
2.5 Minimax Numerical Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 269
Christopher Tremblay
2.6 Oblique View Frustums for Mirrors and Portals. . . . . . . . . . . . . . . . . 281
Eric Lengyel
vi Contents
SECTION 3 ARTIFICIAL INTELLIGENCE. . . . . . . . . . . . . . . . . . . . . . . . . 295
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
Robin Hunicke, Northwestern University
3.1 Automatic Cover Finding with Navigation Meshes . . . . . . . . . . . . . . 299
Borut Pfeifer, Radical Entertainment
3.2 Fast Target Ranking Using an Artificial Potential Field . . . . . . . . . . . 307
Markus Breyer, Factor 5
3.3 Using Lanchester Attrition Models to Predict the
Results of Combat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
John Bolton, Page 44 Studios, LLC
3.4 Implementing Practical Planning for Game AI . . . . . . . . . . . . . . . . . . 329
Jamie Cheng, Relic Entertainment Inc., and Finnegan Southey, University of Alberta,
Department of Computing Science
3.5 Optimizing a Decision Tree Query Algorithm for
Multithreaded Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
Chuck DeSylva, Intel Corporation
3.6 Parallel AI Development with PVM . . . . . . . . . . . . . . . . . . . . . . . . . . 353
Michael Ramsey, 2015 Inc.
3.7 Beyond A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
Mario Grimani, Xtreme Strategy Games and Matthew Titelbaum, Monolith Productions
3.8 Advanced Pathfinding with Minimal Replanning Cost:
Dynamic A Star (D*) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
Marco Tombesi
SECTION 4 PHYSICS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Mike Dickheiser, Red Storm Entertainment
4.1 Back of the Envelope Aerodynamics for Game Physics . . . . . . . . . . 395
Graham Rhodes, Applied Research Associates, Inc.
4.2 Dynamic Grass Simulation and Other Natural Effects . . . . . . . . . . . . 411
Rishi Ramraj, The University of Waterloo
Contents vii
4.3 Realistic Cloth Animation Using the Mass-Spring Model . . . . . . . . . 421
Juan M. Cordero, Dep. de Lenguajes y Sistemas Informticos, Universidad de Sevilla
4.4 Practical Animation of Soft Bodies for Game Development: The
Pressurized Soft-Body Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
Maciej Matyka, University of Wroclaw
4.5 Adding Life to Ragdoll Simulation Using Feedback
Control Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
Michael Mandel, Apple Computer
4.6 Designing a Prescripted Physics System . . . . . . . . . . . . . . . . . . . . . 457
Daniel F. Higgins
4.7 Prescripted Physics: Techniques and Applications. . . . . . . . . . . . . . 473
Shawn Shoemaker
4.8 Realistic Camera Movement in a 3D Car Simulator. . . . . . . . . . . . . . 483
Barnabs Aszdi and Szabolcs Czuczor, Budapest University of Technology and
Economics, Department of Control Engineering and Information Technology,
Computer Graphics Group
SECTION 5 GRAPHICS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
Jason L. Mitchell, ATI Research
5.1 Realistic Cloud Rendering on Modern GPUs . . . . . . . . . . . . . . . . . . . 499
Jean-Franois Dube, UBISOFT
5.2 Let It Snow, Let It Snow, Let It Snow (and Rain) . . . . . . . . . . . . . . . . 507
Niniane Wang, Google Inc., and Bretton Wade, Microsoft Corporation
5.3 Widgets: Rendering Fast and Persistent Foliage. . . . . . . . . . . . . . . . 515
Martin Brownlow
5.4 2.5 Dimensional Impostors for Realistic Trees and Forests . . . . . . . 527
Gbor Szijrt, Technical University of Budapest
5.5 Gridless Controllable Fire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
Neeharika Adabala, School of Computer Science, University of Central Florida, and
Charles E. Hughes, School of Computer Science and School of Film and Digital
Media, University of Central Florida
5.6 Powerful Explosion Effects Using Billboard Particles . . . . . . . . . . . . 551
Steve Rabin, Nintendo of America Inc.
viii Contents
5.7 A Simple Method for Rendering Gemstones . . . . . . . . . . . . . . . . . . . 561
Thorsten Scheuermann, ATI Research
5.8 Volumetric Post-Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
Dominic Filion, Artificial Mind & Movement, and Sylvain Boisse, Motorola
5.9 Procedural Level Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
Timothy E. Roden and Ian Parberry, University of North Texas
5.10 Recombinant Shaders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
Dominic Filion, Artificial Mind & Movement
SECTION 6 NETWORK AND MULTIPLAYER . . . . . . . . . . . . . . . . . . . . . . 599
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
Shekhar Dhupelia
6.1 Keeping a Massively Multiplayer Online Game Massive,
Online, and Persistent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
Shea Street, Tantrum Games
6.2 Implementing a Seamless World Server . . . . . . . . . . . . . . . . . . . . . . 611
Patrick Duquette, UBISOFT Entertainment Inc.
6.3 Designing a Vulgarity Filtering System . . . . . . . . . . . . . . . . . . . . . . . 621
Shekhar Dhupelia
6.4 Fast and Efficient Implementation of a Remote Procedure
Call System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
Hyun-jik Bae
6.5 Overcoming Network Address Translation in Peer-to-Peer
Communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
Jon Watte
6.6 A Reliable Messaging Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
Martin Brownlow
6.7 Safe Random Number Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
Shekhar Dhupelia
6.8 Secure by Design. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681
Adam Martin, Grex Games
Contents ix
SECTION 7 AUDIO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695
Mark DeLoura
7.1 Multithreaded Audio Programming Techniques . . . . . . . . . . . . . . . . 697
James Boer
7.2 Sound Management by Group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 713
Matthew Harmon, eV Interactive Corporation
7.3 Using 3D Surfaces as Audio Emitters . . . . . . . . . . . . . . . . . . . . . . . . 721
Sami Hamlaoui
7.4 Fast Environmental Reverb Based on Feedback Delay Networks . . . 729
Christian Schler, Phenomic Game Development
7.5 Introduction to Single-Speaker Speech Recognition. . . . . . . . . . . . . 741
Julien Hamaide
About the CD-ROM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 751
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753
x Contents
|
