CGF-AI home
      News     Products     CGF-AI     Links  
 
 

 

 

 

 

AI consulting, design and development

 

 

 

 

CGF-AI provides AI consulting, AI design and development on a contract basis, primarily for first and third person perspective combat games and combat simulations.



 


 

 

 

Game Credits

 

 

 

 

William contributed to the AI for Guerrilla's Killzone (PlayStation2, 2004, published by Sony (SCEE / SCEA)) and Guerrilla's Shellshock: Nam '67 (PlayStation2, Xbox, PC, 2004, published by Eidos Interactive).



The resulting AI is described in more detail in AI Game Programming Wisdom 3 and the Game Developer Conferences 2005 proceedings (see below).


 
Killzone box cover (PAL) Shellshock: Nam '67 box cover (NTSC)


 

 

 

Publications

 

 

 

 

  • AIGameDev.com Paris game AI conference (June 11, 2009):
    Multi-Unit Planning with HTN and A*

    Abstract: HTN planners are great for problems containing hierarchy, such as planning combined arms attacks. HTN planners can be made to find a 'best' plan (rather than any plan in a depth-first search) when the planner is designed similar to an A* path-finder. An initial plan with a top-level task is expanded with more detailed tasks until the plan solely consists of primitive tasks. Methods generate multiple alternative 'successor' plans by adding those more detailed tasks. The cost of (partial) plans is estimated based on the world state recorded in a task's start and end state. Using this cost estimate, the planner takes the least cost partial plan from the collection of 'open plans' and expands this. Several heuristics are given to deal with combinatorial explosion.


    Download(s):

  • slides (.pdf, 38 slides, ~13MB)


 
AIGameDev.com Paris conference slides 'Multi-Unit Planning with HTN and A*'

 

 

  • AI Game Programming Wisdom 3 (March 2006):
    Being a Better Buddy: Interpreting the Player's Behavior (15 pages)

    Abstract: In shooter games, the player's activity can be interpreted by the AI to recognize certain tactical behaviors. Based on this, the AI can direct the friendly NPCs to better assist the player. To interpret and classify the player's activity, a naïve Bayes classifier is used. With careful design of the inputs to this classifier, some post-processing of its output, and by gathering good training data, the player's activity can be interpreted in an efficient and robust way.


    This chapter is accompanied by a sample implementation and some example training data.


    Download(s):


 
article snapshot AI Game Programming Wisdom 3

 

 

  • AI Game Programming Wisdom 3 (March 2006):
    Dynamic Procedural Combat Tactics, by Remco Straatman, Arjen Beij, William van der Sterren (15 pages)

    Abstract: Dynamic combat tactics are essential in making tactical shooters less linear and more responsive to the player and to changes in the game world. Designer placed hints for positioning and detailed scripting are impractical for games with unpredictable situations due to player freedom and dynamic environments. This article describes the techniques used to address these issues for Guerrilla's console titles Killzone and Shellshock Nam '67. The basic position evaluation mechanism is explained and its application when selecting tactical positions and finding tactical paths. Some alternative uses of the technique are given, such as generating intelligent scanning positions and suppressive fire, and the practical issues of configuration and performance are discussed.



   

 

 

  • AI Game Programming Wisdom 2 (January 2004):
    Path Lookup Tables: Small is Beautiful (13 pages)

    Abstract: The fastest way to 'find' a path from waypoint A to B is not to search. It is much faster to look up a path from a pre-computed table. Being able to find paths ten to two hundred times faster than with A* may make a big difference. This frees up CPU budget for other AI decisions. It allows the use of paths and travel times in a much larger portion of the AI's reasoning. However, path lookup tables are not without disadvantages. The amount of memory required for the tables often prohibit their use for anything other than small levels.


    This chapter discusses optimizations of path lookup tables, and take a look at two designs that offer the performance benefits at lower costs. First, a path lookup matrix using indices that consumes only one fourth of traditional path lookup tables. Second, an area based path lookup table which consumes even less, and scales much better, at the costs of a more complex lookup.

    This chapter is accompanied by the LUT Explorer, a small GUI based application created to demonstrate area-based path lookup and test the implementation of the LUT based path-lookup algorithms.


    Download(s):


 
article snapshot AI Game Programming Wisdom 2

 

 

  • Game Programming Gems 3 (August 2002):
    Tactical Path-Finding with A* (15 pages)

    Abstract: Tactical paths consider cover and stealth in addition to travel time. Although costs for cover and stealth are easily added to the A* cost function, this alone does not result in convincing tactical paths. This chapter analyzes the defects in these paths, and discusses tactical improvements: taking into account exposure time and enemy aiming behavior, and anticipating likely enemy movement.
    The extensions to the A* cost functions introduce additional run-time costs. This chapter discusses these costs, and provides work-arounds and optimizations to make tactical pathfinding more efficient.

    This gem is accompanied by a version of James Mathews' "A* Explorer", modified to allow the reader to experiment with all the examples (and more tactical path-finding).


    Download(s):


 
gem snapshot

 

 

 

  • AI Game Programming Wisdom (March 2002):
    Squad Tactics: Team AI and Emergent Maneuvers (15 pages)

    Abstract: AI squad behavior is made up of coordinated individual actions towards a joint goal. There are two basic coordination styles: centralized control by a leader, and decentralized cooperation between individuals. This chapter discusses the latter style in detail. Decentralized cooperation can already be realized with minor changes to "standard individual AI".

    This chapter illustrates how some tactical squad maneuvers can emerge from these coordinating individual AIs, using a squad assault as an example. The limitations of the approach are illustrated using a second example: a squad ambush. This chapter precedes and complements the chapter "Squad Tactics: Planned Maneuvers".


 
gem snapshot AI Programming Wisdom cover image

 

 

 

  • AI Programming Wisdom (March 2002):
    Squad Tactics: Planned Maneuvers (14 pages)

    Abstract: AI squad behavior can also be realized by designing an explicit team leader, responsible for planning and managing the squad's maneuver. This AI team leader assesses the squad's state, picks and plans the most appropriate squad maneuver. He executes the squad maneuver by issuing orders, and by interpreting feedback and information from the squad members. This is illustrated using a bounding overwatch squad advance.

    This centralized style to squad AI is more complex than the emergent behavior in "Squad Tactics: Team AI and Emergent Maneuvers". However, it does provide largely autonomous operating squads, able to execute complex maneuvers, and often combines well with some decentralized cooperation among squad members.



 
gem snapshot  

 

 

 

  • Game Programming Gems 2 (August 2001):
    Terrain Analysis for 3D Action Games (x pages)

    Abstract: Terrain reasoning in 3D action games is about understanding concepts such as stronghold, cover, ambush, and sniper location. This chapter introduces a simple yet powerful approach for terrain reasoning, enabling the AI itself to compute these concepts. Traditionally, AI relies on hints and scripts manually added by level designers to grasp the terrain. However, an AI that actually understands the terrain will respond better to dynamic situations and directions issued by the player. The terrain reasoning presented uses a waypoint graph with a high spatial density of waypoints. Due to its density, it is a good abstraction of the terrain. Being a graph, it enables computations. The chapter explains how to express terrain concepts in terms of this graph.



 
gem snapshot

 

 

 

Presentations

 

 

 

 

  • Game Developer Conference 2005 lecture (March 2005):
    Killzone’s AI : Dynamic Procedural Combat Tactics

    Abstract:

    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.


    Note: this talk was presented together with Arjen Beij of Guerrilla, and represents work to which also Remco Straatman and Robert Morcus (both of Guerrilla) heavily contributed.


    Audience feedback (all feedback from the evaluation forms): "Very comprehensive and valuable. Practical implementation techniques were presented. Thank you! GDC needs more of these technically thorough presentations. Too little preparation, good talk otherwise. It really was a good presentation. The 5's are on purpose. Methodical presentation = good nice, hands-on feel pace was slow to my taste not so much new material. Good demos, 3rd person view vs overhead is nice to use. Beautiful programming session - clear, concise, and very interesting. Very well organised + focused talk. Excellent movies: speakers took time with language and details. Very informative. 4 Demos were very good! Well presented, cohesive. Well paced for the amount of content. Good! Easy to understand. Very cool talk. Glad I attended. The visuals, demos, diagrams were great, really clear and easy to understand. I'm going to go buy Killzone now so I can see more of this." (Overall rating 4.3/5)


    Download(s):

    • 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)


 
GDC2005 archive
GDC2005 slides
GDC2005 paper
 

 

 

  • Game Developer Conference 2001 lecture (March 2001):
    Terrain Reasoning for 3D Action Games

    Abstract:

    Terrain reasoning in 3D action games is about understanding concepts such as stronghold, cover, ambush, and sniper location. This lecture introduces a simple yet powerful approach for terrain reasoning, enabling the AI itself to compute these concepts. Traditionally, the AI relies on hints and scripts manually added by level designers to 'grasp' the terrain. However, an AI actually understanding the terrain will better respond to dynamic situations and directions issued by the player.


    The terrain reasoning presented uses a waypoint graph with a high spatial density of way points. Due to its density, it is a good abstraction of the terrain. Being a graph, it enables computations. The lecture shows numerous examples of how to express terrain concepts in terms of this graph. A case study illustrates how situational awareness, team maneuvers, tactical path finding, and adaptive tactics are implemented using both in-game and pre-game terrain reasoning.


    "[William] made an impressive presentation that built upon many of those [AI battlefield analysis] techniques within a Quake-II environment to build a sniper-based game that was uncanny in its ability to select the perfect place for an ambush".
    Game Developer Magazine, August 2001, "Game AI: The State of the Industry (2000-2001)", by Steven Woodcock

    "Van der Sterren presented a practical implementation of Influence Mapping in conjunction with Terrain Waypoint Meshes to produce an effective terrain analysis module.
    His indepth presentation offered detailed formulas and explanations of the strengths and weaknesses of the evaluation techniques in use, and the steps the module took. And the direct application of these methods with an example that most AI programmers can relate to made it much easier to understand the points [William] was making."

    Gamasutra: "Game Developers Conference 2001: An AI Perspective", by Eric Dybsand


    Download(s):


 
2001 Game Developer Conference
terrain reasoning: sniper spots towards east [click to see larger image]
 

 

 


  slides presented at IDGA meeting (1.4MB .pdf)


 

 

 

Downloads

 

 

 

 

  • Behavior Classifier:

    This download contains source code for a naïve Bayes classifier to interpreter tagged player behavior, along with some example data.


    The Behavior Classifier accompanies the AI Game Programming Wisdom 3 chapter "Being a Better Buddy: Interpreting the Player's Behavior".


    Download(s):







  Interpreted behavior (spreadsheet)

  • Path Look Up Table (LUT) Explorer:

    The value of path look-up tables is in their speed, with path lookup 50 to 100 times faster than an optimized A*. The downsides of path lookup tables are their memory consumption, their static nature and the limited ability to handle game unit variations such as movement capabilities and dimensions.


    LUT Explorer is a small GUI based application created to:

    • interactively demonstrate area-based path lookup;

    • test the implementation of the LUT based path-lookup algorithms;

    • compare memory consumption of the LUTs for various (user-created) maps;

    • experiment with closing portals for the area-based LUT;

    The LUT Explorer accompanies the AI Game Programming Wisdom 2 chapter "Path Lookup Tables: Small is Beautiful".


    Download(s):







  LUT Explorer screenshot

  • Tactical A* Explorer:

    As an experiment with tactical path-finding, we invite you to play with the A Star Explorer (ASE) application. James Matthews laid the foundation for this A* tool. The tactical enhancements and line-of-fire approximation described in the Game Programming Gems III article have been added.

    Note that the A* implementation in this ASE is not representative of a high-performance tactical A*. Instead, the algorithm has been designed for hosting alternative cost functions and for visualization.


    Download(s):



  Tactical A* Explorer screenshot