You are previewing Game AI Pro 2.
O'Reilly logo
Game AI Pro 2

Book Description

Game AI Pro2: Collected Wisdom of Game AI Professionals presents cutting-edge tips, tricks, and techniques for artificial intelligence (AI) in games, drawn from developers of shipped commercial games as well as some of the best-known academics in the field. It contains knowledge, advice, hard-earned wisdom, and insights gathered from across the community of developers and researchers who have devoted themselves to game AI.

In this book, 47 expert developers and researchers have come together to bring you their newest advances in game AI, along with twists on proven techniques that have shipped in some of the most successful commercial games of the last few years. The book provides a toolbox of proven techniques that can be applied to many common and not-so-common situations. It is written to be accessible to a broad range of readers. Beginners will find good general coverage of game AI techniques and a number of comprehensive overviews, while intermediate to expert professional game developers will find focused, deeply technical chapters on specific topics of interest to them.

  • Covers a wide range of AI in games, with topics applicable to almost any game
  • Touches on most, if not all, of the topics necessary to get started in game AI
  • Provides real-life case studies of game AI in published commercial games
  • Gives in-depth, technical solutions from some of the industry’s best-known games
  • Includes downloadable demos and/or source code, available at http://www.gameaipro.com

Table of Contents

  1. Preface
  2. Acknowledgments
  3. Web Materials
    1. General System Requirements
    2. Updates
    3. Comments and Suggestions
  4. Editors
  5. Contributors
  6. Section I - General Wisdom
    1. Chapter 1 - Game AI Appreciation, Revisited
      1. 1.1 Introduction
      2. 1.2 What Is Game AI?
      3. 1.3 Fuzzy Border
      4. 1.4 AI as the Nexus of Game Development
      5. 1.5 Frontiers of the Field
        1. 1.5.1 Pathfinding
        2. 1.5.2 Conversations
        3. 1.5.3 Dynamic Storylines
        4. 1.5.4 Player Modeling
        5. 1.5.5 Modeling and Displaying Emotion
        6. 1.5.6 Social Relationships
        7. 1.5.7 Scale
        8. 1.5.8 Content Explosion
        9. 1.5.9 The Unexplored
      6. 1.6 Conclusion
      7. References
    2. Chapter 2 - Combat Dialogue in FEAR: The Illusion of Communication
      1. 2.1 Introduction
      2. 2.2 From Barks to Dialogues
      3. 2.3 Conclusion
      4. References
    3. Chapter 3 - Dual-Utility Reasoning
      1. 3.1 Introduction
      2. 3.2 Dual-Utility Reasoning
      3. 3.3 Dual-Utility Reasoning in Zoo Tycoon 2
      4. 3.4 Conclusion
      5. Reference
    4. Chapter 4 - Vision Zones and Object Identification Certainty
      1. 4.1 Introduction
      2. 4.2 Vision Zones and Object Identification Certainty
        1. 4.2.1 Vision Sweet Spot
      3. 4.3 Incorporating Movement and Camouflage
      4. 4.4 Producing Appropriate Behavior from Identification Certainty
        1. 4.4.1 Alternative 1: Object Certainty with Time
        2. 4.4.2 Alternative 2: Explicit Detection Feedback
      5. 4.5 Conclusion
      6. References
    5. Chapter 5 - Agent Reaction Time: How Fast Should an AI React?
      1. 5.1 Introduction
      2. 5.2 Context Is Key
      3. 5.3 What Does Cognitive Research Tell Us?
        1. 5.3.1 Simple Reaction Time
        2. 5.3.2 Recognition or Go/No-Go Time
        3. 5.3.3 Complex Cognitive Task Reaction Time
      4. 5.4 Conclusion
      5. References
    6. Chapter 6 - Preventing Animation Twinning Using a Simple Blackboard
      1. 6.1 Introduction
      2. 6.2 Animation Twinning
      3. 6.3 Animation Blackboard
      4. 6.4 Delay Times and Animation Considerations
      5. 6.5 Conclusion
      6. Reference
  7. Section II - Architecture
    1. Chapter 7 - Possibility Maps for Opportunistic AI and Believable Worlds
      1. 7.1 Introduction
      2. 7.2 What Are Probability and Possibility Maps?
      3. 7.3 Using Possibility Maps
      4. 7.4 Updating Probability Maps
      5. 7.5 Combining Possibility and Probability Maps
      6. 7.6 Factorizing Game State
      7. 7.7 Conclusion
    2. Chapter 8 - Production Rules Implementation in 1849
      1. 8.1 Introduction
      2. 8.2 Game Mechanics and Production Rules
        1. 8.2.1 Game Mechanics
        2. 8.2.2 Game Simulation
      3. 8.3 Rule System
        1. 8.3.1 Resources
        2. 8.3.2 Resource Bins
        3. 8.3.3 Conditions and Actions
        4. 8.3.4 Rule Execution
      4. 8.4 Performance
        1. 8.4.1 Condition Checking Frequency
        2. 8.4.2 Condition Definition Language
        3. 8.4.3 Data Model
      5. 8.5 Lessons from 1849
        1. 8.5.1 Benefits
        2. 8.5.2 Lessons
      6. 8.6 Related Work
      7. 8.7 Conclusion
      8. References
    3. Chapter 9 - Production Systems: New Techniques in AAA Games
      1. 9.1 Introduction
        1. 9.1.1 Terminology
        2. 9.1.2 Design Considerations
      2. 9.2 What Decisions Is the System Trying to Make?
      3. 9.3 Choice of Rules Representation
      4. 9.4 Method of Rules Authoring
        1. 9.4.1 Recorded Rule System
        2. 9.4.2 More Typical Systems
      5. 9.5 Choice of Matching System
        1. 9.5.1 Greedy Matching/Selection
      6. 9.6 What Happens If the AI Fails to Find a Rule?
      7. 9.7 What Happens If There Are Multiple Rules?
      8. 9.8 Execution and the Design of the RHS
        1. 9.8.1 More Complex RHS
      9. 9.9 Debugging and Tuning
      10. 9.10 Conclusion
      11. References
    4. Chapter 10 - Building a Risk-Free Environment to Enhance Prototyping: Hinted-Execution Behavior Trees
      1. 10.1 Introduction
      2. 10.2 Explaining the Problem
      3. 10.3 Behavior Trees
        1. 10.3.1 Simple BT
        2. 10.3.2 Tree Complexity
      4. 10.4 Extending the Model
        1. 10.4.1 Hint Concept
        2. 10.4.2 HeBT Selectors
        3. 10.4.3 Hints and Conditions
      5. 10.5 Multilevel Architecture
        1. 10.5.1 Behavior Controllers
        2. 10.5.2 Exposing Hints to Higher Levels
      6. 10.6 More Complex Example
        1. 10.6.1 Prototyping New Ideas
        2. 10.6.2 Base Behavior
        3. 10.6.3 Prototype Idea
        4. 10.6.4 Creating a High-Level Tree
        5. 10.6.5 Analyzing the Results
      7. 10.7 Other Applications
        1. 10.7.1 Adaptation
        2. 10.7.2 Group Behaviors
      8. 10.8 Conclusion
      9. References
    5. Chapter 11 - Smart Zones to Create the Ambience of Life
      1. 11.1 Introduction
      2. 11.2 Designing an Ambience of Life
        1. 11.2.1 What Is a Living Scene?
        2. 11.2.2 Performing Living Scenes through Smart Zones
      3. 11.3 Smart Zones in Practice
        1. 11.3.1 Definition of Smart Zones by Game Designers
        2. 11.3.2 Functioning of the Smart Zone Architecture
          1. 11.3.2.1 Trigger Management
          2. 11.3.2.2 Role Assignment
          3. 11.3.2.3 Behavior Orchestration
        3. 11.3.3 NPC Behaviors
          1. 11.3.3.1 Role Interruption
          2. 11.3.3.2 Management of Overlapping Zones
      4. 11.4 Concrete Example
        1. 11.4.1 Scenario and the Smart Zones
        2. 11.4.2 Implementation in Unity3D
      5. 11.5 Conclusion
      6. Acknowledgments
      7. References
    6. Chapter 12 - Separation of Concerns Architecture for AI and Animation
      1. 12.1 Introduction
      2. 12.2 Animation Graphs
      3. 12.3 Complexity Explosion and the Problem of Scalability
      4. 12.4 SoC
      5. 12.5 Separating Gameplay and Animation
      6. 12.6 Animation Behaviors
      7. 12.7 Animation Controller
      8. 12.8 Benefits of an SoC Animation Architecture
        1. 12.8.1 Functional Testing
        2. 12.8.2 System Refactoring
        3. 12.8.3 Level of Detail
      9. 12.9 Conclusion
      10. References
    7. Chapter 13 - Optimizing Practical Planning for Game AI
      1. 13.1 Introduction
        1. 13.1.1 Required Background
      2. 13.2 How Can You Optimize?
        1. 13.2.1 Measure It!
        2. 13.2.2 Design Valuable Tests!
        3. 13.2.3 Use Profilers!
      3. 13.3 Practical Planning Data Structures
        1. 13.3.1 Actions
        2. 13.3.2 Plans
        3. 13.3.3 States
      4. 13.4 Practical Planning Algorithms
        1. 13.4.1 Iterating over Subsets of State Predicates
        2. 13.4.2 Recording Where the Action Parameters Occur in the Action Predicates
      5. 13.5 Conclusion
      6. References
  8. Section III - Movement and Pathfinding
    1. Chapter 14 - JPS+: An Extreme A* Speed Optimization for Static Uniform Cost Grids
      1. 14.1 Introduction
      2. 14.2 Pruning Strategy
      3. 14.3 Forced Neighbors
      4. 14.4 Jump Points
        1. 14.4.1 Primary Jump Points
        2. 14.4.2 Straight Jump Points
        3. 14.4.3 Diagonal Jump Points
      5. 14.5 Wall Distances
      6. 14.6 Map Preprocess Implementation
      7. 14.7 Runtime Implementation
      8. 14.8 Conclusion
      9. References
    2. Chapter 15 - Subgoal Graphs for Fast Optimal Pathfinding
      1. 15.1 Introduction
      2. 15.2 Preliminaries
      3. 15.3 Simple Subgoal Graphs
        1. 15.3.1 Constructing Simple Subgoal Graphs
        2. 15.3.2 Searching Using Simple Subgoal Graphs
        3. 15.3.3 Identifying All Direct-H-Reachable Subgoals from a Given Cell
      4. 15.4 Two-Level Subgoal Graphs
        1. 15.4.1 Constructing Two-Level Subgoal Graphs
        2. 15.4.2 Searching Using Two-Level Subgoal Graphs
      5. 15.5 N-Level Graphs
      6. 15.6 Conclusion
      7. Acknowledgments
      8. References
    3. Chapter 16 - Theta* for Any-Angle Pathfinding
      1. 16.1 Introduction
      2. 16.2 Problem Formalization
      3. 16.3 A* Algorithm
      4. 16.4 Theta* Algorithm
      5. 16.5 Theta* Paths
      6. 16.6 Analysis
      7. 16.7 Conclusion
      8. Acknowledgment
      9. References
    4. Chapter 17 - Advanced Techniques for Robust, Efficient Crowds
      1. 17.1 Introduction
      2. 17.2 Pathfinding’s Utopian Worldview
      3. 17.3 Congestion Map Approach
      4. 17.4 Augmenting Path Planning with Congestion Maps
      5. 17.5 Path Smoothing
      6. 17.6 Flow Fields with Congestion Maps and Theta
      7. 17.7 Current Alternatives
      8. 17.8 Benefits
      9. 17.9 Drawbacks
      10. 17.10 Performance Considerations
      11. 17.11 Future Work
      12. 17.12 Conclusion
      13. References
    5. Chapter 18 - Context Steering: Behavior-Driven Steering at the Macro Scale
      1. 18.1 Introduction
      2. 18.2 When Steering Behaviors Go Bad
        1. 18.2.1 Flocks versus Groups
        2. 18.2.2 Lack of Context
      3. 18.3 Toward Why, Not How
        1. 18.3.1 Context Maps
      4. 18.4 Context Maps by Example
        1. 18.4.1 Chase Behavior
        2. 18.4.2 Avoid Behavior
        3. 18.4.3 Combining and Parsing
        4. 18.4.4 Subslot Movement
      5. 18.5 Racing with Context
        1. 18.5.1 Coordinate System
        2. 18.5.2 Racing Line Behavior
        3. 18.5.3 Avoid Behavior
        4. 18.5.4 Drafting Behavior
        5. 18.5.5 Processing Context Maps
      6. 18.6 Advanced Techniques
        1. 18.6.1 Post-Processing
        2. 18.6.2 Optimizations
      7. 18.7 Conclusion
      8. References
    6. Chapter 19 - Guide to Anticipatory Collision Avoidance
      1. 19.1 Introduction
      2. 19.2 Key Concepts
        1. 19.2.1 Agent State
        2. 19.2.2 Predicting Collisions (Time to Collision)
        3. 19.2.3 Time Horizon
      3. 19.3 Prototype Implementation
        1. 19.3.1 Agent Forces
        2. 19.3.2 Avoidance Force
          1. 19.3.2.1 Avoidance Force Direction
          2. 19.3.2.2 Avoidance Force Magnitude
          3. 19.3.2.3 Corner Cases
          4. 19.3.2.4 Code
        3. 19.3.3 Runtime Performance
        4. 19.3.4 Parameter Tuning
      4. 19.4 Advanced Approaches
        1. 19.4.1 Human Motion Simulation
          1. 19.4.1.1 Personal Space
          2. 19.4.1.2 Field of View
          3. 19.4.1.3 Distance to Collision
          4. 19.4.1.3 Randomized Perturbation
        2. 19.4.2 Guaranteed Collision Avoidance
        3. 19.4.3 Herd’Em!
      5. 19.5 Conclusion
      6. References
    7. Chapter 20 - Hierarchical Architecture for Group Navigation Behaviors
      1. 20.1 Introduction
      2. 20.2 Group Navigation
        1. 20.2.1 Flocks
        2. 20.2.2 Formations
        3. 20.2.3 Social Groups
      3. 20.3 Navigation Pipeline Architecture
        1. 20.3.1 Navigation Behaviors
        2. 20.3.2 Navigation Pipeline
      4. 20.4 Group to Members Relationship Model
        1. 20.4.1 Leader
        2. 20.4.2 Virtual Group Entity
        3. 20.4.3 Hierarchical Entity Architecture
      5. 20.5 Pathfinding
      6. 20.6 Emergent Group Structure
        1. 20.6.1 Boids and Derivatives
        2. 20.6.2 “Local” Formations
        3. 20.6.3 Implementing an Emergent Group
      7. 20.7 Choreographed Formations
        1. 20.7.1 Formation Design
        2. 20.7.2 Slots Assignment
        3. 20.7.3 “Blind” Formation Following
        4. 20.7.4 Autonomous Formation Following
      8. 20.8 Group Collision Avoidance
        1. 20.8.1 Velocity Correction
        2. 20.8.2 Formation Adaptation
      9. 20.9 Conclusion
      10. References
    8. Chapter 21 - Dynamic Obstacle Navigation in Fuse
      1. 21.1 Introduction
      2. 21.2 Fuse Traversal Setups
      3. 21.3 Climb Mesh Generation
        1. 21.3.1 Path Following on Climb Meshes
        2. 21.3.2 Caveats of the Climb Path Generation
      4. 21.4 Parsing Climb Paths
        1. 21.4.1 Generating Virtual Controller Input
      5. 21.5 Conclusion
      6. References
  9. Section IV - Applied Search Techniques
    1. Chapter 22 - Introduction to Search for Games
      1. 22.1 Introduction
      2. 22.2 Illustrative Example
      3. 22.3 Basic Search Requirements
        1. 22.3.1 Efficient State Representation
      4. 22.4 Alternate Uses of Search
      5. 22.5 Bottlenecks for Search
      6. 22.6 Conclusion
    2. Chapter 23 - Personality Reinforced Search for Mobile Strategy Games
      1. 23.1 Introduction
      2. 23.2 Turn-Based Strategy War Games Based on “Euro” Board Games
      3. 23.3 Evolution and the Triune Brain
      4. 23.4 Personality First
      5. 23.5 Neocortex
      6. 23.6 State Evaluation
      7. 23.7 Limbic Brain
      8. 23.8 Evolution and the Genetic Algorithm
      9. 23.9 AI Chromosomes
      10. 23.10 Conclusion
      11. References
    3. Chapter 24 - Interest Search: A Faster Minimax
      1. 24.1 Introduction
      2. 24.2 Background
      3. 24.3 Rethinking Selective Search
      4. 24.4 Selection by Variation: Interest Search
      5. 24.5 Quantifying the Interest Search Idea
      6. 24.6 Classifying the Moves in Terms of Interest
      7. 24.7 Does This Work?
      8. 24.8 Performance of Interest Search for Treebeard Chess
      9. 24.9 Applying Interest Search to Japanese Chess (Shogi)
      10. 24.10 Dynamic Calculation of Score and Interest
      11. 24.11 Impact of Interest Search on Shogi
      12. 24.12 Analysis
      13. 24.13 Other Games
      14. 24.14 Conclusion
      15. References
    4. Chapter 25 - Monte Carlo Tree Search and Related Algorithms for Games
      1. 25.1 Introduction
      2. 25.2 Background
      3. 25.3 Algorithm 1: Online UCB1
        1. 25.3.1 Applying to Games
      4. 25.4 Algorithm 2: Regret Matching
        1. 25.4.1 Applying to Games
      5. 25.5 Algorithm 3: Offline UCB1
      6. 25.6 Algorithm 4: UCT
        1. 25.6.1 Important Implementation Details
        2. 25.6.2 UCT Enhancements and Variations
        3. 25.6.3 Applying to Games
      7. 25.7 Conclusion
      8. References
    5. Chapter 26 - Rolling Your Own Finite-Domain Constraint Solver
      1. 26.1 Introduction
      2. 26.2 Simple Example
      3. 26.3 Algorithm 1: Brute Force
      4. 26.4 Algorithm 2: Backward Checking
      5. 26.5 Algorithm 3: Forward Checking
      6. 26.6 Detecting Inconsistencies
      7. 26.7 Algorithm 4: Forward Checking with Backtracking and Undo
      8. 26.8 Gory Implementation Details
      9. 26.9 Extensions and Optimizations
        1. 26.9.1 Finite-Domain Representation
        2. 26.9.2 Constraint Arcs and the Work Queue
        3. 26.9.3 Randomized Solutions
        4. 26.9.4 Variable Ordering
      10. 26.10 Conclusion
      11. References
  10. Section V - Tactics, Strategy, and Spatial Awareness
    1. Chapter 27 - Looking for Trouble: Making NPCs Search Realistically
      1. 27.1 Introduction
      2. 27.2 Types of Searching
        1. 27.2.1 Cautious Search
        2. 27.2.2 Aggressive Search
      3. 27.3 Triggering a Search
        1. 27.3.1 Initial Stimulus-Based Trigger
        2. 27.3.2 Losing a Target
      4. 27.4 Phases of Searching
        1. 27.4.1 Phase 1
          1. 27.4.1.1 Cautious
          2. 27.4.1.2 Aggressive
        2. 27.4.2 Phase 2
          1. 27.4.2.1 Generation of Search Spots
          2. 27.4.2.2 Performing the Search
          3. 27.4.2.3 Selecting the Best Search Spot
        3. 27.4.3 Improving Phase 2 Search: Gap Detection
        4. 27.4.4 Ending the Search
      5. 27.5 Conclusion
      6. References
    2. Chapter 28 - Modeling Perception and Awareness in Tom Clancy’s Splinter Cell Blacklist
      1. 28.1 Introduction
        1. 28.1.1 Fairness
        2. 28.1.2 Consistency
        3. 28.1.3 Good Feedback
        4. 28.1.4 Intelligence
      2. 28.2 Visual Perception
      3. 28.3 Environmental Awareness
        1. 28.3.1 Connectivity
        2. 28.3.2 Changed Objects
      4. 28.4 Auditory Perception
        1. 28.4.1 Calculating Audio Distance
        2. 28.4.2 Auditory Detection Fairness
      5. 28.5 Social/Contextual Awareness
        1. 28.5.1 Social Awareness: Conversation
        2. 28.5.2 Contextual Awareness: Unreachable Area
        3. 28.5.3 Disappearing NPC Problem
      6. 28.6 Conclusion
      7. References
    3. Chapter 29 - Escaping the Grid: Infinite-Resolution Influence Mapping
      1. 29.1 Introduction
      2. 29.2 Influence Mapping
      3. 29.3 Limitations
      4. 29.4 Point-Based Influence
      5. 29.5 Making Queries Fast
      6. 29.6 Temporal Influence Propagation
      7. 29.7 Handling Obstacles and Nontrivial Topologies
      8. 29.8 Optimization Queries
      9. 29.9 Traveling to the Third Dimension
      10. 29.10 Example Implementation
      11. 29.11 Suitability Considerations
        1. 29.11.1 Influence Source Density
        2. 29.11.2 Query Point Density
        3. 29.11.3 Update Frequency
        4. 29.11.4 Need for Precise or Extremely Accurate Results
      12. 29.12 Conclusion
      13. References
    4. Chapter 30 - Modular Tactical Influence Maps
      1. 30.1 Introduction
      2. 30.2 Influence Map Overview
      3. 30.3 Propagation
      4. 30.4 Architecture
        1. 30.4.1 Base Map Structure
        2. 30.4.2 Types of Base Maps
        3. 30.4.3 Templates
        4. 30.4.4 Working Maps
      5. 30.5 Population of Map Data
      6. 30.6 Information Retrieval
        1. 30.6.1 Values at a Point
        2. 30.6.2 Combinations of Maps
        3. 30.6.3 Special Functions
      7. 30.7 Usage
        1. 30.7.1 Information
        2. 30.7.2 Targeting
        3. 30.7.3 Positioning
      8. 30.8 Examples
        1. 30.8.1 Location for Area of Effect Attack
        2. 30.8.2 Movement to Safer Spot
        3. 30.8.3 Nearest Battlefront Location
      9. 30.9 Conclusion
      10. References
    5. Chapter 31 - Spatial Reasoning for Strategic Decision Making
      1. 31.1 Introduction
      2. 31.2 Spatial Partitioning
        1. 31.2.1 Region Generation
        2. 31.2.2 Static vs. Dynamic Regions
      3. 31.3 Working with Regions
        1. 31.3.1 Picking Places to Scout or Explore
        2. 31.3.2 Picking Places to Attack
        3. 31.3.3 Picking Unit Positions
        4. 31.3.4 Path Planning
        5. 31.3.5 Distance Estimates
        6. 31.3.6 Region Path Caching
        7. 31.3.7 Recognizing Cul-de-Sacs and Chokepoints
      4. 31.4 Influence Maps
        1. 31.4.1 Influence Map Basics
        2. 31.4.2 Propagation Calculations
        3. 31.4.3 Force Estimates over Regions
        4. 31.4.4 Illusion of Intelligence
        5. 31.4.5 Border Calculations
      5. 31.5 Spatial Characteristics
        1. 31.5.1 Scent of Death
        2. 31.5.2 High-Traffic Areas
        3. 31.5.3 Avenues of Approach
        4. 31.5.4 Flanking Attacks
        5. 31.5.5 Attackable Obstacles
        6. 31.5.6 Counterattacks and Consolidation
      6. 31.6 Conclusion and Future Thoughts
      7. References
    6. Chapter 32 - Extending the Spatial Coverage of a Voxel-Based Navigation Mesh
      1. 32.1 Introduction
      2. 32.2 Overview of Voxel-Based Navmesh Generation
        1. 32.2.1 Voxel-Based Navmesh Goals
        2. 32.2.2 Enter Voxelization
        3. 32.2.4 Triangulating the Polygons
        4. 32.2.5 Recap
      3. 32.3 Extending the Navmesh’s Spatial Coverage
        1. 32.3.1 Reintroducing the Discarded Space
        2. 32.3.2 Using the Metadata
      4. 32.4 Identifying Other Spaces
        1. 32.4.1 Prone Navigation
        2. 32.4.2 Swim Navigation
        3. 32.4.3 Sidestep Navigation
        4. 32.4.4 Multiple Generation Parameter Passes and Hierarchy
      5. 32.5 Playing with the Heuristic
      6. 32.6 Conclusion
      7. References
  11. Section VI - Character Behavior
    1. Chapter 33 - Infected AI in The Last of Us
      1. 33.1 Introduction
      2. 33.2 The Infected
        1. 33.2.1 Senses
        2. 33.2.2 Distractions
      3. 33.3 AI System
        1. 33.3.1 Philosophy
        2. 33.3.2 Data-Driven Design
        3. 33.3.3 Implementation
        4. 33.3.4 Debugging
      4. 33.4 Skills and Behaviors
        1. 33.4.1 Search Skill
        2. 33.4.2 Chase Skill
        3. 33.4.3 Follow Skill
        4. 33.4.4 Ambush Skill
        5. 33.4.5 Throw Skill
        6. 33.4.6 On-Fire Skill
        7. 33.4.7 Wander Skill
        8. 33.4.8 Sleep Skill
      5. 33.5 Conclusion
      6. References
    2. Chapter 34 - Human Enemy AI in The Last of Us
      1. 34.1 Introduction
      2. 34.2 Building Blocks
      3. 34.3 AI Perception
      4. 34.4 Cover and Posts
      5. 34.5 Skills, States, and Behaviors
      6. 34.6 Stealth
      7. 34.7 Lethality
      8. 34.8 Flanking
      9. 34.9 Polish
      10. 34.10 Conclusion
    3. Chapter 35 - Ellie: Buddy AI in The Last of Us
      1. 35.1 Introduction
      2. 35.2 Starting from Scratch
        1. 35.2.1 The Plan
        2. 35.2.2 Approach
      3. 35.3 Ambient Following
        1. 35.3.1 Follow Positions
        2. 35.3.2 Moving
        3. 35.3.3 Dodging
        4. 35.3.4 Teleportation
      4. 35.4 Taking Cover
        1. 35.4.1 Runtime Cover Generation
        2. 35.4.2 Cover Share
      5. 35.5 Combat Utility
        1. 35.5.1 Throwing
        2. 35.5.2 Grapples
        3. 35.5.3 Gifting
      6. 35.6 Armed Combat
        1. 35.6.1 Shooting
        2. 35.6.2 Balancing
        3. 35.6.3 Cheating
      7. 35.7 Finishing Touches
        1. 35.7.1 Vocalizations
        2. 35.7.2 Callouts
        3. 35.7.3 Ambience
      8. 35.8 Conclusion
    4. Chapter 36 - Realizing NPCs: Animation and Behavior Control for Believable Characters
      1. 36.1 Introduction
      2. 36.2 Character Movement
        1. 36.2.1 Movement Models
        2. 36.2.2 Decoupling Extracted Motion
        3. 36.2.3 Motion Correction
        4. 36.2.4 Correcting Displacement Direction and Orientation
          1. 36.2.4.1 Looping Animations
          2. 36.2.4.2 Transition and One-Off Animations
        5. 36.2.5 Correcting Speed
      3. 36.3 Interrupting and Blending Movement
        1. 36.3.1 Pose Matching
        2. 36.3.2 Pose-Only and Per-Bone Blending
      4. 36.4 Combining Actions
        1. 36.4.1 Animation Masking
        2. 36.4.2 Animation Mirroring
        3. 36.4.3 Animation Layering
      5. 36.5 Tracking
        1. 36.5.1 Additive Aiming Poses
        2. 36.5.2 Additive Aiming Animations
        3. 36.5.3 Inverse Kinematics
      6. 36.6 Behaviors
        1. 36.6.1 Creating Variety
          1. 36.6.1.1 Contextual One-Off Animations
          2. 36.6.1.2 Micro Behaviors
          3. 36.6.1.3 Using Additives with Idles
        2. 36.6.2 Behavior Distribution
          1. 36.6.2.1 Action Tokens
          2. 36.6.2.2 Blackboards
          3. 36.6.2.3 Action Ranking
          4. 36.6.2.4 On-Screen Realization
      7. 36.7 Conclusion
    5. Chapter 37 - Using Queues to Model a Merchant’s Inventory
      1. 37.1 Introduction
      2. 37.2 M/M/1 Queues
      3. 37.3 Modeling a Merchant’s Inventory
        1. 37.3.1 Computational Considerations
      4. 37.4 Conclusion
      5. References
    6. Chapter 38 - Psychologically Plausible Methods for Character Behavior Design
      1. 38.1 Introduction
      2. 38.2 Perception and Abstractions
      3. 38.3 Developmental Psychology and the Teleological Stance
      4. 38.4 Attribution Theory
      5. 38.5 Problem of Characters as Tokens
      6. 38.6 Practical Application of Psychology in Character Behavior Design
      7. 38.7 Conclusion
      8. References
  12. Section VII - Analytics, Content Generation, and Experience Management
  13. Chapter 39 - Analytics-Based AI Techniques for a Better Gaming Experience
    1. 39.1 Introduction
    2. 39.2 Game Analytics Approaches to Modeling User Performance, Skills, and Behaviors
      1. 39.2.1 Game Metrics
      2. 39.2.2 Analysis Techniques
        1. 39.2.2.1 Individual Analysis
        2. 39.2.2.2 Communal Analysis
    3. 39.3 Game Analytics and Adaptive Techniques
      1. 39.3.1 Skill-Based Difficulty Adaptation
      2. 39.3.2 Emotion-Based Adaptation
      3. 39.3.3 Style-Based Adaptation
    4. 39.4 Game Analytics and Recommendation Systems
    5. 39.5 Game Analytics and Team Matching Techniques
    6. 39.6 Conclusion
    7. References
  14. Chapter 40 - Procedural Content Generation: An Overview
    1. 40.1 Introduction
    2. 40.2 Technical Approaches to Content Generation
      1. 40.2.1 Algorithms and Approaches
        1. 40.2.1.1 Simulation Based
        2. 40.2.1.2 Constructionist
        3. 40.2.1.3 Grammars
        4. 40.2.1.4 Optimization
        5. 40.2.1.5 Constraint Driven
      2. 40.2.2 Knowledge Representation
        1. 40.2.2.1 Experiential Chunks
        2. 40.2.2.2 Templates
        3. 40.2.2.3 Components
        4. 40.2.2.4 Subcomponents
      3. 40.2.3 Mixing and Matching
    3. 40.3 Understanding PCG’s Relationship to a Game
      1. 40.3.1 PCG’s Mechanical Role
        1. 40.3.1.1 Game Stage
        2. 40.3.1.2 Interaction with the Generator
        3. 40.3.1.3 Control over Player Experience
      2. 40.3.2 Player Interaction with PCG
        1. 40.3.2.1 PCG Relationship to Other Mechanics
        2. 40.3.2.2 Reacting
        3. 40.3.2.3 Strategizing
        4. 40.3.2.4 Searching
        5. 40.3.2.5 Practicing
        6. 40.3.2.6 Community
    4. 40.4 Choosing an Approach
      1. 40.4.1 Getting Started
      2. 40.4.2 Game Design Constraints
      3. 40.4.3 Relationship with Art
      4. 40.4.4 Engineering Constraints
    5. 40.5 Tuning and Debugging a Content Generator
    6. 40.6 Conclusion
      1. 40.6.1 Tools and Frameworks
      2. 40.6.2 Reading and Community
    7. References
  15. Chapter 41 - Simulation Principles from Dwarf Fortress
    1. 41.1 Introduction
    2. 41.2 Principle 1: Don’t Overplan Your Model
    3. 41.3 Principle 2: Break Down and Understand the System
    4. 41.4 Principle 3: Don’t Overcomplicate
    5. 41.5 Principle 4: Base Your Model on Real-World Analogs
    6. 41.6 Conclusion
    7. References
  16. Chapter 42 - Techniques for AI-Driven Experience Management in Interactive Narratives
    1. 42.1 Introduction
    2. 42.2 AI-Driven Experience Management
      1. 42.2.1 Player in a Game Environment
      2. 42.2.2 AI Manager Modifying Narrative
      3. 42.2.3 Choosing between Stories
    3. 42.3 AI-Driven Experience Management: Common Techniques
      1. 42.3.1 Technique: Narrative Generation
      2. 42.3.2 Technique: Play Style Modeling
      3. 42.3.3 Technique: Goal Inference
      4. 42.3.4 Technique: Emotional Modeling
      5. 42.3.5 Technique: Objective Function Maximization
      6. 42.3.6 Technique: Machine-Learned Narrative Selection
    4. 42.4 Implementations
      1. 42.4.1 PaSSAGE
      2. 42.4.2 PAST
      3. 42.4.3 PACE
      4. 42.4.4 SCoReS
    5. 42.5 Conclusion and Future Work
    6. References