Recent advances in 3D visualization and physics-based simulation technology, at both the software and hardware levels, have enabled game developers to create compelling, visually immersive gaming environments. The next step in creating even more immersive games is improved artificial intelligence (AI). Advances in computing power, and in hardware-accelerated graphics in particular, are helping to free up more CPU cycles that can be devoted to more sophisticated AI engines for games. Further, the large number of resources—academic papers, books, game industry articles, and web sites—devoted to AI are helping to put advanced AI techniques within the grasp of every game developer, not just those professionals who devote their careers to AI.
With that said, wading through volumes of technical papers, text books, and web sites can be a daunting task for upcoming game AI developers. This book pulls together the information novices need so that they can get a jump-start in the field of game AI development. We present relevant theory on a wide range of topics, which we support with code samples throughout the book.
Many general game development books cover AI to some extent, however their treatment of the technology tends to be limited. This is probably because such books have to cover a lot of different topics and cannot go into great depth on any particular one. Although several very good books do focus on game AI (we list many of them in the “Additional Resources” section of this Preface), most of them are geared toward experienced AI developers and they focus on relatively specific and advanced topics. Therefore, novices likely would require companion resources that cover some of the more fundamental aspects of game AI in more detail. Still other books cover some specific game AI techniques in great detail, but are restricted to covering just those techniques.
Our book covers a wide range of game AI topics at a level appropriate for novice developers. So, if you are new to game programming or if you are an experienced game programmer who needs to get up to speed quickly on AI techniques such as finite state machines, fuzzy logic, and neural networks, among others, this book is for you.
Because this book is targeted for beginner game AI developers, we don’t assume you have any AI background. We do, however, assume you know how to program using C/C++. We also assume you have a working knowledge of the basic vector math used in games, but we have included a brief vector math refresher in the Appendix in case your skills are a little rusty.
We didn’t hope to (nor did we attempt to) cover every aspect of game AI in this book; far too many techniques and variations of techniques are used for an even larger variety of game types, specific game architectures, and in-game scenarios. Instead, we present a mix of both deterministic (traditional) and nondeterministic (newer) AI techniques aimed squarely at beginner AI developers. Here’s a summary of what we cover:
Here, we define game AI and discuss the current state of the art as well as the future of this technology.
We cover basic techniques for chasing and evading as well as more advanced techniques for intercepting. We also cover techniques applicable to both tile-based and continuous game environments.
Pattern movement techniques are common to many video games and developers have been using them since the early days of gaming. You can use these techniques to preprogram certain behaviors such as the patrolling of a guard or the swooping in of a spacecraft.
The flocking method we examine in this chapter is an example of an A-life algorithm. In addition to creating cool-looking flocking behavior, A-life algorithms form the basis of more advanced group movement.
Potential-based movement is relatively new in game AI applications. The cool thing about this method is that it can handle chasing, evading, swarming, and collision avoidance simultaneously.
Game developers use many techniques to find paths in and around game environments. In this chapter, we cover several of these methods, including waypoints.
No treatment of pathfinding is complete without addressing the workhorse algorithm of pathfinding; therefore, we devote this whole chapter to the A∗ algorithm.
Programmers today often write scripting engines and hand off the tools to level designers who are responsible for creating the content and defining the AI. In this chapter, we explore some of the techniques developers use to apply a scripting system in their games, and the benefits they receive.
Finite state machines are the nuts and bolts of game AI. This chapter discusses the fundamentals of finite state machines and how to implement them.
Developers use fuzzy logic in conjunction with or as a replacement for finite state machines. In this chapter, you’ll learn the advantages fuzzy techniques offer over traditional logic techniques.
Technically, fuzzy logic and finite state machines fall under the general heading of rules-based methods. In this chapter, we cover these methods as well as other variants.
Game developers commonly use basic probability to make their games less predictable. Such cheap unpredictability enables developers to maintain substantial control over their games. Here, we cover basic probability for this purpose as well as lay the groundwork for more advanced methods.
Bayesian techniques are probabilistic techniques, and in this chapter we show how you can use them for decision making and for adaptation in games.
Game developers use neural networks for learning and adaptation in games—in fact, for anything from making decisions to predicting the behavior of players. We cover the most widely used neural network architecture, in detail.
Genetic algorithms offer opportunities for evolving game AI. Although developers don’t often use genetic algorithms in games, their potential for specific applications is promising, particularly if they are combined with other methods.
This appendix shows you how to implement a C++ class that captures all of the vector operations that you’ll need when writing 2D or 3D simulations.
All the chapters in this book are fairly independent of each other. Therefore, you generally can read the chapters in any order you want, without worrying about missing material in earlier chapters. The only exception to this rule is Chapter 12, on basic probability. If you don’t have a background in probability, you should read this chapter before reading Chapter 13, on Bayesian methods.
Also, we encourage you to try these algorithms for yourself in your own programs. If you’re just getting started in game AI, which we assume you are if you’re reading this book, you might want to begin by applying some of the techniques we present in simple arcade-style or board games. You also might consider programming a bot using extensible AI tools that are increasingly becoming standard for first-person shooter games. This approach will give you the opportunity to try out your AI ideas without having to program all the other non-AI aspects of your game.
The following typographical conventions are used in this book:
Indicates menu titles, menu options, menu buttons, and keyboard accelerators (such as Alt and Ctrl).
Indicates new terms, URLs, email addresses, filenames, file extensions, pathnames, directories, and Unix utilities.
Indicates commands, options, switches, variables, attributes, keys, functions, types, classes, namespaces, methods, modules, properties, parameters, values, objects, events, event handlers, XML tags, HTML tags, macros, the contents of files, or the output from commands.
Constant width bold
Shows commands or other text that should be typed literally by the user.
Constant width italic
Shows text that should be replaced with user-supplied values.
Variables shown in bold are vectors as opposed to scalar variables, which are shown in regular print.
Although we attempt to cover a wide range of AI techniques in this book, we realize we can’t compress within these pages everything there is to know about AI in game development. Therefore, we’ve compiled a short list of useful AI web and print resources for you to explore should you decide to pursue game AI further.
Here are some popular web sites related to game development and AI that we find helpful:
The Game AI Page at http://www.gameai.com
AI Guru at http://www.aiguru.com
Gamasutra at http://www.gamasutra.com
GameDev.net at http://www.gamedev.net
AI Depot at http://ai-depot.com
Generation5 at http://www.generation5.org
The American Association for Artificial Intelligence at http://www.aaai.org
Each web site contains information relevant to game AI as well as additional links to other sources of information on AI.
Here are several print resources that we find helpful (note that these resources include both game and nongame AI books):
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference by Judea Pearl (Morgan Kaufmann Publishers, Inc.)
Bayesian Artificial Intelligence by Kevin Korb and Ann Nicholson (Chapman & Hall/CRC)
Bayesian Inference and Decision, Second Edition by Robert Winkler (Probabilistic Publishing)
AI Game Programming Wisdom by Steve Rabin, ed. (Charles River Media)
AI Techniques for Game Programming by Mat Buckland (Premier Press)
Practical Neural Network Recipes in C++ by Timothy Masters (Academic Press)
Neural Networks for Pattern Recognition by Christopher Bishop (Oxford University Press)
AI Application Programming by M. Tim Jones (Charles River Media)
This book is designed to help you get your job done. In general, you can use the code in this book in your programs and documentation. You do not need to contact us for permission unless you’re reproducing a significant portion of the code. For example, writing a program that uses several chunks of code from this book does not require permission. Selling or distributing a CD-ROM of examples from O’Reilly books does require permission. Answering a question by citing this book and quoting example code does not require permission. Incorporating a significant amount of example code from this book into your product’s documentation does require permission.
We appreciate, but do not require, attribution. An attribution usually includes the title, author, publisher, and ISBN. For example: “AI for Game Developers, by David M. Bourg and Glenn Seemann. Copyright 2004 O’Reilly Media, Inc., 0-596-00555-5.”
If you feel your use of code examples falls outside fair use or the permission given here, feel free to contact us at email@example.com.
Please address comments and questions concerning this book to the publisher:
|O’Reilly Media, Inc.|
|1005 Gravenstein Highway North|
|Sebastopol, CA, 95472|
|(800) 998-9938 (in the United States or Canada)|
|(707) 829-0515 (international or local)|
|(707) 829-0104 (fax)|
We have a web page for this book, where we list errata, examples, and any additional information. You can access this page at:
To comment or ask technical questions about this book, send email to:
For more information about our books, conferences, Resource Centers, and the O’Reilly Network, see our web site at:
We’d like to thank our editors, Nathan Torkington and Tatiana Diaz, for their skill, insight, and patience. We’d also like to express our appreciation to O’Reilly for giving us the opportunity to write this book. Further, special thanks go to all the production and technical staff at O’Reilly, and to the technical reviewers, chromatic, Graham Evans, and Mike Keith, for their thoughtful and expert comments and suggestions. Finally, we’d like to thank our respective wives, Helena and Michelle, for their support and encouragement and for putting up with our repeatedly saying, “I have to work on the book this weekend.” We can’t forget to thank our respective children, who always remind us that it’s OK to play. On that note, remember that the most important goal of good AI in games is to make games more fun. Play on!