collEctEd wisdom Successful games merge art and technology in truly unique ways. Fused under tight of gamE ai production deadlines and strict performance requirements, shaped by demanding player expectations, games are among the most complex software projects created today. Game profEssionals AI Pro: Collected Wisdom of Game AI Professionals covers both the art and the technology of game AI. Nothing covered is theory or guesswork. The book brings together the accumulated wisdom, cutting-edge ideas, and clever tricks and techniques of 54 of today’s top game AI professionals. Some chapters present techniques that have been developed and passed down within the community for years while others discuss the most exciting new research and ideas from today’s most innovative games. The book includes core algorithms that you’ll need to succeed, such as behavior trees, utility theory, spatial representation, path planning, motion control, and tactical reasoning. It also describes tricks and techniques that will truly bring your game to life, including perception systems, social modeling, smart camera systems, player prediction, and even an AI sound designer. Throughout, the book discusses the optimizations and performance enhancements that enable your game to run while maintaining 60 frames per second. Features • Contains 48 articles from 54 of the game industry’s top developers • Presents many practical, cutting-edge techniques drawn from successful games • Includes both the core algorithms that are widely used in the industry today as well as new ideas and research that are being shared for the first time • Provides example programs and source code at www.gameaipro.com EditEd by K16125 stEvE rabin Computer Game Development ColleCted Wisdom of Game ai Professionals CollECtEd WiSdom of GamE ai PRofESSionalS EditEd by StEvEn Rabin Boca Raton London New York CRC Press is an imprint of the Taylor & Francis Group, an informa business AN A K PETERS BOOK CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2014 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 20140311 International Standard Book Number-13: 978-1-4665-6597-5 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com Contents Preface xi Web Materials xiii Acknowledgments xv The Editors xvii The Contributors xix Part I General Wisdom 1 What Is Game AI? 3 Kevin Dill 2 Informing Game AI through the Study of Neurology 11 Brett Laming 3 Advanced Randomness Techniques for Game AI: Gaussian Randomness, Filtered Randomness, and Perlin Noise 29 Steve Rabin, Jay Goldblatt, and Fernando Silva v Part II Architecture 4 Behavior Selection Algorithms: An Overview 47 Michael Dawe, Steve Gargolinski, Luke Dicken, Troy Humphreys, and Dave Mark 5 Structural Architecture—Common Tricks of the Trade 61 Kevin Dill 6 The Behavior Tree Starter Kit 73 Alex J. Champandard and Philip Dunstan 7 Real-World Behavior Trees in Script 93 Michael Dawe 8 Simulating Behavior Trees: A Behavior Tree/Planner Hybrid Approach 99 Daniel Hilburn 9 An Introduction to Utility Theory 113 David “Rez” Graham 10 Building Utility Decisions into Your Existing Behavior Tree 127 Bill Merrill 11 Reactivity and Deliberation in Decision-Making Systems 137 Carle Côté 12 Exploring HTN Planners through Example 149 Troy Humphreys 13 Hierarchical Plan-Space Planning for Multi-unit Combat Maneuvers 169 William van der Sterren 14 Phenomenal AI Level-of-Detail Control with the LOD Trader 185 Ben Sunshine-Hill 15 Runtime Compiled C++ for Rapid AI Development 201 Doug Binks, Matthew Jack, and Will Wilson 16 Plumbing the Forbidden Depths: Scripting and AI 219 Mike Lewis vi Contents Part III Movement and Pathfinding 17 Pathfinding Architecture Optimizations 241 Steve Rabin and Nathan R. Sturtevant 18 Choosing a Search Space Representation 253 Nathan R. Sturtevant 19 Creating High-Order Navigation Meshes through Iterative Wavefront Edge Expansions 259 D. Hunter Hale and G. Michael Youngblood 20 Precomputed Pathfinding for Large and Detailed Worlds on MMO Servers 269 Fabien Gravot, Takanori Yokoyama, and Youichiro Miyake 21 Techniques for Formation Movement Using Steering Circles 289 Stephen Bjore 22 Collision Avoidance for Preplanned Locomotion 297 Bobby Anguelov 23 Crowd Pathfinding and Steering Using Flow Field Tiles 307 Elijah Emerson 24 Efficient Crowd Simulation for Mobile Games 317 Graham Pentheny 25 Animation-Driven Locomotion with Locomotion Planning 325 Jarosław Ciupiński Part IV Strategy and Tactics 26 Tactical Position Selection: An Architecture and Query Language 337 Matthew Jack 27 Tactical Pathfinding on a NavMesh 361 Daniel Brewer Contents vii 28 Beyond the Kung-Fu Circle: A Flexible System for Managing NPC Attacks 369 Michael Dawe 29 Hierarchical AI for Multiplayer Bots in Killzone 3 377 Remco Straatman, Tim Verweij, Alex Champandard, Robert Morcus, and Hylke Kleve 30 Using Neural Networks to Control Agent Threat Response 391 Michael Robbins Part V Agent Awareness and Knowledge Representation 31 Crytek’s Target Tracks Perception System 403 Rich Welsh 32 How to Catch a Ninja: NPC Awareness in a 2D Stealth Platformer 413 Brook Miles 33 Asking the Environment Smart Questions 423 Mieszko Zielinski 34 A Simple and Robust Knowledge Representation System 433 Phil Carlisle 35 A Simple and Practical Social Dynamics System 441 Phil Carlisle 36 Breathing Life into Your Background Characters 451 David “Rez” Graham 37 Alibi Generation: Fooling All the Players All the Time 459 Ben Sunshine-Hill Part VI Racing 38 An Architecture Overview for AI in Racing Games 471 Simon Tomlinson and Nic Melder 39 Representing and Driving a Race Track for AI Controlled Vehicles 481 Simon Tomlinson and Nic Melder viii Contents