book

AI for Games, Third Edition, 3rd Edition

by Ian Millington

March 2019

Beginner

1030 pages

29h 27m

English

CRC Press

Read now

Unlock full access

1.1 What Is AI?1.1.1 Academic AI1.1.2 Game AI1.2 Model of Game AI1.2.1 Movement1.2.2 Decision Making1.2.3 Strategy1.2.4 Infrastructure1.2.5 Agent-Based AI1.2.6 In the Book1.3 Algorithms and Data Structures1.3.1 Algorithms1.3.2 Representations1.3.3 Implementation1.4 Layout of the Book
2.1 The Complexity Fallacy2.1.1 When Simple Things Look Good2.1.2 When Complex Things Look Bad2.1.3 The Perception Window2.1.4 Changes of Behavior2.2 The Kind of AI in Games2.2.1 Hacks2.2.2 Heuristics2.2.3 Algorithms2.3 Speed and Memory Constraints2.3.1 Processor Issues2.3.2 Memory Concerns2.3.3 Platforms2.4 The AI Engine2.4.1 Structure of an AI Engine2.4.2 Tool Concerns2.4.3 Putting It All Together

3.1 The Basics of Movement Algorithms3.1.1 Two-Dimensional Movement3.1.2 Statics3.1.3 Kinematics3.2 Kinematic Movement Algorithms3.2.1 Seek3.2.2 Wandering3.3 Steering Behaviors3.3.1 Steering Basics3.3.2 Variable Matching3.3.3 Seek and Flee3.3.4 Arrive3.3.5 Align3.3.6 Velocity Matching3.3.7 Delegated Behaviors3.3.8 Pursue and Evade3.3.9 Face3.3.10 Looking Where You’re Going3.3.11 Wander3.3.12 Path Following3.3.13 Separation3.3.14 Collision Avoidance3.3.15 Obstacle and Wall Avoidance3.3.16 Summary3.4 Combining Steering Behaviors3.4.1 Blending and Arbitration3.4.2 Weighted Blending
3.4.4 Cooperative Arbitration3.4.5 Steering Pipeline3.5 Predicting Physics3.5.1 Aiming and Shooting3.5.2 Projectile Trajectory3.5.3 The Firing Solution3.5.4 Projectiles with Drag3.5.5 Iterative Targeting3.6 Jumping3.6.1 Jump Points3.6.2 Landing Pads3.6.3 Hole Fillers3.7 Coordinated Movement3.7.1 Fixed Formations3.7.2 Scalable Formations3.7.3 Emergent Formations3.7.4 Two-Level Formation Steering3.7.5 Implementation3.7.6 Extending to More Than Two Levels3.7.7 Slot Roles and Better Assignment3.7.8 Slot Assignment3.7.9 Dynamic Slots and Plays3.7.10 Tactical Movement3.8 Motor Control3.8.1 Output Filtering3.8.2 Capability-Sensitive Steering3.8.3 Common Actuation Properties3.9 Movement in the Third Dimension3.9.1 Rotation in Three Dimensions3.9.2 Converting Steering Behaviors to Three Dimensions3.9.3 Align3.9.4 Align to Vector3.9.5 Face3.9.6 Look Where You’re Going3.9.7 Wander3.9.8 Faking Rotation Axes
4.1 The Pathfinding Graph4.1.1 Graphs4.1.2 Weighted Graphs4.1.3 Directed Weighted Graphs4.1.4 Terminology4.1.5 Representation4.2 Dijkstra4.2.1 The Problem4.2.2 The Algorithm4.2.3 Pseudo-Code4.2.4 Data Structures and Interfaces4.2.5 Performance of Dijkstra4.2.6 Weaknesses4.3 A*4.3.1 The Problem4.3.2 The Algorithm4.3.3 Pseudo-Code4.3.4 Data Structures and Interfaces4.3.5 Implementation Notes4.3.6 Algorithm Performance4.3.7 Node Array A*4.3.8 Choosing a Heuristic4.4 World Representations4.4.1 Tile Graphs4.4.2 Dirichlet Domains4.4.3 Points of Visibility4.4.4 Navigation Meshes4.4.5 Non-Translational Problems4.4.6 Cost Functions4.4.7 Path Smoothing4.5 Improving on A*4.6 Hierarchical Pathfinding4.6.1 The Hierarchical Pathfinding Graph4.6.2 Pathfinding on the Hierarchical Graph4.6.3 Hierarchical Pathfinding on Exclusions4.6.4 Strange Effects of Hierarchies on Pathfinding4.6.5 Instanced Geometry4.7 Other Ideas in Pathfinding4.7.1 Open Goal Pathfinding4.7.2 Dynamic Pathfinding4.7.3 Other Kinds of Information Reuse4.7.4 Low Memory Algorithms4.7.5 Interruptible Pathfinding4.7.6 Pooling Planners4.8 Continuous Time Pathfinding4.8.1 The Problem4.8.2 The Algorithm4.8.3 Implementation Notes4.8.4 Performance4.8.5 Weaknesses4.9 Movement Planning4.9.1 Animations4.9.2 Movement Planning4.9.3 Example4.9.4 Footfalls
5.1 Overview of Decision Making5.2 Decision Trees5.2.1 The Problem5.2.2 The Algorithm5.2.3 Pseudo-Code5.2.4 Knowledge Representation5.2.5 Implementation Notes5.2.6 Performance of Decision Trees5.2.7 Balancing the Tree5.2.8 Beyond the Tree5.2.9 Random Decision Trees5.3 State Machines5.3.1 The Problem5.3.2 The Algorithm5.3.3 Pseudo-Code5.3.4 Data Structures and Interfaces5.3.5 Performance5.3.6 Implementation Notes5.3.7 Hard-Coded FSM5.3.8 Hierarchical State Machines5.3.9 Combining Decision Trees and State Machines5.4 Behavior Trees5.4.1 Implementing Behavior Trees5.4.2 Pseudo-Code5.4.3 Decorators5.4.4 Concurrency and Timing5.4.5 Adding Data to Behavior Trees5.4.6 Reusing Trees5.4.7 Limitations of Behavior Trees5.5 Fuzzy Logic5.5.1 A Warning5.5.2 Introduction to Fuzzy Logic5.5.3 Fuzzy Logic Decision Making5.5.4 Fuzzy State Machines
5.6.1 Markov Processes5.6.2 Markov State Machine5.7 Goal-Oriented Behavior5.7.1 Goal-Oriented Behavior5.7.2 Simple Selection5.7.3 Overall Utility5.7.4 Timing5.7.5 Overall Utility GOAP5.7.6 GOAP with IDA*5.7.7 Smelly GOB5.8 Rule-Based Systems5.8.1 The Problem5.8.2 The Algorithm5.8.3 Pseudo-Code5.8.4 Data Structures and Interfaces5.8.5 Rule Arbitration5.8.6 Unification5.8.7 Rete5.8.8 Extensions5.8.9 Where Next5.9 Blackboard Architectures5.9.1 The Problem5.9.2 The Algorithm5.9.3 Pseudo-Code5.9.4 Data Structures and Interfaces5.9.5 Performance5.9.6 Other Things Are Blackboard Systems5.10 Action Execution5.10.1 Types of Action5.10.2 The Algorithm5.10.3 Pseudo-Code5.10.4 Data Structures and Interfaces5.10.5 Implementation Notes5.10.6 Performance5.10.7 Putting It All Together
6.1 Waypoint Tactics6.1.1 Tactical Locations6.1.2 Using Tactical Locations6.1.3 Generating the Tactical Properties of a Waypoint6.1.4 Automatically Generating the Waypoints6.1.5 The Condensation Algorithm6.2 Tactical Analyses6.2.1 Representing the Game Level6.2.2 Simple Influence Maps6.2.3 Terrain Analysis6.2.4 Learning with Tactical Analyses6.2.5 A Structure for Tactical Analyses6.2.6 Map Flooding6.2.7 Convolution Filters6.2.8 Cellular Automata6.3 Tactical Pathfinding6.3.1 The Cost Function6.3.2 Tactic Weights and Concern Blending6.3.3 Modifying the Pathfinding Heuristic6.3.4 Tactical Graphs for Pathfinding6.3.5 Using Tactical Waypoints6.4 Coordinated Action6.4.1 Multi-Tier AI6.4.2 Emergent Cooperation6.4.3 Scripting Group Actions6.4.4 Military Tactics
7.1 Learning Basics7.1.1 Online or Offline Learning7.1.2 Intra-Behavior Learning7.1.3 Inter-Behavior Learning7.1.4 A Warning7.1.5 Over-Learning7.1.6 The Zoo of Learning Algorithms7.1.7 The Balance of Effort7.2 Parameter Modification7.2.1 The Parameter Landscape7.2.2 Hill Climbing7.2.3 Extensions to Basic Hill Climbing7.2.4 Annealing7.3 Action Prediction7.3.1 Left or Right7.3.2 Raw Probability7.3.3 String Matching7.3.4 N-Grams7.3.5 Window Size7.3.6 Hierarchical N-Grams7.3.7 Application in Combat7.4 Decision Learning7.4.1 The Structure of Decision Learning7.4.2 What Should You Learn?7.4.3 Four Techniques7.5 Naive Bayes Classifiers7.5.1 Pseudo-Code7.5.2 Implementation Notes7.6 Decision Tree Learning7.6.1 ID37.6.2 ID3 with Continuous Attributes7.6.3 Incremental Decision Tree Learning7.7 Reinforcement Learning7.7.1 The Problem7.7.2 The Algorithm7.7.3 Pseudo-Code7.7.4 Data Structures and Interfaces7.7.5 Implementation Notes7.7.6 Performance7.7.7 Tailoring Parameters7.7.8 Weaknesses and Realistic Applications7.7.9 Other Ideas in Reinforcement Learning7.8 Artificial Neural Networks7.8.1 Overview7.8.2 The Problem7.8.3 The Algorithm7.8.4 Pseudo-Code7.8.5 Data Structures and Interfaces7.8.6 Implementation Caveats7.8.7 Performance7.8.8 Other Approaches7.9 Deep Learning7.9.1 What is Deep Learning?7.9.2 Data
8.1 Pseudorandom Numbers8.1.1 Numeric Mixing and Game Seeds8.1.2 Halton Sequence8.1.3 Phyllotaxic Angles8.1.4 Poisson Disk8.2 Lindenmayer Systems8.2.1 Simple L-systems8.2.2 Adding Randomness to L-systems8.2.3 Stage-Specific Rules8.3 Landscape Generation8.3.1 Modifiers and Height-Maps8.3.2 Noise8.3.3 Perlin Noise8.3.4 Faults8.3.5 Thermal Erosion8.3.6 Hydraulic Erosion8.3.7 Altitude Filtering8.4 Dungeons and Maze Generation8.4.1 Mazes by Depth First Backtracking8.4.2 Minimum Spanning Tree Algorithms8.4.3 Recursive Subdivision8.4.4 Generate and Test8.5 Shape Grammars8.5.1 Running the Grammar8.5.2 Planning
9.1 Game Theory9.1.1 Types of Games9.1.2 The Game Tree9.2 Minimaxing9.2.1 The Static Evaluation Function9.2.2 Minimaxing9.2.3 The Minimaxing Algorithm9.2.4 Negamaxing9.2.5 AB Pruning9.2.6 The AB Search Window9.2.7 Negascout9.3 Transposition Tables and Memory9.3.1 Hashing Game States9.3.2 What to Store in the Table9.3.3 Hash Table Implementation9.3.4 Replacement Strategies9.3.5 A Complete Transposition Table9.3.6 Transposition Table Issues9.3.7 Using Opponent’s Thinking Time9.4 Memory-Enhanced Test Algorithms9.4.1 Implementing Test9.4.2 The MTD Algorithm9.4.3 Pseudo-Code9.5 Monte Carlo Tree Search (MCTS)9.5.1 Pure Monte Carlo Tree Search9.5.2 Adding Knowledge9.6 Opening Books and Other Set Plays9.6.1 Implementing an Opening Book9.6.2 Learning for Opening Books9.6.3 Set Play Books9.7 Further Optimizations9.7.1 Iterative Deepening9.7.2 Variable Depth Approaches9.8 Game Knowledge9.8.1 Creating a Static Evaluation Function9.8.2 Learning the Static Evaluation Function9.9 Turn-Based Strategy Games9.9.1 Impossible Tree Size9.9.2 Real-Time AI in a Turn-Based Game
10.1 Scheduling10.1.1 The Scheduler10.1.2 Interruptible Processes10.1.3 Load-Balancing Scheduler10.1.4 Hierarchical Scheduling10.1.5 Priority Scheduling10.2 Anytime Algorithms10.3 Level of Detail10.3.1 Graphics Level of Detail10.3.2 AI LOD10.3.3 Scheduling LOD10.3.4 Behavioral LOD10.3.5 Group LOD10.3.6 In Summary
11.1 Communication11.1.1 Polling11.1.2 Events11.1.3 Determining Which Approach to Use11.2 Event Managers11.2.1 Implementation11.2.2 Event Casting11.2.3 Inter-Agent Communication11.3 Polling Stations11.3.1 Pseudo-Code11.3.2 Performance11.3.3 Implementation Notes11.3.4 Abstract Polling11.4 Sense Management11.4.1 Faking It11.4.2 What Do We Know?11.4.3 Sensory Modalities11.4.4 Region Sense Manager11.4.5 Finite Element Model Sense Manager
12.0.1 Toolchains Limit AI12.0.2 Where AI Knowledge Comes From12.1 Knowledge for Pathfinding and Waypoints12.1.1 Manually Creating Region Data12.1.2 Automatic Graph Creation12.1.3 Geometric Analysis12.1.4 Data Mining12.2 Knowledge for Movement12.2.1 Obstacles12.2.2 High-Level Staging12.3 Knowledge for Decision Making12.3.1 Object Types12.3.2 Concrete Actions12.4 The Toolchain12.4.1 Integrated Game Engines12.4.2 Custom Data-Driven Editors12.4.3 AI Design Tools12.4.4 Remote Debugging12.4.5 Plug-Ins
13.1 Implementation Language13.1.1 C++13.1.2 C#13.1.3 Swift13.1.4 Java13.1.5 JavaScript13.2 Scripted AI13.2.1 What Is Scripted AI?13.2.2 What Makes a Good Scripting Language?13.2.3 Embedding13.2.4 Choosing an Open Source Language13.2.5 A Language Selection13.3 Creating a Language13.3.1 Rolling Your Own
14.1 The Design14.1.1 Example14.1.2 Evaluating the Behaviors14.1.3 Selecting Techniques14.1.4 The Scope of One Game14.2 Shooters14.2.1 Movement and Firing14.2.2 Decision Making14.2.3 Perception14.2.4 Pathfinding and Tactical AI14.2.5 Shooter-Like Games14.2.6 Melee Combat14.3 Driving14.3.1 Movement14.3.2 Pathfinding and Tactical AI14.3.3 Driving-Like Games14.4 Real-Time Strategy14.4.1 Pathfinding14.4.2 Group Movement14.4.3 Tactical and Strategic AI14.4.4 Decision Making14.4.5 MOBAs14.5 Sports14.5.1 Physics Prediction14.5.2 Playbooks and Content Creation14.6 Turn-Based Strategy Games14.6.1 Timing14.6.2 Helping the Player
15.1 Teaching Characters15.1.1 Representing Actions15.1.2 Representing the World15.1.3 Learning Mechanism15.1.4 Predictable Mental Models15.2 Flocking and Herding Games15.2.1 Making the Creatures15.2.2 Tuning Steering for Interactivity15.2.3 Steering Behavior Stability15.2.4 Ecosystem Design
Books, Periodicals, Papers and WebsitesGames

Overview

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.