O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Artificial Intelligence for Games, 2nd Edition

Book Description

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. It will also include new and expanded coverage of the following: AI-oriented gameplay; Behavior driven AI; Casual games (puzzle games).

Table of Contents

  1. Preliminaries
  2. Dedication
  3. About the Authors
  4. Acknowledgments
    1. Changes to the second edition
  5. Preface
  6. About the Website
  7. Part I AI and Games
    1. Chapter 1 Introduction
      1. 1.1 What Is AI?
        1. 1.1.1 Academic AI
          1. The Early Days
          2. The Symbolic Era
          3. The Modern Era
          4. Engineering
        2. 1.1.2 Game AI
      2. 1.2 Model of Game AI
        1. 1.2.1 Movement
        2. 1.2.2 Decision Making
        3. 1.2.3 Strategy
        4. 1.2.4 Infrastructure
        5. 1.2.5 Agent-Based AI
        6. 1.2.6 In the Book
      3. 1.3 Algorithms, Data Structures, and Representations
        1. 1.3.1 Algorithms
          1. Performance Characteristics
          2. Pseudo-Code
        2. 1.3.2 Representations
      4. 1.4 On the Website
        1. 1.4.1 Programs
        2. 1.4.2 Libraries
          1. Optimizations
          2. Rendering and Maths
          3. Updating the Code
      5. 1.5 Layout of the Book
      1. Figure 1.1
    2. Chapter 2 Game AI
      1. 2.1 The Complexity Fallacy
        1. 2.1.1 When Simple Things Look Good
        2. 2.1.2 When Complex Things Look Bad
        3. 2.1.3 The Perception Window
        4. 2.1.4 Changes of Behavior
      2. 2.2 The Kind of AI in Games
        1. 2.2.1 Hacks
        2. 2.2.2 Heuristics
          1. Common Heuristics
            1. Most Constrained
            2. Do the Most Difficult Thing First
            3. Try the Most Promising Thing First
        3. 2.2.3 Algorithms
      3. 2.3 Speed and Memory
        1. 2.3.1 Processor Issues
          1. SIMD
          2. Multi-Core Processing and Hyper-Threading
          3. Virtual Functions/Indirection
        2. 2.3.2 Memory Concerns
          1. Cache
        3. 2.3.3 PC Constraints
        4. 2.3.4 Console Constraints
          1. Working with Rendering Hardware
          2. Handheld Consoles
      4. 2.4 The AI Engine
        1. 2.4.1 Structure of an AI Engine
        2. 2.4.2 Toolchain Concerns
        3. 2.4.3 Putting It All Together
      1. Figure 2.1
      2. Figure 2.2
  8. Part II Techniques
    1. Chapter 3 Movement
      1. 3.1 The Basics of Movement Algorithms
        1. 3.1.1 Two-Dimensional Movement
          1. Characters as Points
        2. 3.1.2 Statics
          1. ½ Dimensions
          2. Math
        3. 3.1.3 Kinematics
          1. Independent Facing
          2. Updating Position and Orientation
          3. Variable Frame Rates
          4. Forces and Actuation
      2. 3.2 Kinematic Movement Algorithms
        1. 3.2.1 Seek
          1. Data Structures and Interfaces
          2. Performance
          3. Flee
          4. Arriving
        2. 3.2.2 Wandering
          1. Pseudo-Code
          2. Data Structures
          3. Implementation Notes
        3. 3.2.3 On the Website
      3. 3.3 Steering Behaviors
        1. 3.3.1 Steering Basics
        2. 3.3.2 Variable Matching
        3. 3.3.3 Seek and Flee
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Performance
          4. Flee
          5. On the Website
        4. 3.3.4 Arrive
          1. Pseudo-Code
          2. Performance
          3. Implementation Notes
          4. Leave
        5. 3.3.5 Align
          1. Pseudo-Code
          2. Implementation Notes
          3. Performance
          4. The Opposite
        6. 3.3.6 Velocity Matching
          1. Pseudo-Code
          2. Performance
        7. 3.3.7 Delegated Behaviors
        8. 3.3.8 Pursue and Evade
          1. Pseudo-Code
          2. Implementation Notes
          3. Performance
          4. Evade
          5. Overshooting
        9. 3.3.9 Face
          1. Pseudo-Code
        10. 3.3.10 Looking Where You’re Going
          1. Pseudo-Code
          2. Implementation Notes
          3. Performance
        11. 3.3.11 Wander
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Performance
        12. 3.3.12 Path Following
          1. Pseudo-Code
          2. Data Structures and Interfaces
            1. Path Types
            2. Keeping Track of the Parameter
          3. Performance
        13. 3.3.13 Separation
          1. Pseudo-Code
          2. Implementation Notes
          3. Performance
          4. Attraction
          5. Independence
        14. 3.3.14 Collision Avoidance
          1. Pseudo-Code
          2. Performance
        15. 3.3.15 Obstacle and Wall Avoidance
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Performance
          4. Collision Detection Problems
            1. The Corner Trap
        16. 3.3.16 Summary
      4. 3.4 Combining Steering Behaviors
        1. 3.4.1 Blending and Arbitration
        2. 3.4.2 Weighted Blending
          1. The Algorithm
          2. Pseudo-Code
          3. Data Structures
          4. Performance
          5. Flocking and Swarming
          6. On the Website
          7. Problems
            1. Stable Equilibria
            2. Constrained Environments
            3. Nearsightedness
        3. 3.4.3 Priorities
          1. The Algorithm
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Implementation Notes
          5. On the Website
          6. Performance
          7. Equilibria Fallback
          8. Weaknesses
          9. Variable Priorities
        4. 3.4.4 Cooperative Arbitration
        5. 3.4.5 Steering Pipeline
          1. Algorithm
            1. Targeters
            2. Decomposers
            3. Constraints
            4. The Actuator
          2. Pseudo-Code
          3. Data Structures and Interfaces
            1. Targeter
            2. Decomposer
            3. Constraint
            4. Actuator
            5. Deadlock
            6. Goal
            7. Paths
          4. Performance
          5. On the Website
          6. Example Components
            1. Targeter
            2. Decomposer
            3. Constraint
          7. Conclusion
      5. 3.5 Predicting Physics
        1. 3.5.1 Aiming and Shooting
        2. 3.5.2 Projectile Trajectory
          1. Predicting a Landing Spot
        3. 3.5.3 The Firing Solution
        4. 3.5.4 Projectiles with Drag
          1. Rotating and Lift
        5. 3.5.5 Iterative Targeting
          1. The Problem
          2. The Algorithm
          3. Pseudo-Code
          4. Data Structures and Interfaces
          5. Performance
          6. Iterative Targeting without Motion Equations
          7. Other Uses of Prediction
      6. 3.6 Jumping
        1. 3.6.1 Jump Points
          1. Achieving the Jump
          2. Weaknesses
        2. 3.6.2 Landing Pads
          1. The Trajectory Calculation
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Implementation Notes
          5. Performance
          6. Jump Links
        3. 3.6.3 Hole Fillers
      7. 3.7 Coordinated Movement
        1. 3.7.1 Fixed Formations
        2. 3.7.2 Scalable Formations
        3. 3.7.3 Emergent Formations
        4. 3.7.4 Two-Level Formation Steering
          1. Removing the Leader
          2. Moderating the Formation Movement
          3. Drift
        5. 3.7.5 Implementation
          1. Data Structures and Interfaces
          2. Implementation Caveats
          3. Performance
          4. Sample Formation Pattern
        6. 3.7.6 Extending to More than Two Levels
        7. 3.7.7 Slot Roles and Better Assignment
          1. Hard and Soft Roles
        8. 3.7.8 Slot Assignment
          1. Generalized Slot Costs
          2. Implementation
          3. Data Structures and Interfaces
          4. Performance
        9. 3.7.9 Dynamic Slots and Plays
        10. 3.7.10 Tactical Movement
          1. Tactical Motion and Anchor Point Moderation
      8. 3.8 Motor Control
        1. 3.8.1 Output Filtering
        2. 3.8.2 Capability-Sensitive Steering
          1. Coping with Combined Steering Behaviors
        3. 3.8.3 Common Actuation Properties
          1. Human Characters
          2. Cars and Motorbikes
          3. Tracked Vehicles (Tanks)
      9. 3.9 Movement in the Third Dimension
        1. 3.9.1 Rotation in Three Dimensions
        2. 3.9.2 Converting Steering Behaviors to Three Dimensions
          1. Linear Steering Behaviors in Three Dimensions
          2. Angular Steering Behaviors in Three Dimensions
        3. 3.9.3 Align
        4. 3.9.4 Align to Vector
        5. 3.9.5 Face
        6. 3.9.6 Look Where You’re Going
        7. 3.9.7 Wander
        8. 3.9.8 Faking Rotation Axes
          1. The Algorithm
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Implementation Notes
          5. Performance
      10. Exercises
      1. Figure 3.1
      2. Figure 3.2
      3. Figure 3.3
      4. Figure 3.4
      5. Figure 3.5
      6. Figure 3.6
      7. Figure 3.7
      8. Figure 3.8
      9. Figure 3.9
      10. Figure 3.10
      11. Figure 3.11
      12. Figure 3.12
      13. Figure 3.13
      14. Figure 3.14
      15. Figure 3.15
      16. Figure 3.16
      17. Figure 3.17
      18. Figure 3.18
      19. Figure 3.19
      20. Figure 3.20
      21. Figure 3.21
      22. Figure 3.22
      23. Figure 3.23
      24. Figure 3.24
      25. Figure 3.25
      26. Figure 3.26
      27. Figure 3.27
      28. Figure 3.28
      29. Figure 3.29
      30. Figure 3.30
      31. Figure 3.31
      32. Figure 3.32
      33. Figure 3.33
      34. Figure 3.34
      35. Figure 3.35
      36. Figure 3.36
      37. Figure 3.37
      38. Figure 3.38
      39. Figure 3.39
      40. Figure 3.40
      41. Figure 3.41
      42. Figure 3.42
      43. Figure 3.43
      44. Figure 3.44
      45. Figure 3.45
      46. Figure 3.46
      47. Figure 3.47
      48. Figure 3.48
      49. Figure 3.49
      50. Figure 3.50
      51. Figure 3.51
      52. Figure 3.52
      53. Figure 3.53
      54. Figure 3.54
      55. Figure 3.55
      56. Figure 3.56
      57. Figure 3.57
      58. Figure 3.58
      59. Figure 3.59
      60. Figure 3.60
      61. Figure 3.61
      62. Figure 3.62
      63. Figure 3.63
      64. Figure 3.64
      65. Figure 3.65
      66. Figure 3.66
      67. Figure 3.67
      68. Figure 3.68
      69. Figure 3.69
      70. Figure 3.70
      71. Figure 3.71
      72. Figure 3.72
      73. Figure 3.73
    2. Chapter 4 Pathfinding
      1. 4.1 The Pathfinding Graph
        1. 4.1.1 Graphs
        2. 4.1.2 Weighted Graphs
          1. Representative Points in a Region
          2. The Non-Negative Constraint
        3. 4.1.3 Directed Weighted Graphs
        4. 4.1.4 Terminology
        5. 4.1.5 Representation
      2. 4.2 Dijkstra
        1. 4.2.1 The Problem
        2. 4.2.2 The Algorithm
          1. Processing the Current Node
          2. The Node Lists
          3. Calculating Cost-So-Far for Open and Closed Nodes
          4. Terminating the Algorithm
          5. Retrieving the Path
        3. 4.2.3 Pseudo-Code
          1. Other Functions
        4. 4.2.4 Data Structures and Interfaces
          1. Simple List
          2. Pathfinding List
          3. Graph
        5. 4.2.5 Performance of Dijkstra
        6. 4.2.6 Weaknesses
      3. 4.3 A*
        1. 4.3.1 The Problem
        2. 4.3.2 The Algorithm
          1. Processing the Current Node
          2. The Node Lists
          3. Calculating Cost-So-Far for Open and Closed Nodes
          4. Terminating the Algorithm
          5. Retrieving the Path
        3. 4.3.3 Pseudo-Code
          1. Changes from Dijkstra
        4. 4.3.4 Data Structures and Interfaces
          1. Pathfinding List
            1. Priority Queues
            2. Priority Heaps
            3. Bucketed Priority Queues
            4. Implementations
          2. Heuristic Function
            1. A Heuristic for Any Goal
            2. Heuristic Speed
        5. 4.3.5 Implementation Notes
        6. 4.3.6 Algorithm Performance
        7. 4.3.7 Node Array A*
          1. Keeping a Node Array
          2. Checking if a Node Is in Open or Closed
            1. The Closed List Is Irrelevant
          3. The Open List Implementation
          4. A Variation for Large Graphs
        8. 4.3.8 Choosing a Heuristic
          1. Underestimating Heuristics
          2. Overestimating Heuristics
          3. Euclidean Distance
          4. Cluster Heuristic
          5. Fill Patterns in A*
          6. Quality of Heuristics
          7. Dijkstra Is A*
      4. 4.4 World Representations
          1. Quantization and Localization
          2. Generation
          3. Validity
        1. 4.4.1 Tile Graphs
          1. Division Scheme
          2. Quantization and Localization
          3. Generation
          4. Validity
          5. Usefulness
        2. 4.4.2 Dirichlet Domains
          1. Division Scheme
          2. Quantization and Localization
          3. Validity
          4. Usefulness
        3. 4.4.3 Points of Visibility
          1. Division Scheme
          2. Quantization, Localization, and Validity
          3. Usefulness
        4. 4.4.4 Navigation Meshes
          1. Division Scheme
          2. Quantization and Localization
          3. Validity
          4. Usefulness
          5. Edges as Nodes
        5. 4.4.5 Non-Translational Problems
        6. 4.4.6 Cost Functions
        7. 4.4.7 Path Smoothing
          1. The Algorithm
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Performance
      5. 4.5 Improving on A*
      6. 4.6 Hierarchical Pathfinding
        1. 4.6.1 The Hierarchical Pathfinding Graph
          1. Nodes
          2. Connections
          3. Connection Costs
            1. Minimum Distance
            2. Maximin Distance
            3. Average Minimum Distance
            4. Summary of the Heuristics
        2. 4.6.2 Pathfinding on the Hierarchical Graph
          1. Algorithm
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Performance
        3. 4.6.3 Hierarchical Pathfinding on Exclusions
        4. 4.6.4 Strange Effects of Hierarchies on Pathfinding
        5. 4.6.5 Instanced Geometry
          1. Algorithm
            1. Instance Graph
            2. World Graph
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Implementation Notes
          5. Performance
          6. Weaknesses
          7. Setting Node Offsets
      7. 4.7 Other Ideas in Pathfinding
        1. 4.7.1 Open Goal Pathfinding
        2. 4.7.2 Dynamic Pathfinding
        3. 4.7.3 Other Kinds of Information Reuse
        4. 4.7.4 Low Memory Algorithms
          1. IDA*—Iterative Deepening A*
          2. SMA*—Simplified Memory-Bounded A*
        5. 4.7.5 Interruptible Pathfinding
        6. 4.7.6 Pooling Planners
      8. 4.8 Continuous Time Pathfinding
        1. 4.8.1 The Problem
        2. 4.8.2 The Algorithm
          1. Nodes as States
          2. The Size of the Graph
          3. How the Graph Is Created
          4. Which Pathfinder
        3. 4.8.3 Implementation Notes
        4. 4.8.4 Performance
        5. 4.8.5 Weaknesses
      9. 4.9 Movement Planning
        1. 4.9.1 Animations
        2. 4.9.2 Movement Planning
          1. The Planning Graph
          2. Planning
          3. Infinite Graphs
          4. Implementation Issues
        3. 4.9.3 Example
        4. 4.9.4 Footfalls
      10. Exercises
      1. Figure 4.1
      2. Figure 4.2
      3. Figure 4.3
      4. Figure 4.4
      5. Figure 4.5
      6. Figure 4.6
      7. Figure 4.7
      8. Figure 4.8
      9. Figure 4.9
      10. Figure 4.10
      11. Figure 4.11
      12. Figure 4.12
      13. Figure 4.13
      14. Figure 4.14
      15. Figure 4.15
      16. Figure 4.16
      17. Figure 4.17
      18. Figure 4.18
      19. Figure 4.19
      20. Figure 4.20
      21. Figure 4.21
      22. Figure 4.22
      23. Figure 4.23
      24. Figure 4.24
      25. Figure 4.25
      26. Figure 4.26
      27. Figure 4.27
      28. Figure 4.28
      29. Figure 4.29
      30. Figure 4.30
      31. Figure 4.31
      32. Figure 4.32
      33. Figure 4.33
      34. Figure 4.34
      35. Figure 4.35
      36. Figure 4.36
      37. Figure 4.37
      38. Figure 4.38
      39. Figure 4.39
      40. Figure 4.40
      41. Figure 4.41
      42. Figure 4.42
      43. Figure 4.43
      44. Figure 4.44
      45. Figure 4.45
      46. Figure 4.46
      47. Figure 4.47
      48. Figure 4.48
      49. Figure 4.49
      50. Figure 4.50
      51. Figure 4.51
      52. Figure 4.52
      53. Figure 4.53
      54. Figure 4.54
      55. Figure 4.55
    3. Chapter 5 Decision Making
      1. 5.1 Overview of Decision Making
      2. 5.2 Decision Trees
        1. 5.2.1 The Problem
        2. 5.2.2 The Algorithm
          1. Decisions
          2. Combinations of Decisions
          3. Decision Complexity
          4. Branching
        3. 5.2.3 Pseudo-Code
          1. Multiple Branches
        4. 5.2.4 On the Website
        5. 5.2.5 Knowledge Representation
        6. 5.2.6 Implementation Nodes
        7. 5.2.7 Performance of Decision Trees
        8. 5.2.8 Balancing the Tree
        9. 5.2.9 Beyond the Tree
        10. 5.2.10 Random Decision Trees
          1. Pseudo-Code
          2. Timing Out
          3. On the Website
          4. Using Random Decision Trees
      3. 5.3 State Machines
          1. A Basic State Machine
          2. Finite State Machines
          3. The Game FSM
        1. 5.3.1 The Problem
        2. 5.3.2 The Algorithm
        3. 5.3.3 Pseudo-Code
        4. 5.3.4 Data Structures and Interfaces
          1. Transition Implementation
            1. Weaknesses
        5. 5.3.5 On the Website
        6. 5.3.6 Performance
        7. 5.3.7 Implementation Notes
        8. 5.3.8 Hard-Coded FSM
          1. Pseudo-Code
          2. Performance
          3. Weaknesses
        9. 5.3.9 Hierarchical State Machines
          1. The Problem
          2. The Algorithm
            1. Examples
          3. Pseudo-Code
          4. Implementation Notes
          5. Performance
          6. On the Website
        10. 5.3.10 Combining Decision Trees and State Machines
          1. Pseudo-Code
      4. 5.4 Behavior Trees
          1. Types of Task
          2. A Simple Example
          3. Behavior Trees and Reactive Planning
        1. 5.4.1 Implementing Behavior Trees
        2. 5.4.2 Pseudo-Code
          1. Performance
          2. Implementation Notes
          3. Non-Deterministic Composite Tasks
        3. 5.4.3 Decorators
          1. Guarding Resources with Decorators
        4. 5.4.4 Concurrency and Timing
          1. Waiting
          2. The Parallel Task
            1. Policies for Parallel
          3. Using Parallel
          4. The Parallel Task for Condition Checking
          5. Intra-Task Behavior
        5. 5.4.5 Adding Data to Behavior Trees
        6. 5.4.6 Reusing Trees
          1. Instantiating Trees
          2. Reusing Whole Trees
          3. Reusing Sub-trees
        7. 5.4.7 Limitations of Behavior Trees
      5. 5.5 Fuzzy Logic
        1. 5.5.1 A Warning
        2. 5.5.2 Introduction to Fuzzy Logic
          1. Fuzzy Sets
          2. Membership of Multiple Sets
          3. Fuzzification
            1. Numeric Fuzzification
            2. Fuzzification of Other Data Types
          4. Defuzzification
            1. Using the Highest Membership
            2. Blending Based on Membership
            3. Center of Gravity
            4. Choosing a Defuzzification Approach
            5. Defuzzification to a Boolean Value
            6. Defuzzification to an Enumerated Value
          5. Combining Facts
          6. Fuzzy Rules
        3. 5.5.3 Fuzzy Logic Decision Making
          1. The Problem
          2. The Algorithm
            1. Rule Structure
          3. Pseudo-Code
          4. Data Structures and Interfaces
          5. Implementation Notes
          6. Performance
          7. Weaknesses
          8. Combs Method
        4. 5.5.4 Fuzzy State Machines
          1. The Problem
          2. The Algorithm
          3. Pseudo-Code
          4. Data Structures and Interfaces
          5. Implementation Notes
          6. Performance
          7. Multiple Degrees of Transition
          8. On the Website
      6. 5.6 Markov Systems
        1. 5.6.1 Markov Processes
          1. Conservative Markov Processes
          2. Iterated Processes
          3. Markov Processes in Math and Science
        2. 5.6.2 Markov State Machine
          1. The Algorithm
            1. Default Transitions
            2. Actions
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. On the Website
      7. 5.7 Goal-Oriented Behavior
        1. 5.7.1 Goal-Oriented Behavior
          1. Goals
          2. Actions
        2. 5.7.2 Simple Selection
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Performance
          4. Weaknesses
        3. 5.7.3 Overall Utility
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Performance
        4. 5.7.4 Timing
          1. Utility Involving Time
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Performance
          5. Calculating the Goal Change over Time
          6. The Need for Planning
        5. 5.7.5 Overall Utility GOAP
          1. The Algorithm
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Implementation Notes
          5. Performance
          6. Weaknesses
        6. 5.7.6 GOAP with IDA*
          1. IDA*
          2. The Heuristic
          3. The Algorithm
          4. Pseudo-Code
          5. Data Structures and Interfaces
          6. Implementation Notes
          7. Performance
        7. 5.7.7 Smelly GOB
          1. Compound Actions
            1. Action-Based Signals
            2. Character-Specific Signals
      8. 5.8 Rule-Based Systems
        1. 5.8.1 The Problem
          1. Database Matching
          2. Condition–Action Rules
          3. Database Rewriting Rules
          4. Forward and Backward Chaining
          5. Format of Data in the Database
            1. Notation of Wild Cards
        2. 5.8.2 The Algorithm
        3. 5.8.3 Pseudo-Code
        4. 5.8.4 Data Structures and Interfaces
          1. The Database
          2. Rules
          3. IF-Clauses
          4. Item Matching
            1. Datum Matching
            2. Data Group Matching
          5. Summary
        5. 5.8.5 Implementation Notes
        6. 5.8.6 Rule Arbitration
          1. First Applicable
          2. Least Recently Used
          3. Random Rule
          4. Most Specific Conditions
          5. Dynamic Priority Arbitration
        7. 5.8.7 Unification
          1. Performance
        8. 5.8.8 Rete
          1. The Algorithm
            1. Matching the Database
            2. An Example
            3. Removing a Fact
            4. Adding a Fact
            5. Managing the Update
            6. An Update Example
          2. On the Website
          3. Performance
        9. 5.8.9 Extensions
          1. Managing Large Rule Sets
          2. Justification in Expert Systems
        10. 5.8.10 Where Next
      9. 5.9 Blackboard Architectures
        1. 5.9.1 The Problem
        2. 5.9.2 The Algorithm
          1. Extracting an Action
        3. 5.9.3 Pseudo-Code
        4. 5.9.4 Data Structures and Interfaces
          1. The Blackboard Language
        5. 5.9.5 Performance
        6. 5.9.6 Other Things Are Blackboard Systems
          1. Rule-Based Systems
          2. Finite State Machines
      10. 5.10 Scripting
        1. 5.10.1 Language Facilities
          1. Speed
          2. Compilation and Interpretation
          3. Extensibility and Integration
          4. Re-Entrancy
        2. 5.10.2 Embedding
        3. 5.10.3 Choosing a Language
          1. Advantages
          2. Disadvantages
          3. Open-Source Languages
        4. 5.10.4 A Language Selection
          1. Lua
          2. Scheme and Variations
          3. Python
          4. Other Options
            1. Tcl
            2. Java
            3. JavaScript
            4. Ruby
        5. 5.10.5 Rolling Your Own
          1. The Stages of Language Processing
            1. Tokenizing
            2. Parsing
            3. Compiling
            4. Interpreting
            5. Just-in-Time Compiling
          2. Tools: A Quick Look at Lex and Yacc
        6. 5.10.6 Scripting Languages and Other AI
      11. 5.11 Action Execution
        1. 5.11.1 Types of Action
          1. A Single Action
          2. Interrupting Actions
          3. Compound Actions
          4. Scripted Actions
            1. An Aside on Scripts
        2. 5.11.2 The Algorithm
        3. 5.11.3 Pseudo-Code
        4. 5.11.4 Data Structures and Interfaces
        5. 5.11.5 Implementation Notes
          1. Debugging
        6. 5.11.6 Performance
        7. 5.11.7 Putting It All Together
          1. On the Website
      1. Figure 5.1
      2. Figure 5.2
      3. Figure 5.3
      4. Figure 5.4
      5. Figure 5.5
      6. Figure 5.6
      7. Figure 5.7
      8. Figure 5.8
      9. Figure 5.9
      10. Figure 5.10
      11. Figure 5.11
      12. Figure 5.12
      13. Figure 5.13
      14. Figure 5.14
      15. Figure 5.15
      16. Figure 5.16
      17. Figure 5.17
      18. Figure 5.18
      19. Figure 5.19
      20. Figure 5.20
      21. Figure 5.21
      22. Figure 5.22
      23. Figure 5.23
      24. Figure 5.24
      25. Figure 5.25
      26. Figure 5.26
      27. Figure 5.27
      28. Figure 5.28
      29. Figure 5.29
      30. Figure 5.30
      31. Figure 5.31
      32. Figure 5.32
      33. Figure 5.33
      34. Figure 5.34
      35. Figure 5.35
      36. Figure 5.36
      37. Figure 5.37
      38. Figure 5.38
      39. Figure 5.39
      40. Figure 5.40
      41. Figure 5.41
      42. Figure 5.42
      43. Figure 5.43
      44. Figure 5.44
      45. Figure 5.45
      46. Figure 5.46
      47. Figure 5.47
      48. Figure 5.48
      49. Figure 5.49
      50. Figure 5.50
      51. Figure 5.51
      52. Figure 5.52
      53. Figure 5.53
      54. Figure 5.54
      55. Figure 5.55
      56. Figure 5.56
      57. Figure 5.57
    4. Chapter 6 Tactical and Strategic AI
      1. 6.1 Waypoint Tactics
        1. 6.1.1 Tactical Locations
          1. A Set of Locations
          2. Primitive and Compound Tactics
          3. Waypoint Graphs and Topological Analysis
          4. Continuous Tactics
          5. Context Sensitivity
          6. Putting It Together
        2. 6.1.2 Using Tactical Locations
          1. Simple Tactical Movement
          2. Using Tactical Information Like Any Other Data
          3. Tactical Information in Fuzzy Logic Decision Making
          4. Generating Nearby Waypoints
          5. Tactical Pathfinding
        3. 6.1.3 Generating the Tactical Properties of a Waypoint
          1. Cover Points
          2. Visibility Points
          3. Shadow Points
          4. Compound Tactics
          5. Generating Tactical Properties and Tactical Analysis
        4. 6.1.4 Automatically Generating the Waypoints
          1. Watching Human Players
          2. Condensing a Waypoint Grid
        5. 6.1.5 The Condensation Algorithm
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. The Trade-Off
      2. 6.2 Tactical Analyses
        1. 6.2.1 Representing the Game Level
        2. 6.2.2 Simple Influence Maps
          1. Simple Influence
          2. Calculating the Influence
            1. Limited Radius of Effect
            2. Convolution Filters
            3. Map Flooding
          3. Applications
          4. Dealing with Unknowns
        3. 6.2.3 Terrain Analysis
          1. Terrain Difficulty
          2. Visibility Map
        4. 6.2.4 Learning with Tactical Analyses
        5. 6.2.5 A Structure for Tactical Analyses
          1. Multi-Layer Analyses
          2. When to Combine Things
          3. Building a Tactical Analysis Server
        6. 6.2.6 Map Flooding
          1. The Algorithm
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Performance
        7. 6.2.7 Convolution Filters
          1. The Algorithm
          2. Boundaries
          3. Pseudo-Code
          4. Data Structures and Interfaces
          5. Implementation Notes
          6. Performance
          7. Filters
          8. Gaussian Blur
          9. Separable Filters
          10. The Sharpening Filter
        8. 6.2.8 Cellular Automata
          1. Cellular Automata Rules
          2. Running a Cellular Automaton
          3. The Complexity of Cellular Automata
          4. Applications and Rules
            1. Area of Security
            2. Building a City
      3. 6.3 Tactical Pathfinding
        1. 6.3.1 The Cost Function
        2. 6.3.2 Tactic Weights and Concern Blending
        3. 6.3.3 Modifying the Pathfinding Heuristic
        4. 6.3.4 Tactical Graphs for Pathfinding
        5. 6.3.5 Using Tactical Waypoints
      4. 6.4 Coordinated Action
        1. 6.4.1 Multi-Tier AI
          1. Group Decisions
          2. Group Movement
          3. Group Pathfinding
          4. Including the Player
          5. Explicit Player Orders
          6. Structuring Multi-Tier AI
        2. 6.4.2 Emergent Cooperation
          1. Scalability
          2. Predictability
        3. 6.4.3 Scripting Group Actions
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Implementation Notes
          4. Performance
          5. Creating Scripts
        4. 6.4.4 Military Tactics
          1. Case Study: A Fire Team Takes a House
      5. Exercises
      1. Figure 6.1
      2. Figure 6.2
      3. Figure 6.3
      4. Figure 6.4
      5. Figure 6.5
      6. Figure 6.6
      7. Figure 6.7
      8. Figure 6.8
      9. Figure 6.9
      10. Figure 6.10
      11. Figure 6.11
      12. Figure 6.12
      13. Figure 6.13
      14. Figure 6.14
      15. Figure 6.15
      16. Figure 6.16
      17. Figure 6.17
      18. Figure 6.18
      19. Figure 6.19
      20. Figure 6.20
      21. Figure 6.21
      22. Figure 6.22
      23. Figure 6.23
      24. Figure 6.24
      25. Figure 6.25
      26. Figure 6.26
      27. Figure 6.27
      28. Figure 6.28
      29. Figure 6.29
      30. Figure 6.30
    5. Chapter 7 Learning
      1. 7.1 Learning Basics
        1. 7.1.1 Online or Offline Learning
        2. 7.1.2 Intra-Behavior Learning
        3. 7.1.3 Inter-Behavior Learning
        4. 7.1.4 A Warning
        5. 7.1.5 Over-Learning
        6. 7.1.6 The Zoo of Learning Algorithms
        7. 7.1.7 The Balance of Effort
      2. 7.2 Parameter Modification
        1. 7.2.1 The Parameter Landscape
          1. Energy and Fitness Values
        2. 7.2.2 Hill Climbing
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Implementation Notes
          4. Performance
        3. 7.2.3 Extensions to Basic Hill Climbing
          1. Momentum
          2. Adaptive Resolution
          3. Multiple Trials
          4. Finding the Global Optimum
        4. 7.2.4 Annealing
          1. Direct Method
            1. Pseudo-Code
            2. Implementation Notes
            3. Performance
          2. Boltzmann Probabilities
            1. Pseudo-Code
            2. Performance
          3. Optimizations
      3. 7.3 Action Prediction
        1. 7.3.1 Left or Right
        2. 7.3.2 Raw Probability
        3. 7.3.3 String Matching
        4. 7.3.4 N-Grams
            1. N-Grams in Computer Science
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Implementation Notes
          4. Performance
        5. 7.3.5 Window Size
          1. Memory Concerns
          2. Sequence Length
        6. 7.3.6 Hierarchical N-Grams
          1. Pseudo-Code
          2. Data Structures and Implementation
          3. Performance
          4. Confidence
        7. 7.3.7 Application in Combat
      4. 7.4 Decision Learning
        1. 7.4.1 Structure of Decision Learning
          1. Weak or Strong Supervision
        2. 7.4.2 What Should You Learn?
        3. 7.4.3 Four Techniques
      5. 7.5 Naive Bayes Classifiers
          1. Pseudo-Code
        1. 7.5.1 Implementation Notes
      6. 7.6 Decision Tree Learning
        1. 7.6.1 ID3
          1. Algorithm
          2. Entropy and Information Gain
          3. More than Two Actions
          4. Non-Binary Discrete Attributes
          5. Pseudo-Code
            1. Split by Attribute
            2. Entropy
            3. Entropy of Sets
          6. Data Structures and Interfaces
          7. Starting the Algorithm
          8. Performance
        2. 7.6.2 ID3 with Continuous Attributes
          1. Single Splits
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Performance
          5. On the Website
          6. Multiple Categories
        3. 7.6.3 Incremental Decision Tree Learning
          1. The Algorithm
          2. Walk Through
          3. Problems with ID4
          4. Heuristic Algorithms
      7. 7.7 Reinforcement Learning
        1. 7.7.1 The Problem
        2. 7.7.2 The Algorithm
          1. Q-Learning’s Representation of the World
          2. Doing Learning
          3. How It Works
          4. Exploration Strategy
          5. Convergence and Ending
          6. On the Website
        3. 7.7.3 Pseudo-Code
        4. 7.7.4 Data Structures and Interfaces
        5. 7.7.5 Implementation Notes
        6. 7.7.6 Performance
        7. 7.7.7 Tailoring Parameters
          1. Alpha: The Learning Rate
          2. Gamma: The Discount Rate
          3. Rho: Randomness for Exploration
          4. Nu: The Length of Walk
          5. Choosing Rewards
        8. 7.7.8 Weaknesses and Realistic Applications
          1. Limits of the Algorithm
          2. Applications
          3. Case Study: Choosing Tactical Defense Locations
            1. On the Website
        9. 7.7.9 Other Ideas in Reinforcement Learning
          1. TD
          2. Off-Policy and On-Policy Algorithms
          3. TD in Board Game AI
          4. Neural Networks for Storage
          5. Actor–Critic
      8. 7.8 Artificial Neural Networks
          1. Neural Network Zoology
        1. 7.8.1 Overview
          1. Architecture
          2. Feedforward and Recurrence
          3. Neuron Algorithm
          4. Learning Rule
        2. 7.8.2 The Problem
          1. What about Decision Tree Learning?
        3. 7.8.3 The Algorithm
          1. Initial Setup and Framework
          2. Feedforward
          3. Backpropagation
            1. The Error Term
            2. The Gain
        4. 7.8.4 Pseudo-Code
        5. 7.8.5 Data Structures and Interfaces
        6. 7.8.6 Implementation Caveats
          1. On the Website
        7. 7.8.7 Performance
        8. 7.8.8 Other Approaches
          1. Radial Basis Function
          2. Weakly Supervised Learning
          3. Hebbian Learning
      9. Exercises
      1. Figure 7.1
      2. Figure 7.2
      3. Figure 7.3
      4. Figure 7.4
      5. Figure 7.5
      6. Figure 7.6
      7. Figure 7.7
      8. Figure 7.8
      9. Figure 7.9
      10. Figure 7.10
      11. Figure 7.11
      12. Figure 7.12
      13. Figure 7.13
      14. Figure 7.14
      15. Figure 7.15
      16. Figure 7.16
      17. Figure 7.17
      18. Figure 7.18
      19. Figure 7.19
      20. Figure 7.20
      21. Figure 7.21
      22. Figure 7.22
      23. Figure 7.23
      24. Figure 7.24
      25. Figure 7.25
    6. Chapter 8 Board Games
      1. 8.1 Game Theory
        1. 8.1.1 Types of Games
          1. Number of Players
            1. Plies, Moves, and Turns
          2. The Goal of the Game
          3. Information
          4. Applying Algorithms
        2. 8.1.2 The Game Tree
          1. Branching Factor and Depth
          2. Transposition
      2. 8.2 Minimaxing
        1. 8.2.1 The Static Evaluation Function
          1. Range of the Function
          2. Combining Scoring Functions
          3. Simple Move Choice
        2. 8.2.2 Minimaxing
        3. 8.2.3 The Minimaxing Algorithm
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. More than Two Players
          4. Performance
        4. 8.2.4 Negamaxing
          1. Negamax and the Static Evaluation Function
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Performance
          5. Implementation Notes
        5. 8.2.5 AB Pruning
          1. Alpha Pruning
          2. Beta Pruning
          3. AB Negamax
          4. Pseudo-Code
          5. Data Structures and Interfaces
          6. Performance
        6. 8.2.6 The AB Search Window
          1. Move Order
          2. Aspiration Search
        7. 8.2.7 Negascout
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Performance
          4. Move Ordering and Negascout
          5. Principal Variation Search
      3. 8.3 Transposition Tables and Memory
        1. 8.3.1 Hashing Game States
          1. Zobrist Keys
          2. Hash Implementation
          3. Incremental Zobrist Hashing
          4. The Game Class, Revisited
        2. 8.3.2 What to Store in the Table
        3. 8.3.3 Hash Table Implementation
        4. 8.3.4 Replacement Strategies
        5. 8.3.5 A Complete Transposition Table
          1. Performance
          2. Implementation Notes
        6. 8.3.6 Transposition Table Issues
          1. Path Dependency
          2. Instability
        7. 8.3.7 Using Opponent’s Thinking Time
      4. 8.4 Memory-Enhanced Test Algorithms
        1. 8.4.1 Implementing Test
          1. Pseudo-Code
          2. Transposition Table
        2. 8.4.2 The MTD Algorithm
          1. MTD Variations
          2. Memory Size
        3. 8.4.3 Pseudo-Code
          1. Performance
      5. 8.5 Opening Books and Other Set Plays
        1. 8.5.1 Implementing an Opening Book
          1. Opening Book in the Evaluation Function
        2. 8.5.2 Learning for Opening Books
        3. 8.5.3 Set Play Books
          1. Ending Database
      6. 8.6 Further Optimizations
        1. 8.6.1 Iterative Deepening
          1. MTD Implementation
          2. History Heuristic
        2. 8.6.2 Variable Depth Approaches
          1. Extensions
          2. Quiescence Pruning
      7. 8.7 Turn-Based Strategy Games
        1. 8.7.1 Impossible Tree Size
          1. Divide and Conquer
          2. Heuristics
        2. 8.7.2 Real-Time AI in a Turn-Based Game
      8. Exercises
      1. Figure 8.1
      2. Figure 8.2
      3. Figure 8.3
      4. Figure 8.4
      5. Figure 8.5
      6. Figure 8.6
      7. Figure 8.7
      8. Figure 8.8
      9. Figure 8.9
      10. Figure 8.10
      11. Figure 8.11
      12. Figure 8.12
  9. Part III Supporting Technologies
    1. Chapter 9 Execution Management
      1. 9.1 Scheduling
        1. 9.1.1 The Scheduler
          1. Frequencies
          2. Phase
          3. Pseudo-Code
          4. Implementation Notes
          5. Performance
          6. Direct Access
          7. Pseudo-Code
            1. Data Structures and Interfaces
            2. Performance
          8. Phase Quality
          9. Automatic Phasing
            1. Wright’s Method
            2. Analytic Method
          10. Single Task Spikes
        2. 9.1.2 Interruptible Processes
          1. Threads
          2. Software Threads
          3. Micro-Threads
          4. Hyper-Threads and Multiple Cores
          5. Quality of Service
        3. 9.1.3 Load-Balancing Scheduler
          1. Pseudo-Code
          2. Data Structures
          3. Performance
        4. 9.1.4 Hierarchical Scheduling
          1. Data Structures and Interfaces
          2. Behavior Selection
        5. 9.1.5 Priority Scheduling
          1. Pseudo-Code
          2. Performance
          3. Other Policies
          4. Priority Problems
      2. 9.2 Anytime Algorithms
      3. 9.3 Level of Detail
        1. 9.3.1 Graphics Level of Detail
        2. 9.3.2 AI LOD
          1. Importance Values
        3. 9.3.3 Scheduling LOD
          1. Frequency Schedulers
          2. Priority Schedulers
          3. Combined Scheduling
        4. 9.3.4 Behavioral LOD
          1. Entry and Exit Processing
          2. Behavior Compression
          3. Hysteresis
            1. Choose Any Available Behavior
            2. Choose the First Available Behavior in the List
            3. Select the Most Central Behavior
            4. Select the Available Behavior with the Smallest Range
            5. Fallback Behaviors
          4. Pseudo-Code
          5. Data Structures and Interfaces
          6. Implementation Notes
          7. Performance
        5. 9.3.5 Group LOD
          1. Probability Distributions
        6. 9.3.6 In Summary
      4. Exercises
      1. Figure 9.1
      2. Figure 9.2
      3. Figure 9.3
      4. Figure 9.4
      5. Figure 9.5
      6. Figure 9.6
      7. Figure 9.7
      8. Figure 9.8
      9. Figure 9.9
      10. Figure 9.10
    2. Chapter 10 World Interfacing
      1. 10.1 Communication
      2. 10.2 Getting Knowledge Efficiently
        1. 10.2.1 Polling
          1. Polling Stations
        2. 10.2.2 Events
          1. Event Managers
        3. 10.2.3 Determining What Approach to Use
      3. 10.3 Event Managers
        1. 10.3.1 Implementation
          1. Pseudo-Code
          2. Data Structures and Interfaces
          3. Performance
          4. Implementation Notes
        2. 10.3.2 Event Casting
          1. Broadcasting
          2. Narrowcasting
          3. Compromising
        3. 10.3.3 Inter-Agent Communication
      4. 10.4 Polling Stations
        1. 10.4.1 Pseudo-Code
        2. 10.4.2 Performance
        3. 10.4.3 Implementation Notes
        4. 10.4.4 Abstract Polling
      5. 10.5 Sense Management
        1. 10.5.1 Faking It
        2. 10.5.2 What Do We Know?
          1. Polling and Notification Revisited
        3. 10.5.3 Sensory Modalities
          1. Sight
            1. Speed
            2. Sight Cone
            3. Line of Sight
            4. Distance
            5. Brightness
            6. Differentiation
          2. Hearing
          3. Touch
          4. Smell
          5. Fantasy Modalities
        4. 10.5.4 Region Sense Manager
          1. The Algorithm
          2. Pseudo-Code
          3. Data Structures and Interfaces
          4. Performance
          5. Camouflage and Shadows
          6. Weaknesses
        5. 10.5.5 Finite Element Model Sense Manager
          1. Finite Element Models
          2. The Sense Graph
            1. Sight
          3. The Algorithm
            1. Sights
            2. Sound
            3. Smell
            4. Calculating Intensity from Node to Node
            5. Iterative Algorithm
            6. Dispatching
          4. On the Website
          5. Implementation Notes
          6. Weaknesses
            1. Content Creation
      6. Exercises
      1. Figure 10.1
      2. Figure 10.2
      3. Figure 10.3
      4. Figure 10.4
      5. Figure 10.5
      6. Figure 10.6
      7. Figure 10.7
      8. Figure 10.8
      9. Figure 10.9
      10. Figure 10.10
    3. Chapter 11 Tools and Content Creation
      1. 11.0.1 Toolchains Limit AI
      2. 11.0.2 Where AI Knowledge Comes from
      3. 11.1 Knowledge for Pathfinding and Waypoint Tactics
        1. 11.1.1 Manually Creating Region Data
          1. Tile Graphs
          2. Dirichlet Domains
          3. Navigation Meshes
          4. Bounded Regions
        2. 11.1.2 Automatic Graph Creation
        3. 11.1.3 Geometric Analysis
          1. Calculating Costs
          2. Calculating Connections
            1. Point-Based Representations
            2. Arbitrary Bounding Regions
            3. Limitations of Visibility Approaches
            4. Mesh Representations
          3. Calculating Nodes
        4. 11.1.4 Data Mining
          1. Calculating Nodes
          2. Calculating Connections
          3. Character Movement
          4. Limitations
          5. Other Representations
      4. 11.2 Knowledge for Movement
        1. 11.2.1 Obstacles
          1. Walls
          2. Obstacle Representation
        2. 11.2.2 High-Level Staging
      5. 11.3 Knowledge for Decision Making
        1. 11.3.1 Object Types
        2. 11.3.2 Concrete Actions
      6. 11.4 The Toolchain
        1. 11.4.1 Data-Driven Editors
        2. 11.4.2 AI Design Tools
          1. Scripting Tools
          2. State Machine Designers
        3. 11.4.3 Remote Debugging
        4. 11.4.4 Plug-Ins
      7. Exercises
      1. Figure 11.1
      2. Figure 11.2
      3. Figure 11.3
      4. Figure 11.4
      5. Figure 11.5
  10. Part IV Designing Game AI
    1. Chapter 12 Designing Game AI
      1. 12.1 The Design
        1. 12.1.1 Example
        2. 12.1.2 Evaluating the Behaviors
          1. Example
        3. 12.1.3 Selecting Techniques
          1. Example
        4. 12.1.4 The Scope of One Game
      2. 12.2 Shooters
        1. 12.2.1 Movement and Firing
        2. 12.2.2 Decision Making
        3. 12.2.3 Perception
        4. 12.2.4 Pathfinding and Tactical AI
        5. 12.2.5 Shooter-Like Games
          1. Platform and Adventure Games
          2. MMOGs
      3. 12.3 Driving
        1. 12.3.1 Movement
        2. 12.3.2 Pathfinding and Tactical AI
        3. 12.3.3 Driving-Like Games
      4. 12.4 Real-Time Strategy
        1. 12.4.1 Pathfinding
        2. 12.4.2 Group Movement
        3. 12.4.3 Tactical and Strategic AI
        4. 12.4.4 Decision Making
      5. 12.5 Sports
        1. 12.5.1 Physics Prediction
        2. 12.5.2 Playbooks and Content Creation
      6. 12.6 Turn-Based Strategy Games
        1. 12.6.1 Timing
        2. 12.6.2 Helping the Player
      1. Figure 12.1
      2. Figure 12.2
      3. Figure 12.3
      4. Figure 12.4
      5. Figure 12.5
      6. Figure 12.6
      7. Figure 12.7
    2. Chapter 13 AI-Based Game Genres
      1. 13.1 Teaching Characters
        1. 13.1.1 Representing Actions
        2. 13.1.2 Representing the World
        3. 13.1.3 Learning Mechanism
          1. Neural Network Architecture
          2. Observational Learning
          3. Mind-Reading for Observational Learning
          4. Feedback Learning
        4. 13.1.4 Predictable Mental Models and Pathological States
          1. Instincts
          2. The Brain Death of a Character
      2. 13.2 Flocking and Herding Games
        1. 13.2.1 Making the Creatures
        2. 13.2.2 Tuning Steering for Interactivity
        3. 13.2.3 Steering Behavior Stability
        4. 13.2.4 Ecosystem Design
          1. Size of the Food Chain
          2. Behavior Complexity
          3. Sensory Limits
          4. Movement Range
          5. Putting It All Together
      1. Figure 13.1
      2. Figure 13.2
      3. Figure 13.3
    1. References
      1. A.1 Books, Periodicals, and Papers
      2. A.2 Games