GDC2005 lecture: Killzone’s AI : Dynamic Procedural Combat Tactics February 21, 2005

Arjen Beij (of Guerrilla Games) and William van der Sterren (CGF-AI) will discuss Killzone's AI in more detail at the upcoming Game Developer Conference, March 7-11 in San Francisco. In their lecture, Arjen and William show how the Killzone's AI behaves tactically as a result of a simple position evaluation technique that is capable of responding to many simultaneous static and dynamic inputs. (Guerrilla Games' Remco Straatman and Robert Morcus also were involved in the work presented). Killzone’s AI : Dynamic Procedural Combat Tactics Dynamic combat tactics are essential in making tactical shooters less linear and more responsive to the player and to changes in the game world. We have taken position evaluation techniques similar to those used in traditional games such as Chess and Go, and apply them on-the-fly in our console based tactical shooters. We use this procedural approach to create wide variety of individual and squad tactics and maneuvers. This enables the AI to react appropriately to any approach the player or other NPCs take, and to changes in the game world. Furthermore, because this AI does not rely on designer placed hints, the AI can apply these tactics anywhere in the game world. This talk discusses techniques and experiences in creating the dynamic combat AI in Guerrilla's Killzone and Shellshock Nam '67. We explain the basic dynamic position evaluation mechanism and the specific properties used to distinguish a wide range of situations and tactics. Then we discuss how to use position evaluation to select tactical positions, predict positions of out-of-sight threats, use grenades, select suppressive fire targets, and perform tactical path finding. We explain how to implement efficient dynamic combat AI by off-loading a considerable part of the required ray casts to a small amount of pre-calculated terrain information. This talk concludes with our experiences, both good and bad, in realizing a game with dynamic combat AI. The lecture is scheduled for March 10, 5:30pm-6:30pm. Materials: proceedings paper (.pdf, 18 pages, ~1.8MB) slides (.pdf, 44p, ~8.1MB, without the movies referred in slides 17, 24 and 34) slides (Macromedia Flash.swf, 44p, ~0.9MB, opens on separate page)

Tactical A* Pathfinding December 31, 2003

Here are some illustrations of tactical pathfinding using A* (as described in the Game Programming Gems III book). A tactical path deviates from the shortest path to achieve increased concealement and cover from threats. The simple way to create tactical paths is adding a new cost to the A* cost function. These new costs reflect exposure to enemy observation and fire at each point in the terrain. In the figures 1 and 2 below, a map is populated with 5 threats (dark yellow squares), each having 360 degrees line-of-fire to their immediate surroundings (indicated in pale yellow). The path is illustrated by a continuous line, and runs from the red to the green solid square. Figure 1 illustrates a shortest path. Figure 2 shows a path taking a few detours to reduce the exposure to hostile lines-of-fire. You can experiment yourself with these maps and tactical cost function settings by downloading the enhanced A* Explorer (based on James Matthews' original A* Explorer). Fig 1. Traditional shortest path (and search space) Fig 2. Tactical path balancing cover and travel costs Figure 1 is created with figure1.ase (in the ase\Examples folder) and the following settings: movement type=diagonal, movement costs=vector, threat costs=none. Figure 2 use the same settings but adds: threat costs=line of fire, assumed threat movement=2 cells. Adding just a cost function to deal with cover and concealment is trivial. However, adding a good cost function is hard. First of all, evaluating lines-of-fire often is costly, because it requires ray-casting or a large look-up table. Additionally, the resulting path is often very sensitive to any threat movement (which is bound to happen in most action games). Figure 3 illustrates the path resulting from exact line-of-fire calculations under the assumption that all threats are known and remain static during the journey along the path. Although the path cleverly visits the protection of the obstacles in the center, it relies on the exact position of the threats during the first and third quart of the path (from the red to the green square). Computing the path again after moving a single threat just one cell is likely to result in a radically different path. Figure 4 shows a different path for the same situation. This time, the path is created using a coarse and efficient approximation of the line-of-fire: for each cell and for several radial sectors (8), we pre-compute the maximum distance from which a threat in that sector still can see the AI agent in that cell. This approximation consumes only a handful of bytes per cell (in contrast to the NxN table required to represent exact lines-of-fire), and is very efficient to lookup (in contrast to actual ray casting). And because the approximation takes into account a larger number potential threat positions (namely, all possible threat positions within that radial sector), it doesn't suffer as much from the assumption that threats are static. Fig 3. Tactical path using exact line-of-fire and static threats Fig 4. Tactical path using approximate and cheap line-of-fire Figure 3 was created with figure2.ase (in the ase\Examples folder) and the following settings: movement type=diagonal, movement costs=vector, threat costs=line of fire, assumed threat movement=none. For figure 4, the settings from figure 3 adjusted as follows: threat costs=use approximated lines-of-fire from table. Fig 5. Screenshot of Tactical A* Explorer options You're invited to experiment yourself with the consequences of threat placement and the various options for the tactical A* pathfinder using the enhanced A* Explorer, available for download with examples and C++ source code. A more elaborate description is available in Game Programming Gems III.

Squad Tactics contribution to 'Game AI Programming Wisdom' book October 1, 2001       I have been contributing to the upcoming AI Game Programming Wisdom book. This book, providing over 600+ pages devoted to game AI, will appear in Spring 2002. In two chapters I sketched AI for squad tactics and maneuvers. One chapter discusses 'emergent squad tactics', a small step up from conventional individual AI that enables the kind of squad behavior that made Half-Life famous. The second chapter discusses 'planned squad tactics' in which a squad level AI plans and directs complex squad maneuvers (such as a bounding overwatch pullback drill). As one of contributors, I had the opportunity to review a number of the other chapters. These chapters really impressed me: they provide clear guidance and plenty of techniques to deal with many of the problems in developing advanced game AI. William

Game Programming Gems II now shipping! August 08, 2001       The Game Programming Gems II book is now available, including a chapter on "terrain reasoning for 3D action games" by William. This second book in the Game Programming Gems range provides another invaluable 'toolbox' of gems, this time covering more advanced material. Specifically, Gems II contains the following 14 chapters on AI: AI Overall / Architecture Strategies for Optimizing AI - Steve Rabin Micro-Threads for Game Object AI - Bruce Dawson Managing AI with Micro-Threads - Simon Carter RTS and Terrain Reasoning An Architecture for RTS Command Queueing - Steve Rabin A High Performance Tile-base Line-of-Sight and Search system - Matt Pritchard Influence Mapping - Paul Tozour Strategic Assessment Techniques - Paul Tozour Terrain Reasoning for 3D Action Games - William van der Sterren Pathfinding and Flocking Expanded Geometry for Points-of-Visibility Pathfinding - Thomas Young Optimizing Points-of-Visibility Pathfinding - Thomas Young Flocking with Teeth: Predators and Prey - Steven Woodcock Advanced Topics made Practical A Generic Fuzzy State Machine in C++ - Eric Dybsand Imploding Combinatorial Explosion in a Fuzzy System - Michael Zarozinski Using Neural Networks in AI: A Concrete Example - John Manslow

Slides from IGDA Meeting available June 01, 2001       The slides William presented at the IGDA Amsterdam chapter meeting (mentioned below) are now available here (1.3MB pdf).

IGDA Amsterdam chapter presentation May 29, 2001       The third IGDA Amsterdam chapter meeting, May 31, in Houten, will host two presentations. One presentation addresses Maya4 by Mark Cass and Tom Kluyskens of Alias|Wavefront (with some insights in it's use in the development of Tombraider 4).   The other presentation will be William's GDC talk. William will present some highlights of his GDC presentation on terrain reasoning for 3D action games: how does the game AI interpret its surroundings? how to relate tactics and terrain understanding? how to implement terrain understanding? In addition, William presents some of his experiences from the Game Developer Conference.

GDC Paper Available On-line + Links Updated May 29, 2001       The Game Developer Conference web site is now providing access to the majority of the GDC2001 papers. You can also find William's paper "Terrain Reasoning for 3D Action Games" at their site (as an 18 page 1.3 MB .pdf file).     Additionally, this site's "Links" page has been extended with links to a number of recent papers and presentations that address (game) AI, teams, tactics, and terrain reasoning.   In addition to the above mentioned Game Developer Conference, the 2001 Conference on Computer Generated Forces & Behavioral Representation (aka the CGF-BR Conference) also provides a good number of interesting publications on tactical AI.

Slides GDC Presentation Available March 27, 2001       I've made available the slides of my talk on "Terrain Reasoning for 3D Action Games" at the Game Developer Conference 2001. You'll find the 100 slides, including most of the session's questions and answers, here (1.3MB pdf file).

Cancelled Presentation at IGDA Amsterdam Chapter Meeting March 27, 2001       The arrival of our baby-daughter turns me into a daddy. She arrived yesterday "feature complete", but three weeks earlier than expected. I'm now working hard to provide her (and her mother) the care and attention they need.   The flip-side of all this happy news is that I won't be able to provide the IGDA presentation scheduled for this Thursday. Most likely, I'll give the presentation at some later date.