Artificial Intelligence for Games by Ian Millington and John Funge

Kindle Print Replica

August 6, 2009
Publisher: CRC Press
ISBN: 978-0123747310

From the Amazon website

Creating robust artificial intelligence is one of the greatest challenges for game developers, yet the commercial success of a game is often dependent upon the quality of the AI. In this book, Ian Millington brings extensive professional experience to the problem of improving the quality of AI in games. He describes numerous examples from real games and explores the underlying ideas through detailed case studies. He goes further to introduce many techniques little used by developers today. The book's associated web site contains a library of C++ source code and demonstration programs, and a complete commercial source code library of AI algorithms and techniques.

 

"Artificial Intelligence for Games - 2nd edition" will be highly useful to academics teaching courses on game AI, in that it includes exercises with each chapter. Book website www.ai4g.com contains a platform-agnostic library of well structured and commented source code in C++. The executables use the basic source code for each technique and are designed to run in Windows.

Contents

1. Introduction

  • Academic AI / Game AI
  • Model of Game AI: Movement, Decision Making, Strategy, Infrastructure, Agent-Based AI
  • Algorithms, Data Structures, and Representations: Algorithms, Representations.

2. Game AI

  • The Complexity Fallacy
  • The Kind of AI in Games: Hacks, Heuristics, Algorithms
  • Speed and Memory: Processor Issues, Memory Concerns, PC Constraints, Console Constraints
  • The AI Engine: Structure of an AI Engine, Toolchain Concerns

3. Movement

  • The Basics of Movement Algorithms: Two-Dimensional Movement, Statics, Kinematics
  • Kinematic Movement Algorithms: Seek, Wandering
  • Steering Behaviors: Steering Basics, Variable Matching, Seek and Flee, Arrive, Align, Velocity Matching, Delegated Behaviors, Pursue and Evade, Face, Looking Where You're Going, Wander, Path Following, Separation, Collision Avoidance, Obstacle and Wall Avoidance
  • Combining Steering Behaviors: Blending and Arbitration, Weighted Blending, Priorities, Cooperative Arbitration, Steering Pipeline
  • Predicting Physics: Aiming and Shooting, Projectile Trajectory, The Firing Solution, Projectiles with Drag, Iterative Targeting
  • Jumping: Jump Points, Landing Pads, Hole Fillers
  • Coordinated Movement: Fixed Formations, Scalable Formations, Emergent Formations, Two-Level Formation Steering, Implementation, Extending to More than Two Levels, Slot Roles and Better Assignment, Slot Assignment, Dynamic Slots and Plays, Tactical Movement
  • Motor Control: Output Filtering, Capability-Sensitive Steering, Common Actuation Properties
  • Movement in the Third Dimension: Rotation, Converting Steering Behaviors to 3D, Align, Align to Vector, Face, Look Where You're Going, Wander, Faking Rotation Axes

4. Pathfinding

  • The Pathfinding  Graph: Graphs, Weighted Graphs, Directed Weighted Graphs, Terminology, Representation
  • Dijkstra: The Problem, The Algorithm, Pseudo-Code, Data Structures and Interfaces, Performance, Weaknesses
  • A*: The Problem, The Algorithm, Pseudo-Code, Data Structures and Interfaces, Implementation, Performance, Node Array A*, Choosing a Heuristic
  • World Representations: Tile Graphs, Dirichlet Domains, Points of Visibility, Navigation Meshes, Non-Translational Problems, Cost Functions, Path Smoothing
  • Improving on A*
  • Hierarchical Pathfinding: The Hierarchical Pathfinding Graph, Pathfinding on the Hierarchical Graph, Hierarchical Pathfinding on Exclusions, Strange Effects of Hierarchies on Pathfinding, Instanced Geometry
  • Other Ideas on Pathfinding: Open Goal Pathfinding, Dynamic Pathfinding, Other Kinds of Information Reuse, Low Memory Algorithms, Interruptible Pathfinding, Pooling Planners
  • Continuous Time Pathfinding: The Problem, The Algorithm, Implementation Notes, Performance, Weaknesses
  • Movement Planning: Animations, Movement Planning, Example, Footfalls
  • Exercises

5. Decision Making

  • Overview of Decision Making
  • Decision Trees
  • State Machines
  • Behavior Trees
  • Fuzzy Logic
  • Markov Systems
  • Goal-Oriented Behavior
  • Rule-Based Systems
  • Blackboard Architectures
  • Scripting
  • Action Execution

6. Tactical and Strategic AI

  • Waypoint Tactics
  • Tactical Analyses
  • Tactical Pathfinding
  • Coordinated Action

7. Learning

  • Learning Basics
  • Parameter Modification
  • Action Prediction
  • Decision Learning
  • Naive Bayes Classifiers
  • Decision Tree Learning
  • Reinforcement Learning
  • Artificial Neural Networks

8. Board Games

  • Game Theory
  • Minimaxing
  • Transposition Tables and Memory
  • Memory-Enhanced Test Algorithms
  • Opening Books and Other Set Plays
  • Further Optimizations
  • Turn-Based Strategy Games

9. Execution Management

  • Scheduling
  • Anytime Algorithms
  • Level of Detail

10. World Interfacing

  • Communication
  • Getting Knowledge Efficiently
  • Event Managers
  • Polling Stations
  • Sense Management

11. Tools and Content Creation

  • Knowledge for Pathfinding and Waypoint Tactics
  • Knowledge for Movement
  • Knowledge for Decision Making
  • The Toolchain

12. Designing Game AI

  • The Design
  • Shooters
  • Driving
  • Real-Time Strategy
  • Sports
  • Turn-Based Strategy Games

13. AI-Based Game Genres

  • Teaching Characters
  • Flocking and Herding Games

Notes

  • Search and knowledge are intrinsically linked: the more knowledge you have, the less searching for an answer you need; the faster you can search, the less knowledge you need.
  • AI has three sections: movement, decision making, and strategy. Movement and decision making are described by algorithms that work on a character-by-character basis. Strategy operates on a whole team or side.
  • Movement refers to algorithms that turn decisions into motion.
  • Decision making involves a character working out what to do next.
  • Strategy refers to an overall approach used by a group of characters.
  • AI requires infrastructure: animation, physics simulation, world interfacing, etc.
  • Agent-based AI is a bottom-up design: you work out how each character behave and implement the AI needed to support that. The overall behavior of the game is a function of behaviours of individual characters. Non-agent based AI builds a single system to simulate everything.
  • Whenever a character in a game changes behavior, the change is far more noticeable than the behavior itself.
  • The kind of AI in games: hacks (ad hoc solutions involving random numbers, animation, etc.), heuristics (rules of thumb that work in most, but not all, cases), algorithms.
  • Complex AI sometimes needs to be split into components distributed over multiple frames.
  • AI can take advantage of multi-core processing and hyper-threading by running AI for different characters in different threads.
  • Indirect functions (such as virtual functions) may negatively influence the branch predictor on the processor. Indirect function calls are typically much more costly than direct function calls.
  • Performance improvement: keep all data for one algorithm in the same place. This way the processor can fetch a whole chunk of memory into the cache. For example, it may be better to keep positions of all characters together in an array.
  • Movement algorithms output a desired velocity.
  • Kinematic movement has two speeds: stationary and running/walking.
  • Dynamic movement takes account of the current motion of the character. It outputs forces or accelerations.