|
|
AI Game Programming Wisdom
71 Articles, Edited by Steve Rabin, 2002.
|
Survey of Lowest Known Online Prices
$48.97 (30% off) Amazon.com (free shipping)
$55.96 (20% off) BarnesAndNoble.com
Section 1: General Wisdom
 |
Abstract: This article provides a big-picture summary of game AI: what it is, where it's going, where it's been, how it can grow, and what makes it so different from any other discipline. We give a broad overview of the evolution of AI in games since the birth of the videogame, as well as the evolution of a game AI within the scope of a game's development. We also describe many of the academic AI techniques that have been applied to games, explain the important distinctions between the needs and approaches mainstream AI and game AIs of various genres, and discuss some of the ways that game AI technologies are likely to grow in the future.
The Illusion of Intelligence |
Solving the Right Problem |
Abstract: This article will talk about going back to first principles: What is the problem we are trying to solve? Why is that important - what are we really trying to do? Too early programmers settle on an answer to the first when they should more carefully examine the second. A clear example comes from the AI Roundtables at the GDC. At first the company fixated on trying to do speech input. In a world where the NPCs talk, they should be able to listen as well. This left them with the huge mountain of work to do speech recognition, and even if they could climb that mountain, the bigger mountain of natural language processing was waiting hidden behind it. After all, even if Dragon Dictate parses everything you say as well as your officemate does, it surely does not have the ability to make sense of it and respond intelligently. Instead of trying to climb these two large mountains of work, the company stepped back to the question of why it is important. It was important to give a more immersive and natural experience. So instead of doing speech, they implemented gestures. Large motion gestures are universally understood. The shrug that means "I don't know" means "I don't know" to just about everybody. They got a much better result by solving a different problem! While this article won't give people the easier problem to solve, it should help get them thinking about the process. It will also give a number of things other designers do to inspire them to "think outside the box."
12 Tips from the Trenches |
Abstract: This article is intended to give developers who are new to Game AI a head start. It gives an overview of many techniques professional Game AI developers have found useful, that may not be immediately obvious to a novice. Topics covered include precomputing navigation, building a world with AI hints, providing fallbacks, finite-state machine organization, and data-driven approaches. Many tips reference other articles in AI Game Programming Wisdom for more detail.
Section 2: Useful Techniques and Specialized Systems
Building an AI Diagnostic Toolset |
Abstract: This article describes invaluable techniques that real developers use to tweak, test, and diagnose their AI during the development cycle. We describe literally dozens of specific ways you can instrument your AI to help you tweak and test it more quickly and figure out what's wrong when your AI breaks.
A General Purpose Trigger System |
Abstract: This article describes the implementation of a general-purpose centralized Trigger System. A Trigger System is used to keep track of events in the game world, and to optimize processing agents need to perform to recognize these events. Centralizing the Trigger System allows for culling by priority and proximity before delivering Trigger events to agents. The article and companion CD include working code for a stimulus-response Trigger System. Enhancements are discussed to extend the system to handle processing a grouping hierarchy of agents, in addition to individual agents.
A Data-Driven Architecture for Animation Selection |
Abstract: Animation selection is a common task for AI systems. Due to advances in animation technology, it is now common to provide a much wider range of animations for characters, including specific animations for specific situations. Rather than simply playing a "Run" animation, characters may play a specific "RunWithSword", "AngryRun", or "InjuredRun" animation. The Action Table is a simple data-driven approach to animation selection. This article describes the implementation of the Action Table, and goes on to describe how this technique can be extended to handle randomization and dynamic animation lists.
Realistic Character Behavior with Prioritized, Categorized Animation |
Abstract: Skeletal animation systems allow AI programmers to creates realistic behavior for characters by playing multiple, layered animations simultaneously. The challenge comes in trying to manage these independent layers of animation. This article describes the implementation of a system in which layers of animation are prioritized, and categorized by the region of the body they affect. This data-driven approach moves the management of the layers out of the code. The article and companion CD provide code for this layering system. Handling of blended transitions between animations is discussed using a bone caching technique.
Designing a GUI Tool to Aid in the Development of Finite State Machines |
The Beauty of Response Curves |
Simple and Efficient Line-of-Sight for 3D Landscapes |
An Open Source Fuzzy Logic Library |
Abstract: This article introduces the Free Fuzzy Logic Library (FFLL), an open source library that can load files that adhere to the IEC 61131-7 Fuzzy Control Language (FCL) standard. FFLL provides a solid base of code that you are free to enhance, extend, and improve. Whether used for rapid prototyping or as a component in an AI engine, FFLL can save significant time and money. The entire library and a sample program is included on the book's CD.
Section 3: Pathfinding with A*
Basic A* Pathfinding Made Simple |
Pathfinding Design Architecture |
How to Achieve Lightning Fast A* |
Practical Optimizations for A* Path Generation |
Abstract: The A* algorithm is probably the most widely used path algorithm in games, but in its pure form, A* can use a great deal of memory and take a long time to execute. While most optimizations deal with improving the estimate heuristic or with storing and searching the open and closed lists more efficiently, this article examines methods of restricting A* to make it faster and more responsive to changing map conditions. Such A* restrictions take the form of artificially constricting the search space, using partial solutions, or short-circuiting the algorithm altogether. For each restriction, the situations in which these optimizations will prove most useful are discussed.
Section 4: Pathfinding and Movement
Simple, Cheap Pathfinding |
Abstract: There are several cases in which using a lightweight AI method for pathfinding is appropriate, especially on low-powered hand-held gaming systems like the Game Boy Advance or various cell phones. This article presents a simple scheme in which a four-sensored, or whiskered robot, can move through an environment with surprisingly lifelike results. This scheme was successfully used in a number of published games for the Game Boy Color (including NFL Blitz, Disney's Tarzan, and Alice in Wonderland), as well as in several other games for mobile devices.
Preprocessed Solution for Open Terrain Environments |
Building a Near-Optimal Navigation Mesh |
Abstract: When you want your AI characters to perform pathfinding in a fully 3D environment, the kind of data structure you select to perform pathfinding will have an enormous impact on the performance of your pathfinding and the quality of the paths. A navigation mesh is one of the best ways to pathfind in these kinds of game worlds. It provides very fast pathfinding and allows you to find the optimal path from any arbitrary point in the game world to any other. This article describes in minute detail how to take arbitrary 3D world geometry ("polygon soup") and automatically construct and optimize a navigation mesh as a preprocessing step.
Realistic Turning between Waypoints |
Navigating Doors, Elevators, Ledges, and Other Obstacles |
Simple Swarms as an Alternative to Flocking |
Abstract: Craig Reynold's flocking algorithms have been well documented and are highly successful at producing natural-looking movement in groups of agents. However, the algorithms can be computationally expensive, especially where there are a large number of agents or a complex environment to detect against. For this reason, they are not always suited to real-time applications such as video games. This article details a much simpler algorithm for producing natural-looking movement in large swarms of creatures involving tens or hundreds of agents. Although this algorithm cannot guarentee separation of creatures within the swarm, the overall impression organic movement is very convincing.
Section 5: Tactical Issues and Intelligent Group Movement
Strategic and Tactical Reasoning with Waypoints |
Abstract: Non-player characters (NPCs) commonly use waypoints for navigation through their virtual world. This article will demonstrate how preprocessing the relationships between these waypoints can be used to dynamically generate combat tactics for NPCs in a first-person shooter or action adventure game. By precalculating and storing tactical information about the relationship between waypoints in a bit string class, NPCs can quickly find valuable tactical positions and exploit their environment. Issues discussed include fast map analysis, safe pathfinding, using visibility, intelligent attack positioning, flanking, static waypoint analysis, pinch points, squad tactics, limitations, and advanced issues.
Recognizing Strategic Dispositions: Engaging the Enemy |
Squad Tactics: Team AI and Emergent Maneuvers |
Abstract: AI squad behavior is made up of coordinated individual actions towards a joint goal. There are two basic coordination styles: centralized control by a leader, and decentralized cooperation between individuals. This chapter discusses the latter style in detail. Decentralized cooperation can already be realized with minor changes to "standard individual AI". This chapter illustrates how some tactical squad maneuvers can emerge from these coordinating individual AIs, using a squad assault as an example. The limitations of the approach are illustrated using a second example: a squad ambush. This chapter precedes and complements the chapter "Squad Tactics: Planned Maneuvers".
Squad Tactics: Planned Maneuvers |
Abstract: AI squad behavior can also be realized by designing an explicit team leader, responsible for planning and managing the squad's maneuver. This AI team leader assesses the squad's state, picks and plans the most appropriate squad maneuver. He executes the squad maneuver by issuing orders, and by interpreting feedback and information from the squad members. This is illustrated using a bounding overwatch squad advance. This centralized style to squad AI is more complex than the emergent behavior in "Squad Tactics: Team AI and Emergent Maneuvers". However, it does provide largely autonomous operating squads, able to execute complex maneuvers, and often combines well with some decentralized cooperation among squad members.
Tactical Team AI Using a Command Hierarchy |
Abstract: Team-based AI is becoming an increasingly trendy selling point for first- and third-person action games. Often, this is limited to scripted sequences or simple "I need backup" requests. However, by using a hierarchy of decision-making, it is possible to create some very convincing teams that make decisions in real time.
Abstract: In games today, formations are expected for any type of cohesive group movement. From squad-based first-person shooters to sports sims to real-time strategy games, anytime that a group is moving or working together it is expected to do so in an orderly, intelligent fashion. This article will cover standard military formations, facing issues, mixed formations, spacing distance, ranks, unit mobility, group pathfindng, and dealing with obstacles.
Section 6: General Purpose Architectures
An Efficient AI Architecture using Prioritized Task Categories |
Abstract: Real-time games have many diverse subsections: rendering, AI, collision detection, player-input and audio are just a few. Each of these tasks has a finite amount of time in which to execute, each is trying to do so as quickly as possible, and all of them must work together to give a rich, detailed gaming world. This article concentrates on the AI component and specifically, how to distribute it over time and make it fast for real-time games. It also details how to avoid processing until it's absolutely necessary. The goal will be to structure our AI so that it can execute quickly and efficiently. Two benefits will be realized by doing this; our games will run more smoothly and we'll have freed up the necessary processing power to bring about even more advanced AI.
An Architecture Based on Load Balancing |
A Simple Inference Engine for a Rule-Based Architecture |
Implementing a State Machine Language |
Abstract: This article presents a robust way to structure your state machines with a simple language. This State Machine Language will not only provide structure, but it will unleash some powerful concepts that will make programming games much easier. While the language itself is simple, it embodies some very important software engineering principles such as simplicity, maintainability, robustness, and ease of debuggine. The following article, "Enhancing a State Machine Language through Messaging," expands on this language with a powerful communication technique using messages. Each article has full soure code on the accompanying CD-ROM.
Enhancing a State Machine Language through Messaging |
Abstract: The previous article, "Implementing a State Machine Language," set the groundwork for a powerful language that can structure state machines in a simple, readable, and very debuggable format. In this article, that language will be expanded to encompass the problem of communication between AI game objects. This communication technique will revolutionize the State Machine Language by allowing complicated control flow and timers. Full source code is included on the accompanying CD-ROM.
Section 7: Decision-Making Architectures
Abstract: The blackboard architecture is a simple technique for handling coordination between agents. Although simple to implement, the architecture has proven elegant and powerful enough to be useful for problems ranging from synthetic character control to natural language understanding and other reasoning problems. This article explains the canonical blackboard architecture and shows many examples of how a game AI can benefit.
Introduction to Bayesian Networks and Reasoning Under Uncertainty |
Abstract: Since the 1990s, probabilistic inference techniques, and the specific subfield of Bayesian networks, have become immensely popular in the academic AI community. The game AI field, however, seems to have missed the boat. This is unfortunate, because Bayesian reasoning techniques can be extraordinarily helpful in getting your AI to reason about situations in a human-like fashion. This article provides a thorough introduction to the underlying concepts of probabilistic reasoning techniques and Bayesian networks, and describes a number of specific examples of the ways you can use them in game AI systems to perform more human-like reasoning.
A Rule-Based Architecture using Dempster-Shafer Theory |
Abstract: DST is a variant of probability theory that explicitly models ignorance and uncertainty. Instead of reasoning on discrete events, it manipulates sets of possible events when evidence is imprecise or partially contradictory. Since DST obeys axioms that are less restrictive than those of classic probability, it may apply in more circumstances.
An Optimized Fuzzy Logic Architecture for Decision-Making |
A Flexible Goal-Based Planning Architecture |
Section 8: FPS, RTS, and RPG AI
First-Person Shooter AI Architecture |
Abstract: This article provides a basic introduction to building an AI architecture for a first-person shooter game (such as Quake or Unreal) or a first-person sneaker (such as Thief: The Dark Project). We discuss the major components of an FPS AI (including specific subsystems for animation, movement and pathfinding, behavior, combat, sensory modelling, and scripting and trigger systems) and how those components should fit together.
Abstract: RTS games are one of the more thorny genres as far as AI is concerned, and a good architecture is necessary to ensure success. Most examples presented in this article are taken from the work done on Empire Earth. Issues include game components (civilization manager, build manager, unit manager, resource manager, research manager, and combat manager), difficulty levels, challenges (random maps, wall building, island hopping, resource management, stalling), and overall strategies.
An Economic Approach to Goal-Directed Reasoning in an RTS |
Abstract: In this article, we discuss one approach to creating an agent for a real-time strategy game, using the Utility Model. This approach takes Economic theories and concepts regarding consumer choice, and creates a mapping onto our game agent's decision space. We explain relevant AI terminology (goal-directed reasoning, reactive systems, planning, heuristic functions) and Economic terminology (utility, marginal utility, cost, production possibilities), and introduce a simplistic RTS example to provide a framework for the concepts.
The Basics of Ranged Weapon Combat |
Abstract: This article gives a brief introduction to the problems of firing ranged weapons. We discuss to-hit rolls, aim point selection, ray-testing, avoiding friendly fire incidents, dead reckoning, and calculating weapon trajectories for ballistic weapons.
Level-Of-Detail AI for a Large Role-Playing Game |
Abstract: With thousands of objects demanding AI time slices in Neverwinter Nights, it would be difficult to satisfy all creatures and maintain a playable frame rate. The level-of-detail AI schemes used allowed the game to achieve the perception of thousands of actors thinking simultaneously. The article discusses how to subdivide your game objects into categories, and how certain time-intensive actions (such as pathfinding and combat) can be reduced to make more efficient use of the time available to AI.
A Dynamic Reputation System Based on Event Knowledge |
Abstract: This article describes a non-player character (NPC) reputation system (a mechanism for dynamically managing NPCs' opinions of each other and of the player in order to influence the NPCs' actions). Most existing reputation systems manage NPCs' opinions globally. The reputation system this article describes instead changes a specific NPC's opinions only if the NPC has direct or indirect knowledge of events that trigger a change. The article describes the data structures required for the reputation system, the way they work together to make the complete system, and the way the system fits into the overall design of NPC behavior.
Section 9: Racing and Sports AI
Representing a Race Track for the AI |
Abstract: This article is the first in a series of three racing AI articles and describes a practical representation of a racetrack for an AI system. The representation includes defining sectors, interfaces, the driving lines (racing line, overtaking line), path type, terrain type, walls, hairpin turns, and brake/throttle points. Methods for determining the current sector and the distance along a sector are also discussed.
Abstract: This is the second article in a series of three racing AI articles that describes how to implement an AI capable of racing a car around a track. Although the AI will follow predefined driving lines, it will not rigidly follow the track like a train on rails, but merely use these lines as a guide. This goal is to have the AI produce an output that emulates human input; specifically joystick and/or key presses. Using this method, the game engine only needs to gather input from the AI controller instead of a human input device. The article will cover the basic AI framework (FSM, fixed-time step, controlling the car, simplifying with 2D), traversing sectors (anticipating the road ahead, hairpin turns), driving to a target, overtaking, handling under-steer and over-steer (detecting the car's stability, testing for stability, correcting the car), wall avoidance, other states (airborne, off the track), and catch-up logic.
Abstract: This is the final article of the three article series, and shows ways to train the AI to race optimally around a racetrack. Issues covered include tuning the car handling (adjusting parameters, converging on optimum values, modifying parameter values, modifying the range, training at high simulation speeds) and real-time editing (real-time track modification, user control overriding AI).
Competitive AI Racing under Open Street Conditions |
Simulating Real Animal Behavior |
Agent Cooperation in FSMs for Baseball |
Section 10: Scripting
Scripting: Overview and Code Generation |
Scripting: The Interpreter Engine |
Scripting: System Integration |
Creating Scripting Languages for Non-Programmers |
Scripting for Undefined Circumstances |
Abstract: Games are increasingly allowing the player to set the agenda. Want to while away hours mucking around with the game physics by throwing rocks into crowds of villagers? No problem! On the other hand, a strong storyline helps to inform the player of their goals, and provides a context for their actions. Traditionally, storylines in games have been advanced via cinematic sequences, and it is common for these to be displayed using the game engine. Can we resolve the conflict that occurs when we simultaneously afford the player the freedom to set the agenda and the game designers the ability to impose a storyline? What if a crucial moment in the story depends on the presence of the harmless little villager that the player unthinkingly threw into the ocean at the beginning of the game? Even worse, what if a non-player character under AI control intrudes into a cinematic sequence and begins to wreak havoc? In this article we discuss the features that were implemented in the game "Black & White" to allow the game designers to create storyline-advancing "Challenges" without compromising the unpredictable nature of the game.
The Perils of AI Scripting |
Abstract: Scripting is an enormously popular technique for developing game AI systems, but it can also be enormously dangerous. This article describes some of the considerations that you should think about very carefully before you jump on the scripting bandwagon, many of which you might not otherwise discover until it's too late. We also describe a number of the things that can go wrong when your lofty scripting language ambitions collide with the realities of game development.
How Not To Implement a Basic Scripting Language |
Abstract: This paper goes into some of the mistakes that were made while writing the scripting languages for Baldur's Gate and Neverwinter Nights. The four major points, which are covered with anecdotes: the lack of up-front design, ignoring early-adopter feedback, believing the code will only be used for one project, and believing the language will be used for one specific task.
Section 11: Learning
Learning and Adaptation in Games |
Abstract: It is anticipated that the widespread adoption of learning in games will be one of the most important advances ever to be made in game AI. Genuinely adaptive AIs will change the way that games are played by forcing the player to continually search for new strategies to defeat the AI. This article presents a detailed examination of the different approaches available for adding learning and adaptation to games and draws on the author's experiences of AI development to provide numerous practical examples. The reader is guided through the decisions that must be made when designing an adaptive AI, and summaries of the problems that are most frequently encountered with practical implementations are provided along with descriptions of effective solutions. The CD that accompanies the book contains source code for a genetic programming class, which can be used to evolve rule-based AI, and genetic algorithm and population-based incremental learner classes, which can be used to evolve AI more generally. The practical application of all these classes is illustrated by evolving an AI that successfully navigates a simple environment.
GoCap: Game Observation Capture |
Pattern Recognition with Sequential Prediction |
Abstract: This article provides a simple but efficient algorithm for recognizing repetitive patterns in number sequences. Pattern recognition is something that humans are very good at, but for a computer this is not so easy. Too often a game AI can be beaten by repeatedly performing the same trick, just because it is unable to perceive the pattern. This article explains how to deal with this problem and shows you how to map game events onto useful number sequences. Furthermore, it describes a few possible applications of the algorithm in computer games.
Using N-Gram Statistical Models to Predict Player Behavior |
Abstract: N-Grams are statistical constructs used to predict sequences of events in situations that exhibit the property of local structure. Language is one such context: the probability of hearing the word "fries" is higher if one has just heard the word "french" than if one has just heard the word "fruit". Some games, specifically fighting games in which players develop signature move combinations, also exhibit this property. The article describes how to train an AI to recognize patterns and predict the human player's next move using N-Gram models.
Practical Natural Language Learning |
Abstract: The perception of intelligence seems to be directly related to the observation of behavior that is surprising yet sensible. Natural language interfaces were common features of computer entertainment software prior to the advent of sophisticated computer graphics, but these were often repetitive in nature: encountering the same scripted conversation over and over again quickly becomes boring. Stochastic language models have the ability to acquire various features of a language from observations they make, and these features can be used generatively to produce novel utterances that have the properties of being both surprising and sensible. In this article we show how such a system, when used to host in-game socially-oriented conversations, can greatly contribute towards the subjective impression of intelligence experienced by the player.
Testing Undefined Behavior as a Result of Learning |
Abstract: We consider learning to be the essence of Artificial Intelligence. Non-player characters, when granted the ability to learn, are given the potential to surprise and entertain the player in completely unexpected ways. This is very reinforcing from the player's point of view, but a nightmare for a testing department. How can they assure the quality of a game that may behave completely differently depending on the who's playing it? In this article we show, via a case study of the computer game "Black & White", exactly how a testing department can achieve their goals when the product they're testing features unpredictable learning AI.
Imitating Random Variations in Behavior using a Neural Network |
Abstract: As game AI has increased in sophistication, it has become possible to create computer controlled agents that display remarkably human-like behavior. One of the few indications that an agent is non-organic is the frequently clinical nature of their actions, an effect exacerbated by the often ad hoc mechanisms used to add random variations. This article shows how neural networks can be taught to imitate the actual random variations in behavior that are exhibited by real people. This makes it possible to simulate the playing styles of different sports personalities in unprecedented detail - even the extent to which, for example, the cueing direction and position of the cue ball relative to the cushion affect the accuracy of a pool player's shots. The article assumes minimal knowledge of neural networks and illustrates the techniques through their application to a real game. The CD that accompanies the book contains all the source code for the game, along with that for the neural network class, which is designed as a plug-in component that can easily be transferred to other applications.
Genetic Algorithms: Evolving the Perfect Troll |
Abstract: Genetic Algorithms mimic the process of natural selection to evolve solutions to problems that cannot be solved analytically. Candidate solutions, generated at random, are tested and evaluated for their fitness; the best of them are then bred and the process repeated over many generations, until an individual of satisfactory performance is found. This article explains the biological foundations of genetic algorithms and illustrates their behavior with an example: evolving a troll for a fantasy game.
The Dark Art of Neural Networks |
|
