Programming Game AI by Example

Programming Game AI by Example

by Mat Buckland
Released September 2004
Publisher(s): Jones & Bartlett Learning
ISBN: 9781449613068

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


Programming Game AI by Example provides a comprehensive and practical introduction to the “bread and butter” AI techniques used by the game development industry, leading the reader through the process of designing, programming, and implementing intelligent agents for action games using the C++ programming language.

Techniques covered include state- and goal-based behavior, inter-agent communication, individual and group steering behaviors, team AI, graph theory, search, path planning and optimization, triggers, scripting, scripted finite state machines, perceptual modeling, goal evaluation, goal arbitration, and fuzzy logic.

Table of contents

  1. Testimonials
  2. Contents (1/2)
  3. Contents (2/2)
  4. Foreword
  5. Acknowledgments
  6. Introduction
  7. Chapter 1 A Math and Physics Primer
    1. Mathematics
      1. Cartesian Coordinates
      2. Functions and Equations (1/2)
      3. Functions and Equations (2/2)
        1. Exponents and Powers
        2. Roots of Numbers (Radicals)
        3. Simplifying Equations
      4. Trigonometry (1/2)
      5. Trigonometry (2/2)
        1. Rays and Line Segments
        2. Angles
        3. Triangles
      6. Vectors (1/2)
      7. Vectors (2/2)
        1. Adding and Subtracting Vectors
        2. Multiplying Vectors
        3. Calculating the Magnitude of a Vector
        4. Normalizing Vectors
        5. Resolving Vectors
        6. The Dot Product
        7. A Practical Example of Vector Mathematics
        8. The Vector2D Struct
      8. Local Space and World Space
    2. Physics
      1. Time
      2. Distance
      3. Mass
      4. Position
      5. Velocity
      6. Acceleration (1/2)
      7. Acceleration (2/2)
      8. Force
    3. Summing Up
  8. Chapter 2 State-Driven Agent Design
    1. What Exactly Is a Finite State Machine?
    2. Implementing a Finite State Machine
      1. State Transition Tables
      2. Embedded Rules
    3. The West World Project
      1. The BaseGameEntity Class
      2. The Miner Class
      3. The Miner States
      4. The State Design Pattern Revisited
      5. The EnterMineAndDigForNugget State
    4. Making the State Base Class Reusable
    5. Global States and State Blips
    6. Creating a State Machine Class
    7. Introducing Elsa
    8. Adding Messaging Capabilities to Your FSM
      1. The Telegram Structure
      2. Miner Bob and Elsa Communicate
      3. Message Dispatch and Management
        1. The MessageDispatcher Class
      4. Message Handling
      5. Elsa Cooks Dinner
        1. Step One
        2. Step Two
        3. Step Three
        4. Step Four
        5. Step Five
    9. Summing Up
  9. Chapter 3 How to Create Autonomously Moving Game Agents
    1. What Is an Autonomous Agent?
    2. The Vehicle Model
      1. Updating the Vehicle Physics
    3. The Steering Behaviors
      1. Seek
      2. Flee
      3. Arrive
      4. Pursuit
      5. Evade
      6. Wander
      7. Obstacle Avoidance
        1. Finding the Closest Intersection Point
        2. Calculating the Steering Force
      8. Wall Avoidance
      9. Interpose
      10. Hide
      11. Path Following
      12. Offset Pursuit
    4. Group Behaviors
      1. Separation
      2. Alignment
      3. Cohesion
      4. Flocking
    5. Combining Steering Behaviors
      1. Weighted Truncated Sum
      2. Weighted Truncated Running Sum with Prioritization
      3. Prioritized Dithering
    6. Ensuring Zero Overlap
    7. Coping with Lots of Vehicles: Spatial Partitioning
    8. Smoothing
  10. Chapter 4 Sports Simulation— Simple Soccer
    1. The Simple Soccer Environment and Rules
      1. The Soccer Pitch
      2. The Goals
      3. The Soccer Ball
        1. SoccerBall::FuturePosition
        2. SoccerBall::TimeToCoverDistance
    2. Designing the AI
      1. The SoccerTeam Class (1/2)
      2. The SoccerTeam Class (2/2)
        1. The Receiving Player
        2. The Closest Player to the Ball
        3. The Controlling Player
        4. The Supporting Player
        5. SoccerTeam States
      3. Field Players (1/3)
      4. Field Players (2/3)
      5. Field Players (3/3)
        1. Field Player Motion
        2. Field Player States
      6. Goalkeepers (1/2)
      7. Goalkeepers (2/2)
        1. Goalkeeper Motion
        2. Goalkeeper States
      8. Key Methods Used by the AI (1/3)
      9. Key Methods Used by the AI (2/3)
      10. Key Methods Used by the AI (3/3)
        1. SoccerTeam::isPassSafeFromAllOpponents
        2. SoccerTeam::CanShoot
        3. SoccerTeam::FindPass
        4. SoccerTeam::GetBestPassToReceiver
    3. Making Estimates and Assumptions Work for You
    4. Summing Up
  11. Chapter 5 The Secret Life of Graphs
    1. Graphs
      1. A More Formal Description
      2. Trees
      3. Graph Density
      4. Digraphs
      5. Graphs in Game AI (1/2)
      6. Graphs in Game AI (2/2)
        1. Navigation Graphs
        2. Dependency Graphs
        3. State Graphs
    2. Implementing a Graph Class
      1. The GraphNode Class
      2. The GraphEdge Class
      3. The SparseGraph Class
    3. Graph Search Algorithms
      1. Uninformed Graph Searches (1/5)
      2. Uninformed Graph Searches (2/5)
      3. Uninformed Graph Searches (3/5)
      4. Uninformed Graph Searches (4/5)
      5. Uninformed Graph Searches (5/5)
        1. Depth First Search
        2. Breadth First Search
      6. Cost-Based Graph Searches (1/4)
      7. Cost-Based Graph Searches (2/4)
      8. Cost-Based Graph Searches (3/4)
      9. Cost-Based Graph Searches (4/4)
        1. Edge Relaxation
        2. Shortest Path Trees
        3. Dijkstra’s Algorithm
        4. Dijkstra with a Twist: A*
    4. Summing Up
  12. Chapter 6 To Script, or Not to Script, That Is the Question
    1. Just What Is a Scripting Language?
    2. What a Scripting Language Can Do for You
      1. Dialogue Flow
      2. Stage Direction
      3. AI Logic
    3. Scripting in Lua
      1. Setting Up Your Compiler to Work with Lua
      2. Getting Started
        1. Lua Variables
        2. Lua Types
        3. Logical Operators
        4. Conditional Structures
      3. Rock-Paper-Scissors in Lua
      4. Interfacing with C/C++ (1/2)
      5. Interfacing with C/C++ (2/2)
        1. Accessing Lua Global Variables from within Your C++ Program
        2. Accessing a Lua Table from within Your C++ Program
        3. Accessing a Lua Function from within C++
        4. Exposing a C/C++ Function to Lua
        5. Exposing a C/C++ Class to Lua
      6. Luabind to the Rescue! (1/2)
      7. Luabind to the Rescue! (2/2)
        1. Setting Up Luabind
        2. Scopes
        3. Exposing C/C++ Functions Using Luabind
        4. Exposing C/C++ Classes Using Luabind
        5. Creating Classes in Lua Using LuaBind
        6. luabind::object
    4. Creating a Scripted Finite State Machine
      1. How It Works
      2. The States
        1. GoHome
        2. Sleep
        3. GoToMine
    5. Useful URLS
    6. It Doesn’t All Smell of Roses
    7. Summing Up
  13. Chapter 7 Raven: An Overview
    1. The Game
    2. Overview of the Game Architecture
      1. The Raven_Game Class
      2. The Raven Map
      3. Raven Weapons
      4. Projectiles
      5. Triggers (1/2)
      6. Triggers (2/2)
        1. TriggerRegion
        2. Trigger
        3. Respawning Triggers
        4. Giver-Triggers
        5. Limited Lifetime Triggers
        6. Sound Notification Triggers
        7. Managing Triggers: The TriggerSystem Class
    3. AI Design Considerations
    4. AI Implementation
      1. Decision Making
      2. Movement
      3. Path Planning
      4. Perception
      5. Target Selection
      6. Weapon Handling
      7. Putting It All Together
      8. Updating the AI Components
    5. Summing Up
  14. Chapter 8 Practical Path Planning
    1. Navigation Graph Construction
      1. Tile Based
      2. Points of Visibility
      3. Expanded Geometry
      4. NavMesh
    2. The Raven Navigation Graph
      1. Coarsely Granulated Graphs
      2. Finely Grained Graphs
      3. Adding Items to the Raven Navigation Graph
      4. Using Spatial Partitioning to Speed Up Proximity Queries
    3. Creating a Path Planner Class
      1. Planning a Path to a Position
      2. Planning a Path to an Item Type
    4. Paths as Nodes or Paths as Edges?
      1. An Annotated Edge Class Example
      2. Modifying the Path Planner Class to Accommodate Annotated Edges
      3. Path Smoothing (1/2)
      4. Path Smoothing (2/2)
        1. Path Smoothing Rough but Quick
        2. Path Smoothing Precise but Slow
      5. Methods for Reducing CPU Overhead (1/3)
      6. Methods for Reducing CPU Overhead (2/3)
      7. Methods for Reducing CPU Overhead (3/3)
        1. Precalculated Paths
        2. Precalculated Costs
        3. Time-Sliced Path Planning
        4. Hierarchical Pathfinding
    5. Getting Out of Sticky Situations
    6. Summing Up
  15. Chapter 9 Goal-Driven Agent Behavior
    1. The Return of Eric the Brave
    2. Implementation
      1. Goal_Composite::ProcessSubgoals
      2. Goal_Composite::RemoveAllSubgoals
    3. Examples of Goals Used by Raven Bots
      1. Goal_Wander
      2. Goal_TraverseEdge
      3. Goal_FollowPath
      4. Goal_MoveToPosition
      5. Goal_AttackTarget
    4. Goal Arbitration
      1. Calculating the Desirability of Locating a Health Item
      2. Calculating the Desirability of Locating a Specific Weapon
      3. Calculating the Desirability of Attacking the Target
      4. Calculating the Desirability of Exploring the Map
      5. Putting It All Together
    5. Spin-offs
      1. Personalities
      2. State Memory
        1. Example One—Automatic Resuming of Interrupted Activities
        2. Example Two—Negotiating Special Path Obstacles
      3. Command Queuing
      4. Using the Queue to Script Behavior
    6. Summing Up
  16. Chapter 10 Fuzzy Logic
    1. Crisp Sets
      1. Set Operators
    2. Fuzzy Sets
      1. Defining Fuzzy Boundaries with Membership Functions
      2. Fuzzy Set Operators
      3. Hedges
    3. Fuzzy Linguistic Variables
    4. Fuzzy Rules
      1. Designing FLVs for Weapon Selection
        1. Designing the Desirability FLV
        2. Designing the Distance to Target FLV
        3. Designing the Ammo Status FLV
      2. Designing the Rule Set for Weapon Selection
      3. Fuzzy Inference (1/2)
      4. Fuzzy Inference (2/2)
        1. Rule One
        2. Rule Two
        3. Rule Three
        4. Defuzzification
    5. From Theory to Application: Coding a Fuzzy Logic Module
      1. The FuzzyModule Class
      2. The FuzzySet Base Class
      3. The Triangular Fuzzy Set Class
      4. The Right Shoulder Fuzzy Set Class
      5. Creating a Fuzzy Linguistic Variable Class
      6. Designing Classes for Building Fuzzy Rules (1/2)
      7. Designing Classes for Building Fuzzy Rules (2/2)
    6. How Raven Uses the Fuzzy Logic Classes
    7. The Combs Method
      1. Fuzzy Inference and the Combs Method
      2. Implementation
    8. Summing Up
  17. Last Words
  18. Appendix A C++ Templates (1/2)
  19. Appendix A C++ Templates (2/2)
  20. Appendix B UML Class Diagrams (1/2)
  21. Appendix B UML Class Diagrams (2/2)
  22. Appendix C Setting Up Your Development Environment
  23. References
  24. Bugs and Errata
  25. Index (1/4)
  26. Index (2/4)
  27. Index (3/4)
  28. Index (4/4)

Product information

  • Title: Programming Game AI by Example
  • Author(s): Mat Buckland
  • Release date: September 2004
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781449613068