AI for Games, Third Edition, 3rd Edition

AI for Games, Third Edition, 3rd Edition

by Ian Millington
Released March 2019
Publisher(s): CRC Press
ISBN: 9781351053280

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Artificial Intelligence is an integral part of every video game. This book helps propfessionals keep up with the constantly evolving technological advances in the fast growing game industry and equips students with up-to-date infortmation they need to jumpstart their careers.

Table of contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright Page
  5. Dedication
  6. Table of Contents
  7. PART I AI and Games
    1. CHAPTER 1 INTRODUCTION
      1. 1.1 What Is AI?
        1. 1.1.1 Academic AI
        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 and Data Structures
        1. 1.3.1 Algorithms
        2. 1.3.2 Representations
        3. 1.3.3 Implementation
      4. 1.4 Layout of the Book
    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
        3. 2.2.3 Algorithms
      3. 2.3 Speed and Memory Constraints
        1. 2.3.1 Processor Issues
        2. 2.3.2 Memory Concerns
        3. 2.3.3 Platforms
      4. 2.4 The AI Engine
        1. 2.4.1 Structure of an AI Engine
        2. 2.4.2 Tool Concerns
        3. 2.4.3 Putting It All Together
  8. PART II Techniques
    1. CHAPTER 3 MOVEMENT
      1. 3.1 The Basics of Movement Algorithms
        1. 3.1.1 Two-Dimensional Movement
        2. 3.1.2 Statics
        3. 3.1.3 Kinematics
      2. 3.2 Kinematic Movement Algorithms
        1. 3.2.1 Seek
        2. 3.2.2 Wandering
      3. 3.3 Steering Behaviors
        1. 3.3.1 Steering Basics
        2. 3.3.2 Variable Matching
        3. 3.3.3 Seek and Flee
        4. 3.3.4 Arrive
        5. 3.3.5 Align
        6. 3.3.6 Velocity Matching
        7. 3.3.7 Delegated Behaviors
        8. 3.3.8 Pursue and Evade
        9. 3.3.9 Face
        10. 3.3.10 Looking Where You’re Going
        11. 3.3.11 Wander
        12. 3.3.12 Path Following
        13. 3.3.13 Separation
        14. 3.3.14 Collision Avoidance
        15. 3.3.15 Obstacle and Wall Avoidance
        16. 3.3.16 Summary
      4. 3.4 Combining Steering Behaviors
        1. 3.4.1 Blending and Arbitration
        2. 3.4.2 Weighted Blending
        3. 3.4.3 Priorities
        4. 3.4.4 Cooperative Arbitration
        5. 3.4.5 Steering Pipeline
      5. 3.5 Predicting Physics
        1. 3.5.1 Aiming and Shooting
        2. 3.5.2 Projectile Trajectory
        3. 3.5.3 The Firing Solution
        4. 3.5.4 Projectiles with Drag
        5. 3.5.5 Iterative Targeting
      6. 3.6 Jumping
        1. 3.6.1 Jump Points
        2. 3.6.2 Landing Pads
        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
        5. 3.7.5 Implementation
        6. 3.7.6 Extending to More Than Two Levels
        7. 3.7.7 Slot Roles and Better Assignment
        8. 3.7.8 Slot Assignment
        9. 3.7.9 Dynamic Slots and Plays
        10. 3.7.10 Tactical Movement
      8. 3.8 Motor Control
        1. 3.8.1 Output Filtering
        2. 3.8.2 Capability-Sensitive Steering
        3. 3.8.3 Common Actuation Properties
      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
        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
    2. CHAPTER 4 PATHFINDING
      1. 4.1 The Pathfinding Graph
        1. 4.1.1 Graphs
        2. 4.1.2 Weighted Graphs
        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
        3. 4.2.3 Pseudo-Code
        4. 4.2.4 Data Structures and Interfaces
        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
        3. 4.3.3 Pseudo-Code
        4. 4.3.4 Data Structures and Interfaces
        5. 4.3.5 Implementation Notes
        6. 4.3.6 Algorithm Performance
        7. 4.3.7 Node Array A*
        8. 4.3.8 Choosing a Heuristic
      4. 4.4 World Representations
        1. 4.4.1 Tile Graphs
        2. 4.4.2 Dirichlet Domains
        3. 4.4.3 Points of Visibility
        4. 4.4.4 Navigation Meshes
        5. 4.4.5 Non-Translational Problems
        6. 4.4.6 Cost Functions
        7. 4.4.7 Path Smoothing
      5. 4.5 Improving on A*
      6. 4.6 Hierarchical Pathfinding
        1. 4.6.1 The Hierarchical Pathfinding Graph
        2. 4.6.2 Pathfinding on the Hierarchical Graph
        3. 4.6.3 Hierarchical Pathfinding on Exclusions
        4. 4.6.4 Strange Effects of Hierarchies on Pathfinding
        5. 4.6.5 Instanced Geometry
      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
        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
        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
        3. 4.9.3 Example
        4. 4.9.4 Footfalls
    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
        3. 5.2.3 Pseudo-Code
        4. 5.2.4 Knowledge Representation
        5. 5.2.5 Implementation Notes
        6. 5.2.6 Performance of Decision Trees
        7. 5.2.7 Balancing the Tree
        8. 5.2.8 Beyond the Tree
        9. 5.2.9 Random Decision Trees
      3. 5.3 State Machines
        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
        5. 5.3.5 Performance
        6. 5.3.6 Implementation Notes
        7. 5.3.7 Hard-Coded FSM
        8. 5.3.8 Hierarchical State Machines
        9. 5.3.9 Combining Decision Trees and State Machines
      4. 5.4 Behavior Trees
        1. 5.4.1 Implementing Behavior Trees
        2. 5.4.2 Pseudo-Code
        3. 5.4.3 Decorators
        4. 5.4.4 Concurrency and Timing
        5. 5.4.5 Adding Data to Behavior Trees
        6. 5.4.6 Reusing 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
        3. 5.5.3 Fuzzy Logic Decision Making
        4. 5.5.4 Fuzzy State Machines
      6. 5.6 Markov Systems
        1. 5.6.1 Markov Processes
        2. 5.6.2 Markov State Machine
      7. 5.7 Goal-Oriented Behavior
        1. 5.7.1 Goal-Oriented Behavior
        2. 5.7.2 Simple Selection
        3. 5.7.3 Overall Utility
        4. 5.7.4 Timing
        5. 5.7.5 Overall Utility GOAP
        6. 5.7.6 GOAP with IDA*
        7. 5.7.7 Smelly GOB
      8. 5.8 Rule-Based Systems
        1. 5.8.1 The Problem
        2. 5.8.2 The Algorithm
        3. 5.8.3 Pseudo-Code
        4. 5.8.4 Data Structures and Interfaces
        5. 5.8.5 Rule Arbitration
        6. 5.8.6 Unification
        7. 5.8.7 Rete
        8. 5.8.8 Extensions
        9. 5.8.9 Where Next
      9. 5.9 Blackboard Architectures
        1. 5.9.1 The Problem
        2. 5.9.2 The Algorithm
        3. 5.9.3 Pseudo-Code
        4. 5.9.4 Data Structures and Interfaces
        5. 5.9.5 Performance
        6. 5.9.6 Other Things Are Blackboard Systems
      10. 5.10 Action Execution
        1. 5.10.1 Types of Action
        2. 5.10.2 The Algorithm
        3. 5.10.3 Pseudo-Code
        4. 5.10.4 Data Structures and Interfaces
        5. 5.10.5 Implementation Notes
        6. 5.10.6 Performance
        7. 5.10.7 Putting It All Together
    4. CHAPTER 6 TACTICAL AND STRATEGIC AI
      1. 6.1 Waypoint Tactics
        1. 6.1.1 Tactical Locations
        2. 6.1.2 Using Tactical Locations
        3. 6.1.3 Generating the Tactical Properties of a Waypoint
        4. 6.1.4 Automatically Generating the Waypoints
        5. 6.1.5 The Condensation Algorithm
      2. 6.2 Tactical Analyses
        1. 6.2.1 Representing the Game Level
        2. 6.2.2 Simple Influence Maps
        3. 6.2.3 Terrain Analysis
        4. 6.2.4 Learning with Tactical Analyses
        5. 6.2.5 A Structure for Tactical Analyses
        6. 6.2.6 Map Flooding
        7. 6.2.7 Convolution Filters
        8. 6.2.8 Cellular Automata
      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
        2. 6.4.2 Emergent Cooperation
        3. 6.4.3 Scripting Group Actions
        4. 6.4.4 Military Tactics
    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
        2. 7.2.2 Hill Climbing
        3. 7.2.3 Extensions to Basic Hill Climbing
        4. 7.2.4 Annealing
      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
        5. 7.3.5 Window Size
        6. 7.3.6 Hierarchical N-Grams
        7. 7.3.7 Application in Combat
      4. 7.4 Decision Learning
        1. 7.4.1 The Structure of Decision Learning
        2. 7.4.2 What Should You Learn?
        3. 7.4.3 Four Techniques
      5. 7.5 Naive Bayes Classifiers
        1. 7.5.1 Pseudo-Code
        2. 7.5.2 Implementation Notes
      6. 7.6 Decision Tree Learning
        1. 7.6.1 ID3
        2. 7.6.2 ID3 with Continuous Attributes
        3. 7.6.3 Incremental Decision Tree Learning
      7. 7.7 Reinforcement Learning
        1. 7.7.1 The Problem
        2. 7.7.2 The Algorithm
        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
        8. 7.7.8 Weaknesses and Realistic Applications
        9. 7.7.9 Other Ideas in Reinforcement Learning
      8. 7.8 Artificial Neural Networks
        1. 7.8.1 Overview
        2. 7.8.2 The Problem
        3. 7.8.3 The Algorithm
        4. 7.8.4 Pseudo-Code
        5. 7.8.5 Data Structures and Interfaces
        6. 7.8.6 Implementation Caveats
        7. 7.8.7 Performance
        8. 7.8.8 Other Approaches
      9. 7.9 Deep Learning
        1. 7.9.1 What is Deep Learning?
        2. 7.9.2 Data
    6. CHAPTER 8 PROCEDURAL CONTENT GENERATION
      1. 8.1 Pseudorandom Numbers
        1. 8.1.1 Numeric Mixing and Game Seeds
        2. 8.1.2 Halton Sequence
        3. 8.1.3 Phyllotaxic Angles
        4. 8.1.4 Poisson Disk
      2. 8.2 Lindenmayer Systems
        1. 8.2.1 Simple L-systems
        2. 8.2.2 Adding Randomness to L-systems
        3. 8.2.3 Stage-Specific Rules
      3. 8.3 Landscape Generation
        1. 8.3.1 Modifiers and Height-Maps
        2. 8.3.2 Noise
        3. 8.3.3 Perlin Noise
        4. 8.3.4 Faults
        5. 8.3.5 Thermal Erosion
        6. 8.3.6 Hydraulic Erosion
        7. 8.3.7 Altitude Filtering
      4. 8.4 Dungeons and Maze Generation
        1. 8.4.1 Mazes by Depth First Backtracking
        2. 8.4.2 Minimum Spanning Tree Algorithms
        3. 8.4.3 Recursive Subdivision
        4. 8.4.4 Generate and Test
      5. 8.5 Shape Grammars
        1. 8.5.1 Running the Grammar
        2. 8.5.2 Planning
    7. CHAPTER 9 BOARD GAMES
      1. 9.1 Game Theory
        1. 9.1.1 Types of Games
        2. 9.1.2 The Game Tree
      2. 9.2 Minimaxing
        1. 9.2.1 The Static Evaluation Function
        2. 9.2.2 Minimaxing
        3. 9.2.3 The Minimaxing Algorithm
        4. 9.2.4 Negamaxing
        5. 9.2.5 AB Pruning
        6. 9.2.6 The AB Search Window
        7. 9.2.7 Negascout
      3. 9.3 Transposition Tables and Memory
        1. 9.3.1 Hashing Game States
        2. 9.3.2 What to Store in the Table
        3. 9.3.3 Hash Table Implementation
        4. 9.3.4 Replacement Strategies
        5. 9.3.5 A Complete Transposition Table
        6. 9.3.6 Transposition Table Issues
        7. 9.3.7 Using Opponent’s Thinking Time
      4. 9.4 Memory-Enhanced Test Algorithms
        1. 9.4.1 Implementing Test
        2. 9.4.2 The MTD Algorithm
        3. 9.4.3 Pseudo-Code
      5. 9.5 Monte Carlo Tree Search (MCTS)
        1. 9.5.1 Pure Monte Carlo Tree Search
        2. 9.5.2 Adding Knowledge
      6. 9.6 Opening Books and Other Set Plays
        1. 9.6.1 Implementing an Opening Book
        2. 9.6.2 Learning for Opening Books
        3. 9.6.3 Set Play Books
      7. 9.7 Further Optimizations
        1. 9.7.1 Iterative Deepening
        2. 9.7.2 Variable Depth Approaches
      8. 9.8 Game Knowledge
        1. 9.8.1 Creating a Static Evaluation Function
        2. 9.8.2 Learning the Static Evaluation Function
      9. 9.9 Turn-Based Strategy Games
        1. 9.9.1 Impossible Tree Size
        2. 9.9.2 Real-Time AI in a Turn-Based Game
  9. PART III Supporting Technologies
    1. CHAPTER 10 EXECUTION MANAGEMENT
      1. 10.1 Scheduling
        1. 10.1.1 The Scheduler
        2. 10.1.2 Interruptible Processes
        3. 10.1.3 Load-Balancing Scheduler
        4. 10.1.4 Hierarchical Scheduling
        5. 10.1.5 Priority Scheduling
      2. 10.2 Anytime Algorithms
      3. 10.3 Level of Detail
        1. 10.3.1 Graphics Level of Detail
        2. 10.3.2 AI LOD
        3. 10.3.3 Scheduling LOD
        4. 10.3.4 Behavioral LOD
        5. 10.3.5 Group LOD
        6. 10.3.6 In Summary
    2. CHAPTER 11 WORLD INTERFACING
      1. 11.1 Communication
        1. 11.1.1 Polling
        2. 11.1.2 Events
        3. 11.1.3 Determining Which Approach to Use
      2. 11.2 Event Managers
        1. 11.2.1 Implementation
        2. 11.2.2 Event Casting
        3. 11.2.3 Inter-Agent Communication
      3. 11.3 Polling Stations
        1. 11.3.1 Pseudo-Code
        2. 11.3.2 Performance
        3. 11.3.3 Implementation Notes
        4. 11.3.4 Abstract Polling
      4. 11.4 Sense Management
        1. 11.4.1 Faking It
        2. 11.4.2 What Do We Know?
        3. 11.4.3 Sensory Modalities
        4. 11.4.4 Region Sense Manager
        5. 11.4.5 Finite Element Model Sense Manager
    3. CHAPTER 12 TOOLS AND CONTENT CREATION
      1. 12.0.1 Toolchains Limit AI
      2. 12.0.2 Where AI Knowledge Comes From
      3. 12.1 Knowledge for Pathfinding and Waypoints
        1. 12.1.1 Manually Creating Region Data
        2. 12.1.2 Automatic Graph Creation
        3. 12.1.3 Geometric Analysis
        4. 12.1.4 Data Mining
      4. 12.2 Knowledge for Movement
        1. 12.2.1 Obstacles
        2. 12.2.2 High-Level Staging
      5. 12.3 Knowledge for Decision Making
        1. 12.3.1 Object Types
        2. 12.3.2 Concrete Actions
      6. 12.4 The Toolchain
        1. 12.4.1 Integrated Game Engines
        2. 12.4.2 Custom Data-Driven Editors
        3. 12.4.3 AI Design Tools
        4. 12.4.4 Remote Debugging
        5. 12.4.5 Plug-Ins
    4. CHAPTER 13 PROGRAMMING GAME AI
      1. 13.1 Implementation Language
        1. 13.1.1 C++
        2. 13.1.2 C#
        3. 13.1.3 Swift
        4. 13.1.4 Java
        5. 13.1.5 JavaScript
      2. 13.2 Scripted AI
        1. 13.2.1 What Is Scripted AI?
        2. 13.2.2 What Makes a Good Scripting Language?
        3. 13.2.3 Embedding
        4. 13.2.4 Choosing an Open Source Language
        5. 13.2.5 A Language Selection
      3. 13.3 Creating a Language
        1. 13.3.1 Rolling Your Own
  10. PART IV Designing Game AI
    1. CHAPTER 14 DESIGNING GAME AI
      1. 14.1 The Design
        1. 14.1.1 Example
        2. 14.1.2 Evaluating the Behaviors
        3. 14.1.3 Selecting Techniques
        4. 14.1.4 The Scope of One Game
      2. 14.2 Shooters
        1. 14.2.1 Movement and Firing
        2. 14.2.2 Decision Making
        3. 14.2.3 Perception
        4. 14.2.4 Pathfinding and Tactical AI
        5. 14.2.5 Shooter-Like Games
        6. 14.2.6 Melee Combat
      3. 14.3 Driving
        1. 14.3.1 Movement
        2. 14.3.2 Pathfinding and Tactical AI
        3. 14.3.3 Driving-Like Games
      4. 14.4 Real-Time Strategy
        1. 14.4.1 Pathfinding
        2. 14.4.2 Group Movement
        3. 14.4.3 Tactical and Strategic AI
        4. 14.4.4 Decision Making
        5. 14.4.5 MOBAs
      5. 14.5 Sports
        1. 14.5.1 Physics Prediction
        2. 14.5.2 Playbooks and Content Creation
      6. 14.6 Turn-Based Strategy Games
        1. 14.6.1 Timing
        2. 14.6.2 Helping the Player
    2. CHAPTER 15 AI-BASED GAME GENRES
      1. 15.1 Teaching Characters
        1. 15.1.1 Representing Actions
        2. 15.1.2 Representing the World
        3. 15.1.3 Learning Mechanism
        4. 15.1.4 Predictable Mental Models
      2. 15.2 Flocking and Herding Games
        1. 15.2.1 Making the Creatures
        2. 15.2.2 Tuning Steering for Interactivity
        3. 15.2.3 Steering Behavior Stability
        4. 15.2.4 Ecosystem Design
  11. REFERENCES
    1. Books, Periodicals, Papers and Websites
    2. Games
  12. INDEX

Product information

  • Title: AI for Games, Third Edition, 3rd Edition
  • Author(s): Ian Millington
  • Release date: March 2019
  • Publisher(s): CRC Press
  • ISBN: 9781351053280