AI for Games

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