Artificial Intelligence for Games, Second Edition

1 ARTIFICIALINTELLIGENCEFOR GAMESS econd EditionIAN MILLINGTONandJOHN FUNGEAMSTERDAM BOSTON HEIDELBERG LONDONNEW YORK OXFORD PARIS SAN DIEGOSAN FRANCISCO SINGAPORE SYDNEY TOKYOM organ Kaufmann Publishers is an imprint of ElsevierMorgan Kaufmann Publishers is an imprint of Corporate Drive, Suite 400, Burlington, MA 01803, USAThis book is printed on acid-free 2009 by Elsevier Inc. All rights used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In allinstances in which Morgan Kaufmann Publishers is aware of a claim, the product names appear in initial capital or all capitalletters. All trademarks that appear or are otherwise referred to in this work belong to their respective owners. Neither MorganKaufmann Publishers nor the authors and other contributors of this work have any relationship or affiliation with suchtrademark owners nor do such trademark owners confirm, endorse or approve the contents of this work.

2 Readers, however,should contact the appropriate companies for more information regarding trademarks and any related part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by anymeans electronic, mechanical, photocopying, scanning, or otherwise without prior written permission of the may be sought directly from Elsevier s Science & Technology Rights Department in Oxford, UK: phone: (+44) 1865843830, fax: (+44) 1865 853333, E-mail: You may also complete your request online via the Elsevierhomepage ( ), by selecting Support & Contact then Copyright and Permission and then ObtainingPermissions. Library of Congress Cataloging-in-Publication DataMillington, Intelligence for games / Ian Millington, John Funge. 2nd 978-0-12-374731-0 (hardcover : alk. paper)1. Computer games Programming. 2. Computer animation. 3. Artificial Funge, John David, 1968- II. dc222009016733 British Library Cataloguing-in-Publication DataA catalogue record for this book is available from the British : 978-0-12-374731-0 For information on all Morgan Kaufmann publicationsvisit our Website by: diacriTech, IndiaPrinted in the United States of America0910111213 54321 For Conor Xiaoyuan the AuthorsIan Millingtonis a partner of Icosagon Ltd.

3 ( ), a consulting company devel-oping next-generation AI technologies for entertainment, modeling, and simulation. Previouslyhe founded Mindlathe Ltd., the largest specialist AI middleware company in computer Games, working on a huge range of game genres and technologies. He has a long background in AI,including PhD research in complexity theory and natural computing. He has published academicand professional papers and articles on topics ranging from paleontology to Funge( ) recently joined Netflix to start and lead the new Game Platformsgroup. Previously,John co-founded AiLive and spent nearly ten years helping to create a successfulcompany that is now well known for its pioneering machine learning technology for games. AiLiveco-created theWii MotionPlus hardware and has established its LiveMove products as the industrystandard for automatic motion recognition. At AiLive John also worked extensively on LiveAI, areal-time behavior capture product that is being used by the former lead game designer of GuitarHero and Rock Band to create a new genre of game.

4 John is also an Assistant Adjunct Professorat the University of California, Santa Cruz (UCSC) where he teaches a Game AI course that heproposed, designed and developed. John has a PhD from the University of Toronto and an MScfrom the University of Oxford. He holds several patents, is the author of numerous technicalpapers, and wrote two previous books on Game the AuthorsivAcknowledgmentsxixPrefacexxiAbo ut the WebsitexxiiiPart IAI and Is AI? Academic Game of Game Decision Agent-Based In the , Data Structures, the of the Book18 Chapter2 Game Complexity When Simple Things Look When Complex Things Look The Perception Changes of Kind of AI in and Processor Memory PC Console AI Structure of an AI Toolchain Putting It All Together34 Part Basics of Movement Two-Dimensional Movement On the Steering Variable Seek and Velocity Delegated Pursue and Looking Where You re Path Collision Obstacle and Wall Steering Blending and Weighted Cooperative Steering Aiming and Projectile The Firing Projectiles with Iterative Jump Landing Hole Fixed Scalable Emergent Two-Level Formation Extending to More than Two Slot Roles and Better Slot Dynamic Slots and Tactical Output Capability-Sensitive Common Actuation in the Third Rotation in Three

5 Converting Steering Behaviors to Three Align to Look Where You re Faking Rotation Pathfinding Weighted Directed Weighted The The Data Structures and Performance of * The The Data Structures and Implementation Algorithm Node Array A* Choosing a Tile Dirichlet Points of Navigation Non-Translational Cost Path on A* The Hierarchical Pathfinding Pathfinding on the Hierarchical Hierarchical Pathfinding on Strange Effects of Hierarchies on Instanced Ideas in Open Goal Dynamic Other Kinds of Information Low Memory Interruptible Pooling Time The The Implementation Movement Footfalls287 Exercises288xContentsChapter5 Decision of Decision The The On the Knowledge Implementation Performance of Decision Balancing the Beyond the Random Decision The The Data Structures and On the Implementation Hard-Coded Hierarchical State Combining Decision Trees and State Implementing Behavior Concurrency and Adding Data to Behavior Reusing Limitations of Behavior A Introduction to fuzzy fuzzy logic Decision fuzzy State Markov Markov State Goal-Oriented Simple Overall Overall Utility GOAP with IDA* Smelly The The Data Structures and Implementation Rule Where The The Data Structures and Other Things Are Blackboard Language Choosing a A Language Rolling Your Scripting Languages and Other Types of The Data Structures and Implementation Putting It All Together490 Chapter6 Tactical and Strategic Tactical Using Tactical Generating the Tactical Properties of a Automatically Generating the

6 The Condensation Representing the Game Simple Influence Terrain Learning with Tactical A Structure for Tactical Map Convolution Cellular The Cost Tactic Weights and Concern Modifying the Pathfinding Tactical Graphs for Using Tactical Multi-Tier Emergent Scripting Group Military Online or Offline Intra-Behavior Inter-Behavior A The Zoo of Learning The Balance of The Parameter Hill Extensions to Basic Hill Left or Raw String Window Application in Structure of Decision What Should You Learn? Four Bayes Implementation Tree ID3 with Continuous Incremental Decision Tree The The Data Structures and Implementation Tailoring Weaknesses and Realistic Other Ideas in Reinforcement Neural The The Data Structures and Implementation Other Approaches658 Exercises662 Chapter8 Board Types of The Game The Static Evaluation The Minimaxing AB The AB Search Tables and Hashing Game What to Store in the Hash Table Replacement A Complete Transposition Transposition Table Using Opponent s Thinking Test Implementing The MTD Books and Other Set Implementing an Opening Learning for Opening Set Play Iterative Variable Depth Strategy Impossible Tree Real-Time AI in a Turn-Based Game708 Exercises708 Part IIIS upporting Technologies711 Chapter9 Execution The Interruptible

7 Load-Balancing Hierarchical Priority of Graphics Level of AI Scheduling Behavioral Group In Summary743 Exercises744 Chapter10 World Knowledge Determining What Approach to Event Inter-Agent Implementation Abstract Faking What Do We Know? Sensory Region Sense Finite Element Model Sense Manager775 Exercises783 Chapter11 Tools and Content Toolchains Limit Where AI Knowledge Comes for Pathfinding and Waypoint Manually Creating Region Automatic Graph Geometric Data for High-Level for Decision Object Concrete Data-Driven AI Design Remote Plug-Ins802 Exercises802 ContentsxviiPart IVDesigning Game AI805 Chapter12 Designing Game Evaluating the Selecting The Scope of One Movement and Decision Pathfinding and Tactical Shooter-Like Pathfinding and Tactical Driving-Like Group Tactical and Strategic Decision Physics Playbooks and Content Strategy Helping the Player830 Chapter13AI-Based Game Representing Representing the Learning Predictable Mental Models and Pathological and Herding Making the Tuning Steering for Steering Behavior Ecosystem , Periodicals.

8 And our names are on the cover, this book contains relatively little that originated with us,but on the other hand it contains relatively few references. When the first Edition of this book waswritten Game AI wasn t as hot as it is today: it had no textbooks, no canonical body of papers,and few well-established citations for the origins of its AI is a field where techniques, gotchas, traps, and inspirations are shared more oftenon the job than in landmark papers. We have drawn the knowledge in this book from a wholeweb of developers, stretching out from here to all corners of the gaming world. Although theyundoubtedly deserve it, we re at a loss how better to acknowledge the contribution of theseunacknowledged are people with whom we have worked closely who have had a more direct influenceon our AI journey. For Ian that includes his PhD supervisor Prof. Aaron Sloman and the team ofcore AI programmers he worked with at Mindlathe: Marcin Chady, who is credited several timesfor inventions in this book; Stuart Reynolds; Will Stones; and Ed Davis.

9 For John the list includeshis colleagues and former colleagues at AiLive: Brian Cabral, Wolff (Daniel) Dobson, Nigel Duffy,Rob Kay, Yoichiro Kawano, Andy Kempling, Michael McNally, Ron Musick, Rob Powers, StuartReynolds (again), Xiaoyuan Tu, Dana Wilkinson, Ian Wright, and Wei a book is a mammoth task that includes writing text,producing code,creating illustra-tions, acting on reviews, and checking proofs. We would therefore especially like to acknowledgethe hard work and incisive comments of the review team: Toby Allen, Jessica D. Bayliss, MarcinChady (again), David Eberly, John Laird, and Brian Peltonen. We have missed one name from thelist: the late, and sorely missed, Eric Dybsand, who also worked on the reviewing of this book, andwe re proud to acknowledge that the benefit we gained from his comments are yet another partof his extensive legacy to the are particularly grateful for the patience of the editorial team led by Tim Cox at MorganKauffman, aided and abetted by Paul Gottehrer and Jessie Evans, with additional wisdom andseries guidance from Dave nights and long days aren t a hardship when you love what you do.

10 So without doubt thepeople who have suffered the worst of the writing process are our families. Ian thanks his wifeMel for the encouragement to start this and the support to see it through. John also thanks hiswife Xiaoyuan and dedicates his portion of the book to her for all her kind and loving supportover the would like to dedicate the book to his late friend and colleague Conor Brennan. For twoyears during the writing of the first Edition he d constantly ask if it was out yet, and whether hecould get a copy. Despite Conor s lack of all technical knowledge Ian continually promised himone on the book s publication. Conor sadly died just a few weeks before the first Edition went enjoyed having his name in print. He would proudly show off a mention in PeteSlosberg s bookBeer for Pete s Sake. It would have appealed to his wry sense of humor to receivethe dedication of a book whose contents would have baffled to the Second editionOne of the things about the first Edition of this book that regularly gets very good feedback isthe idea that the book contains a palette of lots of different approaches.