Chapter 1. A Math and Physics Primer Page 1 Mathematics. Page 1 Cartesian Coordinates. Page 1 Functions and Equations. Page 3 Exponents and Powers. Page 5 Roots of Numbers (Radicals). Page 6 Simplifying Equations. Page 7 Trigonometry. Page 10 Rays and Line Segments. Page 10 Angles. Page 11 Triangles. Page 12 Vectors. Page 18 Adding and Subtracting Vectors. Page 19 Multiplying Vectors. Page 20 Calculating the Magnitude of a Vector. Page 20 Normalizing Vectors. Page 21 Resolving Vectors. Page 22 The Dot Product. Page 23 A Practical Example of Vector Mathematics. Page 24 The Vector2D Struct. Page 25 Local Space and World Space. Page 26 Physics. Page 28 Time. Page 28 Distance. Page 29 Mass. Page 29 Position. Page 30 Velocity. Page 30 Acceleration. Page 32 Force. Page 38 Summing Up. Page 40 Chapter 2. State-Driven Agent Design Page 43 What Exactly Is a Finite State Machine?. Page 44 Implementing a Finite State Machine. Page 45 State Transition Tables. Page 47 Embedded Rules. Page 48 The West World Project. Page 50 The BaseGameEntity Class. Page 52 The Miner Class. Page 53 The Miner States. Page 54 The State Design Pattern Revisited. Page 55 The EnterMineAndDigForNugget State. Page 60 Making the State Base Class Reusable. Page 62 Global States and State Blips. Page 63 Creating a State Machine Class. Page 64 Introducing Elsa. Page 67 Adding Messaging Capabilities to Your FSM. Page 69 The Telegram Structure. Page 70 Miner Bob and Elsa Communicate. Page 71 Message Dispatch and Management. Page 71 The MessageDispatcher Class. Page 73 Message Handling. Page 75 Elsa Cooks Dinner. Page 78 Step One. Page 78 Step Two. Page 79 Step Three. Page 80 Step Four. Page 80 Step Five. Page 81 Summing Up. Page 82 Chapter 3. How to Create Autonomously Moving Game Agents Page 85 What Is an Autonomous Agent?. Page 85 The Vehicle Model. Page 87 Updating the Vehicle Physics. Page 89 The Steering Behaviors. Page 91 Seek. Page 91 Flee. Page 92 Arrive. Page 93 Pursuit. Page 94 Evade. Page 96 Wander. Page 96 Obstacle Avoidance. Page 99 Finding the Closest Intersection Point. Page 100 Calculating the Steering Force. Page 103 Wall Avoidance. Page 104 Interpose. Page 106 Hide. Page 107 Path Following. Page 110 Offset Pursuit. Page 111 Group Behaviors. Page 113 Separation. Page 115 Alignment. Page 116 Cohesion. Page 117 Flocking. Page 118 Combining Steering Behaviors. Page 119 Weighted Truncated Sum. Page 120 Weighted Truncated Running Sum with Prioritization. Page 121 Prioritized Dithering. Page 123 Ensuring Zero Overlap. Page 124 Coping with Lots of Vehicles: Spatial Partitioning. Page 126 Smoothing. Page 130 Chapter 4. Sports Simulation — Simple Soccer Page 133 The Simple Soccer Environment and Rules. Page 134 The Soccer Pitch. Page 135 The Goals. Page 138 The Soccer Ball. Page 138 SoccerBall::FuturePosition. Page 141 SoccerBall::TimeToCoverDistance. Page 142 Designing the AI. Page 144 The SoccerTeam Class. Page 145 The Receiving Player. Page 146 The Closest Player to the Ball. Page 146 The Controlling Player. Page 146 The Supporting Player. Page 146 SoccerTeam States. Page 152 Field Players. Page 155 Field Player Motion. Page 155 Field Player States. Page 156 Goalkeepers. Page 170 Goalkeeper Motion. Page 170 Goalkeeper States. Page 171 Key Methods Used by the AI. Page 176 SoccerTeam::isPassSafeFromAllOpponents. Page 177 SoccerTeam::CanShoot. Page 182 SoccerTeam::FindPass. Page 184 SoccerTeam::GetBestPassToReceiver. Page 185 Making Estimates and Assumptions Work for You. Page 189 Summing Up. Page 189 Chapter 5. The Secret Life of Graphs Page 193 Graphs. Page 193 A More Formal Description. Page 195 Trees. Page 196 Graph Density. Page 196 Digraphs. Page 196 Graphs in Game AI. Page 197 Navigation Graphs. Page 198 Dependency Graphs. Page 199 State Graphs. Page 201 Implementing a Graph Class. Page 203 The GraphNode Class. Page 204 The GraphEdge Class. Page 205 The SparseGraph Class. Page 207 Graph Search Algorithms. Page 209 Uninformed Graph Searches. Page 210 Depth First Search. Page 210 Breadth First Search. Page 224 Cost-Based Graph Searches. Page 231 Edge Relaxation. Page 231 Shortest Path Trees. Page 233 Dijkstra’s Algorithm. Page 233 Dijkstra with a Twist: A*. Page 241 Summing Up. Page 247 Chapter 6. To Script, or Not to Script, That Is the Question Page 249 Just What Is a Scripting Language?. Page 249 What a Scripting Language Can Do for You. Page 251 Dialogue Flow. Page 253 Stage Direction. Page 254 AI Logic. Page 255 Scripting in Lua. Page 255 Setting Up Your Compiler to Work with Lua. Page 256 Getting Started. Page 256 Lua Variables. Page 258 Lua Types. Page 260 Logical Operators. Page 263 Conditional Structures. Page 264 Rock-Paper-Scissors in Lua. Page 265 Interfacing with C/C++. Page 268 Accessing Lua Global Variables from within Your C++ Program. Page 269 Accessing a Lua Table from within Your C++ Program. Page 271 Accessing a Lua Function from within C++. Page 273 Exposing a C/C++ Function to Lua. Page 274 Exposing a C/C++ Class to Lua. Page 276 Luabind to the Rescue!. Page 276 Setting Up Luabind. Page 276 Scopes. Page 277 Exposing C/C++ Functions Using Luabind. Page 278 Exposing C/C++ Classes Using Luabind. Page 279 Creating Classes in Lua Using LuaBind. Page 281 luabind::object. Page 282 Creating a Scripted Finite State Machine. Page 285 How It Works. Page 285 The States. Page 289 GoHome. Page 290 Sleep. Page 290 GoToMine. Page 291 Useful URLS. Page 292 It Doesn’t All Smell of Roses. Page 292 Summing Up. Page 293 Chapter 7. Raven: An Overview Page 295 The Game. Page 295 Overview of the Game Architecture. Page 296 The Raven_Game Class. Page 297 The Raven Map. Page 299 Raven Weapons. Page 301 Projectiles. Page 302 Triggers. Page 303 TriggerRegion. Page 304 Trigger. Page 305 Respawning Triggers. Page 307 Giver-Triggers. Page 308 Limited Lifetime Triggers. Page 309 Sound Notification Triggers. Page 310 Managing Triggers: The TriggerSystem Class. Page 311 AI Design Considerations. Page 313 AI Implementation. Page 315 Decision Making. Page 315 Movement. Page 315 Path Planning. Page 315 Perception. Page 316 Target Selection. Page 321 Weapon Handling. Page 323 Putting It All Together. Page 327 Updating the AI Components. Page 328 Summing Up. Page 331 Chapter 8. Practical Path Planning Page 333 Navigation Graph Construction. Page 333 Tile Based. Page 333 Points of Visibility. Page 334 Expanded Geometry. Page 335 NavMesh. Page 335 The Raven Navigation Graph. Page 336 Coarsely Granulated Graphs. Page 336 Finely Grained Graphs. Page 339 Adding Items to the Raven Navigation Graph. Page 341 Using Spatial Partitioning to Speed Up Proximity Queries. Page 342 Creating a Path Planner Class. Page 342 Planning a Path to a Position. Page 344 Planning a Path to an Item Type. Page 346 Paths as Nodes or Paths as Edges?. Page 348 An Annotated Edge Class Example. Page 350 Modifying the Path Planner Class to Accommodate Annotated Edges. Page 350 Path Smoothing. Page 353 Path Smoothing Rough but Quick. Page 354 Path Smoothing Precise but Slow. Page 358 Methods for Reducing CPU Overhead. Page 359 Precalculated Paths. Page 359 Precalculated Costs. Page 361 Time-Sliced Path Planning. Page 363 Hierarchical Pathfinding. Page 372 Getting Out of Sticky Situations. Page 374 Summing Up. Page 376 Chapter 9. Goal-Driven Agent Behavior Page 379 The Return of Eric the Brave. Page 380 Implementation. Page 382 Goal_Composite::ProcessSubgoals. Page 385 Goal_Composite::RemoveAllSubgoals. Page 386 Examples of Goals Used by Raven Bots. Page 387 Goal_Wander. Page 387 Goal_TraverseEdge. Page 388 Goal_FollowPath. Page 391 Goal_MoveToPosition. Page 393 Goal_AttackTarget. Page 395 Goal Arbitration. Page 398 Calculating the Desirability of Locating a Health Item. Page 400 Calculating the Desirability of Locating a Specific Weapon. Page 401 Calculating the Desirability of Attacking the Target. Page 403 Calculating the Desirability of Exploring the Map. Page 403 Putting It All Together. Page 404 Spin-offs. Page 405 Personalities. Page 405 State Memory. Page 406 Example One — Automatic Resuming of Interrupted Activities. Page 407 Example Two — Negotiating Special Path Obstacles. Page 408 Command Queuing. Page 410 Using the Queue to Script Behavior. Page 412 Summing Up. Page 414 Chapter 10. Fuzzy Logic Page 415 Crisp Sets. Page 417 Set Operators. Page 418 Fuzzy Sets. Page 419 Defining Fuzzy Boundaries with Membership Functions. Page 419 Fuzzy Set Operators. Page 421 Hedges. Page 423 Fuzzy Linguistic Variables. Page 423 Fuzzy Rules. Page 424 Designing FLVs for Weapon Selection. Page 425 Designing the Desirability FLV. Page 426 Designing the Distance to Target FLV. Page 427 Designing the Ammo Status FLV. Page 428 Designing the Rule Set for Weapon Selection. Page 428 Fuzzy Inference. Page 429 Rule One. Page 429 Rule Two. Page 430 Rule Three. Page 430 Defuzzification. Page 433 From Theory to Application: Coding a Fuzzy Logic Module. Page 437 The FuzzyModule Class. Page 437 The FuzzySet Base Class. Page 439 The Triangular Fuzzy Set Class. Page 440 The Right Shoulder Fuzzy Set Class. Page 441 Creating a Fuzzy Linguistic Variable Class. Page 443 Designing Classes for Building Fuzzy Rules. Page 445 How Raven Uses the Fuzzy Logic Classes. Page 451 The Combs Method. Page 452 Fuzzy Inference and the Combs Method. Page 454 Implementation. Page 455 Summing Up. Page 455 Last Words. Page 457 Appendix A. C++ Templates Page 459 Appendix B. UML Class Diagrams Page 465 Appendix C. Setting Up Your Development Environment Page 475 References. Page 477 Bugs and Errata. Page 479 Index. Page 481