 |
|
|
Game Programming Gems 7
48 articles, Edited by Scott Jacobs, 2008.
|
Survey of Lowest Known Online Prices
$48.99 (30% off) Amazon.com (free shipping)
$55.99 (20% off) BarnesAndNoble.com
Section 1: General Programming
 |
Efficient Cache Replacement using the Age and Cost Metrics |
In memory constrained game environments, custom media caches are used to amplify the amount of data in a scene, while leaving a smaller memory footprint than containing the entire media in memory at once. The most difficult aspect of using a cache system is identification of the proper victim page to vacate when the cache fills to its' upper bounds. As cache misses occur, the choice of page replacement algorithm is essential: it is directly linked to the performance and efficiency of hardware memory usage for your game. A bad algorithm will often destroy the performance of your title, where a well implemented algorithm will enhance the quality of your game by a significant factor, without affecting performance. Quite popular cache replacement algorithms, such as LRU, work well for their intended environment, but often struggle in situations that require more data to make accurate victim page identifications. This article presents the Age and Cost metrics to be used as values in constructing the cache replacement algorithm that best fits your game's needs.
High Performance Heap Allocator |
In this gem we will show a novel technique for building a high performance heap allocator, with specific focus on portability, full alignment support, low fragmentation and low book-keeping overhead. Additionally, we will show how to extend the allocator with debugging features and additional interface functions to achieve better performance and usability.
Optical Flow for Video Games Played with Webcams |
 | |
Arnau Ramisa (Institut d'Investigaci?en Intellig�ncia Artificial), Enric Vergara (GeoVirtual), Enric Mart?(Universitat Aut�noma de Barcelona)
Game Programming Gems 7, 2008. |
One of the most widely used techniques in computer vision commercial games is the concept of optical flow. Optical flow is the movement between the pixels of successive frames of a video stream provided, for example, by a modern webcam. Multiple techniques, with different properties, exist in the computer vision literature to determine the optical flow field between a pair of images. In this gem we will explain three of these techniques: the direct subtraction of successive frames, motion history and a more advanced technique: the Lucas & Kanade algorithm. These three techniques have a different degree of robustness and also a different computational cost, therefore the choice depends on the requirements of each application.
Design and Implementation of a Multi-Platform Threading Engine |
This gem focuses on the development of a threading engine that has been engineered for both an Xbox360 and a standard multi-core PC game engine. With that being said, I've provided details on the core systems that are applicable to all architectures, not just a multi-core desktop (Windows/Linux) or Xbox360. So while we will talk about cache lines, they will focus on the principles that make them important across multi-platforms and operating systems.
For Bees and Gamers: How to Handle Hexagonal Tiles
|
Grids are the one of the most prominent tools to simplify complex structures and relationships in order to simulate or visualize them. Their use in games ranges from the graphical tiles of 8x8 pixels used in handheld games to the space representation for AI agents. The typical choice, a square grid, is biased by the squares' simple computational rules; they do not show a surpassing behavior in simulation. Hexagonal tiles, in contrast, offer highly attractive features in both logic and look. However, hexagonal grids are awkward in software development. This gem introduces concepts and techniques to deal with this issue.
A Sketch-based Interface to Real-Time Strategy Games Based on a Cellular Automaton |
How can we control hundreds of units in a realistic and efficient way? And since the interface is designed for hand-to-hand combat, what should we do when the army becomes huge and there is no clear way to direct it? We are facing such situations in current game titles, and despite recent improvements, common unit-based interfaces sometimes leave players frustrated. In this work we describe an alternative which may improve gameplay in such situations. We propose a one-click higher-level interface that controls the movement of entire armies or groups of soldiers.
Foot Navigation Technique for First-Person Shooting Games |
Interaction control in first-person shooting (FPS) games is a complex task that normally involves the use of mouse and keyboard simultaneously, and the memorization of many shortcuts. Since FPS games are highly based on the character movement in the virtual world, a combination of left and right hands (keyboard and mouse) is used to control navigation and action. This gem proposes a technique where the player controls navigation with the foot, keeping both hands free for other types of interaction, such as shooting, weapon selection or object manipulation.
Deferred Function Call Invocation System |
The way in which a game handles interrupt notifications can either lead to a fairly painless and bug-free experience, or to a frustrating world of head-scratching, bug-chasing hurt. This article discusses the implications of asynchronous events and other timing-related issues, and provides a system to handle them gracefully.
Multithread Job and Dependency System |
This gem puts next generation multi-core capabilities into the hands of all programmers without the need to comprehend more complex multithreading concepts to create tasks. By providing a simple system that automatically manages dependencies between tasks there is almost no need of other more specific synchronization mechanisms. The system is adapted for small to medium-sized tasks such as animation blending or particle system updates.
Advanced Debugging Techniques |
While we can not avoid that erroneous code is written, we can try to improve the process of finding and fixing these errors. If an application crashes or does something wrong, information about the crash becomes the most important data in order to find the cause of a malfunction. Therefore I want to present a small framework which detects and reports a vast number of programming errors and can be easily integrated into any existing project.
Section 2: Mathematics and Physics
This article is an introduction to random number generators (RNGs). The main goal is to present a starting point for programmers needing to make decisions about RNG choice and implementation. A second goal is to present better alternatives for the ubiquitous Mersenne Twister (MT). A final goal is to cover various classes of random number generators, providing strengths and weaknesses of each.
Fast Generic Ray Queries for Games |
Ray tracing is useful for more than just rendering. This article describes implementation details for a generic ray tracer that can be used for various parts of a game, such as line-of-sight queries, physics, and sound propagation. The focus is on efficient traversal of individual rays. The kD-tree, built using the surface area heuristic (SAH), is an efficient spatial subdivision for ray queries in a static scene. We describe some approaches to extend this algorithm to support dynamic scenery.
Fast Rigid-Body Collision Detection using Farthest Feature Maps |
This article tries to solve some of the complexities involved in the process of rigid-body collision using some acceleration data structures. We introduce a new data structure called the Farthest Feature Map that is used to accelerate the discovery of a potentially colliding set (PCS) of triangles at run-time. This algorithm, like our previous algorithm based on distance cube-maps, works only with convex rigid bodies and has a preprocessing step and a run-time step.
Using Projective Space to Improve Precision of Geometric Computations |
In order to create robust geometric algorithms that will operate correctly in every case we can't use any operations that will truncate intermediate results (e.g. operations on floating-point numbers) as truncation leads to loss of information, which under certain circumstances can be needed to obtain results. This leaves math based on integers the only way to ensure that truncation doesn't happen. The straightforward representation of points using integer Cartesian coordinates isn't the solution as the intersection of a pair of lines with endpoints with integer coordinates doesn't necessarily occur at integer coordinates. Using rational numbers can solve the problem, but this requires storing six integer values per vector (numerator and denominator for each component) and implementations of efficient operations on such vectors aren't straightforward in three dimensional space. Using projective space can reduce this number to four integers per vector by using vectors with one extra dimension and storing only a single integer per vector component, which will be demonstrated in this chapter.
XenoCollide Complex Collision Detection Made Simple |
Efficient Collision Detection using Transformation Semantics |
In this article, we show a method for inverting transformation matrices used for placing models in games and for extracting useful semantic information from them. We also show how this information can be used for implementing efficient collision detection tasks.
| |
Tony Barrera (Barrera Kristiansen AB), Anders Hast (Creative Media Lab, University of G�vle), Ewert Bengtsson (Centre For Image Analysis, Uppsala University)
Game Programming Gems 7, 2008. |
In this gem we will show how splines can be constructed that can be used to create both straight lines and perfect circle arcs. The latter is not possible with ordinary cubic splines and the trigonometric spline will make it possible to create new forms for 3D models. Furthermore, we will show that the trigonometric functions involved can be computed without the use of the sine and cosine functions in the inner loop, which enables higher performance.
Using Gaussian Randomness to Realistically Vary Projectile Paths |
Whether shooting a gun or firing off some arrows, we all have an intuitive sense of what the shot distribution on a bull's-eye target should look like. Shots will generally be peppered near the center with a few straying shots. This isn't the kind of distribution generated from rand(), but rather a special kind of randomness commonly represented by a bell curve. Fortunately there are random number generators that are capable of generating this type of Gaussian randomness. This article will discuss a very efficient Gaussian random number generator, detailing how it should be applied to simulate natural variations in the paths of projectiles.
Section 3: Artificial Intelligence
Creating Interesting Agents with Behavior Cloning |
In this gem, we will show how to use a machine learning technique called behavior cloning to borrow from styles and strategies of humans playing the game and place them into game agents.
Designing a Realistic and Unified Agent Sensing Model |
Current agent sensing models are rather primitive and there are dozens of clever ways to enhance these basic models. This article will detail many such additions, eventually combining them into a unified sensing model, since all senses should collaboratively inform an agent's awareness of the world. The final model may then be used in any genre of game as a core part of the AI.
Managing AI Algorithmic Complexity: Generic Programming Approach |
During the past seven years, TruSoft International Inc. has been focusing on the research and development of behavior-capture AI technologies. These technologies allow a new type of AI game agent to be created, that are able to learn and adapt in the way real humans do, by learning the playing styles of human players and adapting these strategies to achieve set goals. The system allows game designers to train behavior-capture AI agents directly, by sitting down with a console or a PC and playing the role of the agent to be trained. Agents can then learn tactics and strategies straight from the human controller, without the need for coding. End users are also able to train game characters using the same system, bringing traditional bot development to a whole new level. By simply playing the game, a behavior capture enabled system allows the user to create AI controlled agents that play with very distinct styles.
All About Attitude: Building Blocks for Opinion, Reputation and NPC Personalities |
Attitude systems are more appropriate for games where NPCs need to exhibit believable social behaviors toward the player and/or toward one another. These can include game genres like god games, RPGs, dating games, games about political factions or palace intrigue, espionage, and perhaps some types of RTSs. They may also be appealing for use in certain forms of serious games, e.g. games that need to simulate political processes, media or propaganda effects, or marketing campaigns. This article presents enough basic attitude theory to get started and suggests some lightweight implementations that can be used in conjunction with other parts of the AI.
Understanding Intelligence in Games using Player Traces and Interactive Player Graphs |
As the field of game AI has grown, the ability to create characters and game reactions that impart reasonable, challenging, and even insightful actions in their control has improved. However, our basic ability to describe what makes something truly seem generally intelligent has lagged behind. This gem provides some insight into a specific visualization and graph-based AI analyses mindset with some tools and techniques that forward a goal of better understanding both artificial and human intelligence in games. We show how logging player-centric game data can be used to better understand both natural and artificial player behavior through the use of visual data-mining, graph-based interaction representations, and clustering tools.
Goal-Oriented Plan Merging |
One way planners can be improved is through the use of plan merging, a technique used in several different ways under academic settings but not yet applied to games. Using plan merging can allow a broader range of behaviors for automated agents and even let them attempt to pursue multiple goals at once. This article will examine one way of implementing a plan merging system in the context of a real-time game and discuss the implications of using such a system.
Beyond A*: IDA* and Fringe Search |
While A* itself represents the most widely used algorithm, the degree of specialization and optimization of the A* algorithm for individual cases expands the set tremendously. The driving force behind algorithm selection has always been and will always be defined by memory and time constraints, and in nearly every case one must be traded for the other. IDA* and Fringe Search represent useful modifications of the A* family of algorithms and may ultimately provide advantages over traditional approaches to path-finding.
Section 4: Scripting and Data-Driven Systems
Automatic Lua Binding System |
This gem focuses on an implementation of a Lua binding. This technique allows a programmer to expose their C++ classes to Lua without any knowledge about the system. The tools presented here can apply to other languages as well. The design has been driven by usability, performance, memory footprint, and multithreading.
Serializing C++ Objects into a Database |
In this gem I will present a system which allows storage of C++ objects into an SQL database, and their retrieval using filters. The implementation and examples have been made using Postgresql 8.2 and Microsoft Visual Studio 2005.
The need for common knowledge shared between modules creates both run-time and compile-time dependencies and more dependencies means more complex code structure and longer compilation times. Dataports are a way of helping to manage this complexity by reducing compile-time dependencies and making the run-time behavior more flexible and data-driven. Dataports are a tool to help you create a more dynamic and data driven flow within your programs.
Support Your Local Artist - Adding Shaders to Your Engine |
As a developer, it is awfully tempting to just code the shaders directly into your actors. Unfortunately that approach leads to a dangerous coupling of code, art assets, and shader parameters as well as a hard-coded, inflexible solution that is averse to scaling. This gem presents a data driven design to help you incorporate shaders into your engine. This design offers good techniques for isolating most shader parameters from your actor logic. Included is a fully working implementation that can be used as the basis of a more complete solution.
In any MMORPG, there are plenty of conversations between npc and player. It takes processor time to encrypt them and costs a lot of bandwidth to transfer them. Python is a dynamic object-oriented programming language, and is widely adopted in MMORPG development. It is also powerful, and with the Python compiler package, a developer can manipulate the Abstract Syntax Tree (AST) and the process of analyzing and generating Python bytecode can be controlled at run-time. This article describes how to replace strings with numbers (ID) by manipulating the AST. This way, bandwidth and run-time costs can be saved. A tool based on this idea is given here.
Section 5: Graphics
Advanced Particle Deposition |
Reducing Cumulative Errors in Skeletal Animations |
This gem describes a simple trick to reduce the amount of cumulative error during playback of skeletal animations. It is applied during the offline processing of animation data, as part of the normal animation tool chain, and doesn't affect the size of the animation data. No changes are required in the runtime animation playback engine.
An Alternative Model for Shading of Diffuse Light for Rough Materials |
| |
Tony Barrera, Barrera Kristiansen AB, Anders Hast (Creative Media Lab, University of G�vle), Ewert Bengtsson (Centre For Image Analysis, Uppsala University)
Game Programming Gems 7, 2008. |
In this gem we will show how it is possible to improve the shading of rough materials with a rather simple shading model. We will discuss both the flattening effect, which is visible for rough materials, as well as possible methods for creating the backscattering effect.
High Performance Subdivision Surfaces |
This gem presents extensions to Loop Subdivision, blending results from numerous places and adding useful implementation details. The result is a complete set of subdivision rules for geometry, texture, and other attributes. The surfaces are suitable for terrain, characters, and any geometry used in a game. This gem also presents a general overview of methods for fast subdivision and rendering. After learning the material presented, the reader will be able to implement subdivision surfaces in a production environment in either tools or in the game engine itself.
Animating Relief Impostors using Radial Basis Functions Textures |
This gem describes a new technique for animating relief impostors based on a single multilayer relief texture using radial basis functions (RBF). The technique preserves the relief-impostor properties, allowing the viewer to observe changes in occlusion and parallax during the animation.
Graphics Clipmapping on SM1.1 and Higher |
Most games these days use decals in one way or another; for instance to show bullet marks on the environment, or to add variation on repetitive geometry. Usually this is done by rendering a transparent polygon on top of the existing geometry. This technique however has some drawbacks, especially if you want to apply bump mapping in your decals. When rendering a bump mapped decal on top of existing bump mapped geometry, the lighting is not correct, because the pixels underneath the decal should also have been lit using a combination of the decal bump map and the geometry bump map. In this gem we explain how to render decals which actually replace the bump and the diffuse map of the geometry (this can be extended to any kind of texture map you use), thereby giving correct lighting results and a higher image quality.
Mapping Large Textures for Outdoor Terrain Rendering |
Texturing highly detailed large terrain areas is a requirement in many games, especially flight simulators. Fortunately, hardware supports large textures, up to 8192 texels square. Classical techniques are based on the tiling of large textures or blending detail textures. The problem with these techniques is that, in one case, geometry must be divided into segments with borders exactly matching the texture tile boundaries and, in the other case, the appearance is repetitive, unnatural and unrealistic. This gem explains a method that allows the use of huge textures, based on clipmaps. The technique can be used with any geometry algorithm without the need to divide textures into tiles adapted to the geometry boundaries. Moreover, it allows dynamic geometry deformation.
Art Based Rendering with Graftal Imposters |
Graftals are used to express the shape and formation of plants in a formal grammar for use in computer graphics. A close relative of fractals, graftals allow for a compact representation of foliage. Graftals have also been used in a non-photorealistic cartoon rendering implementation at interactive frame rates. Graftal imposters are used as a real-time method of drawing cartoon-style plants and fur using the geometry shader in modern GPUs. The particular style we aim to produce is inspired by Dr. Seuss's children's book illustrations.
Cheap Talk: Dynamic Real-Time Lipsync |
Game developers are increasingly using lipsyncing for in-game 3D characters. One problem is getting lipsyncing up and running can be both time-consuming and expensive. A custom solution may involve valuable programmer time while a more expedient method, involving purchased middleware, can have other drawbacks. Particularly for developers wanting to experiment with lipsync, perhaps as part of a proof-of-concept demo, a quicker, less expensive solution is desirable. Fortunately, incorporating lipsyncing into a game can be done on the cheap in minimum amount of time. The result is at least adequate for a proof-of-concept and may be sufficient for a packaged game. This gem explains a method for quick and easy lipsyncing.
Section 6: Audio
Audio Signal Processing Using Programmable Graphics Hardware |
MultiStream - The Art of Writing a Next-Gen Audio Engine |
For the past 3 years, the SCEE R&D's audio team has been writing a "next gen" audio engine for the PS3 which was to be part of the official SDK. My aim for this section is, having been a part of the SCEE engine project, to give you an idea of the work involved in designing and creating your own audio engine. In turn, this information may be may be useful in allowing you to create your own audio engine, or by knowing the magnitude of the job depending on your goals, you may decide to use something from an SDK or middleware provider instead.
Listen Carefully: You Probably Won't Hear this Again - Removing Repetition from Audio Environments in Games and Discussing a New Approach to Sound Design |
The technology to create real-time variable in-game sound effects has been available for some time. These techniques can not only remove the issue of repetitive sounds, but they also allow for far more complex audio assets to exist in a game than would have generally been possible with the limited resources of some game consoles. With the advance into the newest generation of game consoles these methods can allow an audio designer to create rich audio environments featuring complex reactive and truly interactive sound and music. In this article, I will discuss the methodology behind creating these more complex and variable sound environments, as well as illustrate a need to shift our thinking as creators of audio assets.
Real-Time Audio Effects Applied |
The purpose of this gem is to outline some of the more basic fundamentals of audio processing from a high level perspective taking into account all the tips and tricks I've learned over the years in designing an audio engine for video games. Some of these tips are straightforward and others required a little more thought to work around.
Context-Driven, Layered Mixing |
This gem presents a mixing system that brings the overall sound of a game under greater human control. A similar system was used with great success in developing Scarface: The World is Yours and supported a three week final mixing session of the game at Skywalker Sound.
Section 7: Network and Multiplayer
High-Level Abstraction of Game World Synchronization |
The power of meta-programming increases productivity over writing code manually. Remote Procedure Call (RPC) is, of course, a kind of meta-programming technique. The gem this article introduces is another meta-programming technique that synchronizes game world using High Level Abstraction (HLA). RPC abstracts source code lines that exchanges messages among hosts in a few lines in the lower code layer, however, HLA abstracts them in higher layer where the messages are exchanged for synchronizing game world state, and that's why we call it high-level.
Authentication for games, where un-trusted clients connect to one or more trusted servers, is an interesting special case of general authentication. This article presents some alternatives that should be considered when designing authentication for an online game system, and proposes one particular set of internally cohesive design choices.
Game Network Debugging with Smart Packet Sniffers |
The concept of a smart packet sniffer or, perhaps better-named, game message sniffer, is the idea that you are not just looking at the raw binary data sent across the wire, or TCP/IP protocol data. You are looking at more detailed information in a human readable form. In its most basic description, we're talking about a packet sniffer that has specific knowledge of the internals of your game protocol.
|
|
|
