|
|
Game Programming Gems 6
52 articles, Edited by Mike Dickheiser, 2006.
|
Survey of Lowest Known Online Prices
$48.97 (30% off) Amazon.com (free shipping)
$55.96 (20% off) BarnesAndNoble.com
Section 1: General Programming
 |
Lock-free algorithms allow access to shared data without needing a lock, but they may restrict what operations are allowed. These algorithms are not wait-free in the sense that all threads will progress immediately, but at least one thread is always able to make progress. Additionally, the algorithms are not necessarily fair; threads are not guaranteed access in order. One of the primary advantages is that lock-free algorithms can provide a huge boost in speed when used in the right places. They are also invulnerable to deadlock, and terminating a thread in the middle of an operation will not affect the stability of other threads. There are other advantages, but game programmers will generally choose lock-free algorithms due to their speed advantages.
Utilizing Multicore Processors with OpenMP |
The reality is that game players will have machines with multiple processors. Taking advantage of these new architectures requires multithreaded approaches to software development. Game developers now face the complex task of multithreading their game engines. The high-performance computing industry has been dealing with this problem for some time. This industry often needs to schedule dozens and sometimes hundreds of independent processors that have a shared view of memory. One of their solutions is called OpenMP. OpenMP is a portable, industry-standard API and programming protocol for C/C++ that supports parallel programming. Many compilers used by game developers are integrating OpenMP technology. This gem provides a brief overview of OpenMP and examines how games can take advantage of this technology to improve performance.
Computer Vision in Games Using the OpenCV Library |
 | |
Arnau Ramisa (Institut d�Investigaci?en Intellig�ncia Artificial), Enric Vergara (Universitat Polit�cnica de Catalunya), Enric Mart?(Universitat Aut�noma de Barcelona)
Game Programming Gems 6, 2006. |
Intel's Open Computer Vision Library (OpenCV) is a powerful, fast, and easy-to-use collection of algorithms and data types written in C/C++, which were created to aid in the development of real-time computer vision applications. Some of the areas covered by the library are: image statistics, mathematic morphology, contour detection and processing, histograms, optical flow, gesture recognition, and many more. To illustrate the applicability of computer vision to traditional games, and to introduce the reader to the OpenCV library, we provide a simple example.
Geographic Grid Registration of Game Objects |
Large, open battlefields or spacefields can contain hundreds or even thousands of objects. When there are no walls, mountains, or forests to separate them, all objects effectively exist in the same room. This presents a difficult computational problem for an AI agent (or any other game system) that is trying to identify the closest or most desirable targets. Svarovsky described this problem very briefly in the first volume of Game Programming Gems. In this gem we explore it more deeply, explain why these open spaces are so difficult to deal with, and present a relatively simple solution that has been implemented in a number of simulations. Pritchard also explored tile-based LOS in Game Programming Gems 2; but he limited his discussion to detectability from the perspective of the human player, leaving the actual detection outcome to the graphic-rendering engine and the human eye. This gem includes complete detection decisions for AI agents who rely on range and LOS calculations entirely in the game engine, and of course extends this to use for any system in the game that needs to make similar queries.
This gem presents a fully functional Binary Space Partition (BSP) compiler. It incorporates new algorithms for automatic portal generation and potentially visible set computation currently used in the Getic 3D?Editor and BSP compiler. This gem also comes with a full implementation of the BSP compiler on the accompanying CD-ROM.
Closest-String Matching Algorithm |
In this gem, we'll demonstrate an algorithm that can be used to find how closely any two strings match. More importantly, we'll demonstrate how this function can be utilized at the heart of a handy error-reporting mechanism wherever data is indexed and sorted by string-based IDs. When no exact string ID is found, this error-reporting mechanism can give the user a best guess as to which string should have been used instead. One of the best examples of this technology in action is the Google?search engine. We'll examine a way to bring a very simple version of this functionality to a game database.
Using CppUnit To Implement Unit Testing |
In the realm of quality assurance, there are two basic domains of testing: black box and white box testing. Black box testing refers to a Quality Assurance (QA) team's testing of a fully integrated system, which includes such techniques as script-based functional testing and manual testing (either unstructured or following a test plan). In contrast, white box testing is quality validation performed by the development team prior to the QA team's testing efforts. White box testing traditionally includes peer reviews and unit testing, the latter of which we will discuss in this gem. Essentially, unit testing is the use of automated tests to verify the results and behavior of smaller components of a software system at the developer's level, regardless of how the component is normally used.
Fingerprinting Pre-Release Builds To Deter and Detect Piracy |
No one wants to see their game pirated, but it is especially heartbreaking when this happens to your game before it has been released. It's one thing when you've sold your game to a million people and it's open season on your copy protection, but it's another thing when an insider leaks a pre-release build. So the big question is: What can be done about this? The solution is twofold. First, you must deter those who have access to pre-release builds from leaking them in the first place. Second, if a build is leaked, you must somehow detect who is responsible so that they can be held accountable. The truth is that if the build gets out, you've lost the war, but it's important to be able to detect the guilty party so as to put teeth into your deterrence strategy. This article will briefly discuss deterrence and then delve deeply into methods for detection through the use of embedded digital fingerprints.
Faster File Loading with Access-Based File Reordering |
Most games face the requirement of loading resources from media. Operating systems can be fairly slow when obtaining file handles for a large number of files. Most games load their resources from packed resource files as an optimization. These are large file databases that contain a full directory hierarchy as a single file or small group of files. Resource files effectively solve this file-handle overhead issue. However, another problem exists: The order of resource files is generally a mirror of the directory structure on disk. Games rarely access resources in the order they appear within the directory structure. Instead, they tend to jump around within the resource file. This can be a major bottleneck. Resources will always load faster when accessed sequentially. Modern games use a large enough data set to show this weakness within the resource file layout. All games exhibit some pattern of resource usage. The next step in optimizing load times is to gather data on how the game uses resources. We can then examine those usage patterns to provide an optimized file order within the resource file. This gem explains a potential solution to this common problem.
Stay in the Game: Asset Hotloading for Fast Iteration |
Asset hotloading is the process by which assets are automatically reloaded into the game while it is running, without stopping or restarting a level. Hotloading can be done with many types of assets: textures, models, level geometry, scripts, game object data, sounds, animations, and so on; and it can reduce iteration times to just a few seconds, even when working with game consoles. Not only will asset hotloading make a huge impact on the quality of your game, but you'll also earn the eternal gratitude of your content creators. This gem shows one possible implementation that offloads as much work as possible to offline tools and minimizes the changes to the game runtime. By adopting this strategy incrementally with the assets that change most frequently, or by implementing it across the board on all game assets, content creators will be able to stay in the game and create the best possible content for their projects.
Section 2: Mathematics and Physics
The first step to mastering floating-point code is to understand how floating-point values are stored in terms of their bit representations. This article will explain in detail the floating-point storage format used on the majority of systems. Those rare systems not implementing this method almost always use a similar one with minor variations, so the knowledge gained by studying this article will benefit your algorithm development greatly. One final note before we begin: An article similar to this one appeared in Game Programming Gems 2. This gem extends that article in several areas, offering many new tricks and at least one improvement.
GPU Computation in Projective Space Using Homogeneous Coordinates |
In this gem, we will show how common intersection computations can be performed directly using homogeneous coordinates. This approach results in higher numerical stability and, in some cases, a significant speed-up. The presented approach is especially convenient if vector and matrix operations are supported on the main processor, or for applications on a Graphics Processing Unit, or GPU.
Solving Systems of Linear Equations Using the Cross Product |
The most common uses of the cross product in computer graphics are to compute the normal of a polygon and perhaps to compute the area of a polygon. This article will show some lesser known applications for the cross product, which might be a surprise for those that are not experts in the field of clipping. In particular, the cross product can be used for solving systems of linear equations. For example, it can be used for computing the intersection of two implicit lines, as well as for computing the coefficients of an implicit line from two given points. We will also show how the setup for bilinear interpolation over a polygon can be computed efficiently using the cross product. Finally, we will show how the cross product can be used to compute the inverse of a 333 matrix. Since the cross product is implemented in hardware in both CPUs and GPUs, making careful use of these properties might lead to more-efficient code.
Efficient Sequence Indexing for Game Development |
Sequence indexing is the art of manipulating objects. It tries to answer one simple question: Given a collection of objects, how do we create, access, and identify various groups of objects drawn from that collection? Most games consist of large collections of objects, so it can be seen how understanding these concepts might be useful for game development. Mathematically, we represent these collections of objects as a sequence. This gem presents the mathematical formulas for indexing and deindexing a few well-known sequences, such as range sequences, permutation sequences, and combinatorial sequences. It also offers a few tips on how they can best be utilized in game environments for various tasks, ranging from simulating deterministic randomness to serializing game objects.
Exact Buoyancy for Polyhedra |
This gem describes an efficient method for computing buoyancy and drag forces on rigid bodies. The algorithm determines an exact buoyancy force for a polyhedron in a water volume. The central equations are in vector form to allow for SIMD optimization. Fagerlund and Gomez have provided similar investigations of real-time buoyancy. Fagerlund uses embedded spheres to approximate the submerged portion of an object. This requires an additional authoring step, and many spheres may be required. Gomez distributes points on the object's surface and attributes a portion of the surface area to each point. He computes vertical columns of displaced water at each surface point. His method also requires an additional authoring step and may require many points to be placed on the surface (e.g., 20 to 30 for a cube). In contrast, the algorithm presented here requires no additional authoring step. In terms of geometric data, the algorithm only needs the vertices and triangles of the polyhedron; however, it is limited to flat water surfaces.
Real-Time Particle-Based Fluid Simulation with Rigid Body Interaction |
Realistic, real-time rendering of the motion of fluids is one of the ways to immerse the user into an interactive application, such as a computer game. The interaction of fluids with rigid bodies is important, because in real life, the motion of fluids and rigid bodies is affected by their influences on each other. Fluid simulation based on Computational Fluid Dynamics (CFD) is useful for rendering a visually plausible behavior for the fluid. However, the computational cost of many CFD techniques is often too great for real-time rendering of fluids, which requires fast simulation. Furthermore, many traditional techniques do not enable an easy simulation of fluids interacting with rigid bodies. This article describes a way to use the smoothed particle hydrodynamics technique to simulate fluids that interact with rigid bodies, and vice versa. We also provide a fast implementation. The proposed method enables real-time simulation of water with rigid body interaction.
Section 3: Artificial Intelligence
Applying Model-Based Decision-Making Methods to Games: Applying the Locust AI Engine to Quake III |
Developing good game Artificial Intelligence (AI) is difficult. The standard approach to developing game AI is based on rules. Unfortunately, rules are brittle, expensive, and time-consuming to develop, modify, and debug, and often result in unintelligent behavior. This gem describes a new approach to game AI, one based on models of the underlying game world-actions, their effects, and observations. The model-based approach is more robust, reduces development cost and time, eases modifications-and results in behavior that is more intelligent. Specifically, this article describes the preliminary results of applying the model-based approach as embodied in the Locust AI engine to Quake III. This article focuses on the impact on the game AI practitioner in terms of features and benefits, and presents a vision for the future of game AI development.
Achieving Coordination with Autonomous NPCs |
This article presents some mechanisms that can be easily added to autonomous NPCs to allow more-cooperative operation. Even though each NPC is deciding its behavior independently, the addition of some extra information and simple communication will make it seem that real coordination is happening.
Behavior-Based Robotic Architectures for Games |
Professional developers and academics have investigated the application of robotic architectures in games, with encouraging results. Yiskis and Champandard have used the subsumption architecture, with the latter making a bot for Quake II. Pinto has applied extended behavior networks to the design of agents for Unreal Tournament. In this gem, we examine these architectures and their applications, present other promising techniques, and point extensions to the systems discussed.
Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Behavior Networks |
In this article, we describe how we designed and integrated fuzzy sensors, finite-state machine behaviors, and an extended behavior network to build a robot for Unreal Tournament. Extended behavior networks are a class of action-selection architectures designed to select good enough sets of actions for agent with many goals situated in dynamic and complex environments. Fuzzy sensors have been successfully applied to various domains in which we have continuous properties and arbitrary categories, and with good results. Finite-state machines are a well-known and well-established technique, both in academia and the game development community, that have been extensively applied in games. They are a good modeling technique for basic competences and behaviors.
A Goal-Oriented Unreal Bot: Building a Game Agent with Goal-Oriented Behavior and Simple Personality Using Extended Behavior Networks |
First-person shooter games, such as Unreal Tournament, constitute a domain where the application of extended behavior networks is interesting. We have the agent situated in a 3D, continuous virtual environment, interacting in many ways with several entities in real time. The scenarios an agent may face are varied and complex. The agent has many weapons available, each with certain properties, and has several items to use. It moves over different landscapes and interacts with several other agents. The action repertory is large (e.g., run, walk, turn, crawl, shoot, change weapons, jump, strafe, pickup item, and use item, among others), and an agent may carry out more than one action simultaneously, such as shooting while jumping. Also, the agent has many possibly conflicting goals, such as fighting while staying safe. For most game modes, simple, stereotypical personalities suffice, as we have mostly shallow characters. In this article, we present the extended behavior network model and the results of experiments to assess its action-selection quality, and we illustrate how we may tune and modify a behavior network so as to achieve different character personalities.
Short-Term Memory Modeling Using a Support Vector Machine |
Programming challenging artificial intelligence in games is one of the most interesting problems you can face. The key element is the learning process. The learning systems experience a lot of difficulties when the strategy of the player is changing continuously. Classical learning systems take time to forget the old rules and to learn the new ones. As a solution, this gem introduces a temporal concept for learning classifiers. The system can easily forget past events. Presented with Support Vector Machines (SVMs), this technique can be applied to other kinds of classifiers.
Using the Quantified Judgment Model for Engagement Analysis |
The Quantified Judgment Model (QJM) is both a model and a theory of combat. Originally developed to simulate historical battles and then later (upon further refinement) used for modern engagement prediction, it is an ideal system for predicting potential victors in a game. In this gem, we will describe the base QJM formula. The base formula can then be further expanded upon by adding models such as an attrition calculation, spatial effectiveness of units, and casualty effectiveness. This gem details the basic QJM formula, and how it can be used to predict combat results quickly, consistently, and efficiently.
Designing a Multilayer, Pluggable AI Engine |
The purpose of this gem is to present an architecture for a data-driven AI engine capable of controlling large groups of autonomous characters that are responding to environment and user interactions in real time. The actual engine that we coded was used as a crowd-simulation system. This article will outline a fully realized data-driven AI system and show its pros and cons, and also compare and contrast this with more-traditional, code-based AI implementations.
A Fuzzy-Control Approach to Managing Scene Complexity |
It is commonly known that games are designed around expected rendering-load ranges. Often, 3D artists work with level editors that are directly linked to the actual game engines, as this allows them to preview their work and to check if the content developed can be run at interactive frame rates. While this has become a norm, probably due to the way games are played by single-users in an expected manner, it is increasingly evident that dynamic environments, such as multiplayer gaming scenarios, are challenging this paradigm. In this article, we describe a fuzzy-control approach to managing scene complexity that addresses both performance and image quality, and is suitable for use in dynamic gaming environments.
Section 4: Scripting and Data-Driven Systems
Scripting Language Survey |
There are many scripting languages available. This article does not try to cover all possible options, but only a few of the most popular ones in game development, as well as a few that are emerging: Python, Lua, GameMonkey, AngelScript. Lua and Python are part of successful commercial games, while GameMonkey and AngelScript are young and still introducing themselves to the game community.
Binding C/C++ Objects to Lua |
| |
Waldemar Celes (PUC-Rio), Luiz Henrique de Figueiredo (Institute for Pure and Applied Mathematics), Roberto Ierusalimschy (PUC-Rio)
Game Programming Gems 6, 2006. |
One reason for the success of Lua as a scripting language is that it is easy to embed; this was one of the original design goals of Lua. However, Lua does not come with tools for creating bindings automatically, because another design goal of Lua is to provide mechanisms, not policy. As a consequence, there are multiple strategies for binding host objects to Lua. Each strategy has advantages and drawbacks, and game developers have to identify the best strategy to expose the desired functionality to the scripting environment. Some developers may map C/C++ objects as simple values, while others may need to implement mechanisms that allow runtime-type checking, or to extend the services provided by the host in Lua. Another important issue that must be addressed is whether to allow Lua to control the lifetime of host objects. In this article, we explore different strategies to bind host objects using Lua's API.
Programming Advanced Control Mechanisms with Lua Coroutines |
| |
Waldemar Celes (PUC-Rio), Luiz Henrique de Figueiredo (Institute for Pure and Applied Mathematics), Roberto Ierusalimschy (PUC-Rio)
Game Programming Gems 6, 2006. |
Managing High-Level Script Execution Within Multithreaded Environments |
Exposing Actor Properties Using Nonintrusive Proxies |
Game Object Component System |
Section 5: Graphics
Synthesis of Realistic Idle Motion for Interactive Characters |
Spatial Partitioning Using an Adaptive Binary Tree |
Enhanced Object Culling with (Almost) Oriented Bounding Boxes |
Skin Splitting for Optimal Rendering |
Interactive Fluid Dynamics and Rendering on the GPU |
Fast Per-Pixel Lighting with Many Lights |
Rendering Road Signs Sharply |
Practical Sky Rendering for Games |
High Dynamic Range Rendering Using OpenGL Frame Buffer Objects |
Section 6: Audio
Real-Time Sound Generation from Deformable Meshes |
A Lightweight Generator for Real-Time Sound Effects |
Faking Real-Time DSP Effects |
Section 7: Network and Multiplayer
Dynamically Adaptive Streaming of 3D Data for Animated Characters |
| |
Thomas Di Giacomo, HyungSeok Kim, Stephane Garchery, and Nadia Magnenat-Thalmann (MIRALab, C.U.I, University of Geneva), and Chris Joslin (School of Information Technology, Carleton University)
Game Programming Gems 6, 2006. |
Complex Systems Based High-Level Architecture for Massively Multiplayer Games |
Generating Globally Unique Identifiers for Game Objects |
Massively Multiplayer Online Prototype Utilizing Second Life for Game Concept Prototyping |
Reliable Peer-to-Peer Gaming Connections Penetrating NAT |
|
