|
|
AI Game Programming Wisdom 2
67 Articles, Edited by Steve Rabin, 2003.
|
Survey of Lowest Known Online Prices
$44.07 (37% off) Amazon.com (free shipping)
$69.95 (0% off) BarnesAndNoble.com
Section 1: General Wisdom
 |
Common Game AI Techniques |
Abstract: This article provides a survey of common game AI techniques that are well known, understood, and widely used. Each technique is explained in simplest terms along with references for delving deeper. Techniques include A* Pathfinding, Command Hierarchies, Dead Reckoning, Emergent Behavior, Flocking, Formations, Influence Mapping, Level-of-Detail AI, Manager Task Assignment, Obstacle Avoidance, Scripting, State Machines, Stack-Based State Machines, Subsumption Architectures, Terrain Analysis, and Trigger Systems.
Promising Game AI Techniques |
Abstract: This article provides a survey of promising game AI techniques that are on the forefront of game AI. Each technique is explained in simplest terms along with references for delving deeper. Techniques include Bayesian Networks, Blackboard Architectures, Decision Tree Learning, Filtered Randomness, Fuzzy Logic, Genetic Algorithms, N-Gram Statistical Prediction, Neural Networks, Perceptrons, Planning, Player Modeling, Production Systems, Reinforcement Learning, Reputation Systems, Smart Terrain, Speech Recognition and Text-to-Speech, and Weakness Modification Learning.
New Paradigms in Artificial Intelligence |
Abstract: This article introduces some new ideas in the field of Artificial Intelligence (AI). Many researchers are looking more toward nature for inspiration, finding many useful design solutions to the problem of behaving in a dirty, noisy world. While traditional AI techniques (OldAI) have had much success in formal domains, such as chess, they often do not scale well and are sometimes impossible to apply in less discrete domains.
A better understanding of the techniques inspired by natural intelligence (NewAI) in addition to OldAI techniques will lead to a much more complete toolbox for an AI designer. This will allow agents to be designed to behave more naturally and a better understanding of why they fail in particular situations, leading to more believable motions and behaviors in games.
Artificial Stupidity: The Art of Intentional Mistakes |
Abstract: What makes a game entertaining and fun does not necessarily correspond to making its opponent characters smarter. The player is, after all, supposed to win. However, letting a player win because of badly programmed artificial intelligence is unacceptable. Fun can be maximized when the mistakes made by computer opponents are intentional. By finely tuning opponent's mistakes, one can prevent computer opponents from looking dumb, while ensuring that the player is still capable of winning. Additionally by catching, identifying and appropriately handling genuine problems with an AI system, one can turn situations in which computer opponents would otherwise look dumb into entertainment assets. Surprisingly many game developers pay scant attention to such ideas. Developers' efforts are often so concentrated on making their computer opponents smart that they neglect to adequately address how the AI makes the game fun.
Arcade AI Doesn't Have to Be Dumb |
Abstract: Good game AI is tricky no write no matter what your resources are. When you're faced with limited CPU and RAM, such as with an arcade game or on a handheld, it can be nearly impossible. Arcade AI Doesn't Have to be Dumb covers various techniques used in the development of the Sega arcade game Behind Enemy Lines which helped give its AIs a bit more spontaneity and seeming intelligence than found in most shooters while not using up much memory or CPU in the process.
The Statistics of Random Numbers |
Abstract: Random numbers are used most heavily by Artificial Intelligence and games in general. To ignore their potential is to make the game predictable and boring. Using them incorrectly can be just as bad as ignoring them outright. Understanding how random numbers are generated, their limitations and their capabilities, can remove many difficulties of using them in your game. This article offers insight into random numbers, their generation, and methods to separate good ones from bad.
Filtered Randomness for AI Decisions and Game Logic |
Abstract: Conventional wisdom suggests that the better the random number generator, the more unpredictable your game will be. However, according to psychology studies, true randomness over the short term often looks decidedly unrandom to humans. This article shows how to make random AI decisions and game logic look more random to players, while still maintaining strong statistical randomness. Full source code, ready to drop into your game, is supplied on the book's CD-ROM.
Section 2: Pathfinding and Movement
Search Space Representations |
Abstract: Navigation in games is about much more than the search algorithm used. An equally important (and often overlooked) consideration is the way the game represents the game world to allow agents to perform a search on it (the "search space representation"). Different games have used nearly every kind of search space representation imaginable. This article discusses the relative strengths and weaknesses of square and hexagonal grids, quadtrees, corner graphs, waypoint graphs, circle/cylinder-based waypoint graphs, space-filling volumes, and triangle-based and N-sided-convex-poly-based navigation meshes for navigating in different types of games. We also discuss additional issues that may change the relative merits of different representations, such as the different movement capabilities of different units and the need to interact with a local pathfinding / dynamic obstacle avoidance system.
Inexpensive Precomputed Pathfinding Using a Navigation Set Hierarchy |
Abstract: The increasing use of precomputed navigation data in today's computer games has led developers to experience both the joys of lightning-fast best path determination and the agony of the memory cost associated with storing all that information. Often, the memory requirements are prohibitive - especially on console platforms - and much slower traditional solutions are required. In this article we present a hierarchical scheme that retains virtually all of the processing speed of the typical precomputed solutions, while dramatically reducing the memory requirements.
Path Look-up Tables - Small is Beautiful |
Abstract: The fastest way to "find" a path from waypoint A to B is not to search. It is much faster to look up a path from a pre-computed table. Being able to find paths ten to two hundred times faster than with A* may make a big difference. This frees up CPU budget for other AI decisions. It allows the use of paths and travel times in a much larger portion of the AI's reasoning. However, path lookup tables are not without disadvantages. The amount of memory required for the tables often prohibit their use for anything other than small levels.
This article discusses optimizations of path lookup tables, and takes a look at two designs that offer the performance benefits at lower costs. First, a path lookup matrix using indices that consumes only one fourth of traditional path lookup tables. Second, an area-based path lookup table which consumes even less, and scales much better, at the costs of a more complex lookup.
An Overview of Navigation Systems |
Jumping, Climbing, and Tactical Reasoning: How to Get More Out of a Navigation System |
Abstract: Few AI related systems are more common and pervasive in games than character navigation. As 3D game engines become more and more complex, characters will look best if they too adapt with equally complex behavior. From opening a door, to hopping over an errant boulder and crouching behind it, keeping AI tied to the environment of your game is often one of the most difficult and important challenges.
Typically these complex behaviors are handled by scripts or a hand coded decision maker. However, we will show that the points and edges within a navigation system are a natural place to store environment specific information. It is possible to automatically detect many properties about the area around a point or edge. This approach allows an AI character to make use of embedded environment information for tactical reasoning as well as low level animation and steering.
Hunting Down the Player in a Convincing Manner |
Abstract: This article is concerned with how to make a game character convincingly hunt or search towards a goal. Gamers expect intelligent behavior from opponents but sometimes it's all too easy to let the AI cheat a little too much. In order to bring about believable searching behavior it is often not sufficient to simply route a game character directly towards its goal; the path will be too direct, too contrived and generally afford little in the way of gameplay possibilities. We must ensure that the character explores and looks like it's trying to find its goal by a process of search rather than direct, shortest-path route following. This article shows how to do this effectively and with low processing cost. The end result is convincing searching and/or hunting behavior that gradually homes in on a goal.
Simple parameters are available to control how quickly goal discovery is likely to happen and also the directness of the resultant path. The method assumes the existence of a working pathfinding/routing system with the described technique being equally suited to 2D and 3D environments. The discussion will show the benefits and scope of indirect paths in terms of the opportunities offered for gameplay, perceived character intelligence and believability.
Avoiding Dynamic Obstacles and Hazards |
Abstract: Static obstacle avoidance is, barring efficiency considerations, a solved problem in games. The A* algorithm is generally used to search a graph data structure representing the navigable terrain in the level to find a route to a goal. However, many game agents still cope badly with dynamic obstacles encountered along the route, often relying entirely on collision code to get them out of trouble. Bumping into entities not only looks unintelligent, it can also have negative game-play implications, especially if the entity is a hazard.
This article outlines a pragmatic approach to solving this problem at the level of short-range movement. Inspired by flocking algorithms, the method involves taking an agent's desired velocity and adding "repulsion" vectors from nearby entities in the agent's memory. The resulting velocity will tend to send the agent around dynamic obstacles and hazards. A nice feature is that two agents on a collision course will intelligently sidestep in opposite directions in order to avoid each other. Moreover, the situation in which a short-range destination is completely blocked by an entity is detected early, so that a new long-range route can be found well before a collision has taken place. The approach is fast and produces very convincing avoidance behavior.
Intelligent Steering Using PID Controllers |
Abstract: In order to achieve the realism demanded by many of today's games, physics simulations have become more complex and accurate. Although realistic physics simulations are often rewarding for human players to control, they can be frustrating from an AI programmer's perspective. As these simulations become more complex, the effects of a given input to the system become less clear, and it becomes more difficult to write a simple if...then...else logic tree to cope with every possible circumstance. Thus, new methods of controlling objects operating under these rules must be developed.
In the context of game AI, the primary use for such control is in the steering of objects operating under the constraints of a physics system. The article will detail a solution to this problem by applying an engineering algorithm known as a Proportional-Integral-Derivative (PID) Controller that has been used for over 50 years. The article comes with full source code to a demo that let's you interactively play with the PID variables that control a rocket steering toward a moving target.
An AI Approach to Creating an Intelligent Camera System |
Abstract: In this article, we will attempt to outline one method of implementing a camera system capable of handling a diverse and dynamic three-dimensional environment. We will detail the approaches taken during development of a to-be-released title, outlining the issues we encountered and how these were overcome.
Section 3: Group Movement, Tactics, and Planning
Constraining Autonomous Character Behavior with Human Concepts |
Abstract: A current trend in Game AI is the move from scripted to autonomous character behavior. Autonomous behavior offers several benefits. Autonomous characters can handle unexpected events that a script might not have anticipated, producing emergent gameplay. Level designers can focus on creating worlds packed with opportunities for characters to showcase their behaviors, rather than getting bogged down scripting the actions of individual characters. Various articles have described how to design goal-based autonomous behavior, where characters select the most relevant behavior based on their desires, sensory input, and proximity to objects of interest. In theory it sounds simple enough to drop a character with a palette of goals into a level filled with tagged objects, and let him take care of himself. In practice, there are many additional factors that need to be considered to get believable behavior from an autonomous character. This article presents a number of factors that should be considered as inputs into the relevancy calculation of a character's goals, in order to produce the most believable decisions. These factors are based on findings encountered during the developement of Monolith Production's No One Lives Forever 2: A Spy in H.A.R.M.'s Way.
Simple Techniques for Coordinated Behavior |
Abstract: There are a number of common problems that arise when developing AI systems for combat with multiple enemies. Agents block each other�s line of fire. Agents follow the exact same path to a target, and often clump up at a destination. Some agents are oblivious to a threat while others nearby are getting shot or even killed. Multiple agents decide to do the exact same action or animation simultaneously. It would seem that a group behavior layer of complex higher-level reasoning would be needed to solve these problems. In fact, these problems can be solved with simple techniques that use existing systems and leverage information that individual agents already have. This article describes simple techniques that can be used to solve coordination problems, using examples from Monolith Productions' "No One Lives Forever 2: A Spy in H.A.R.M.'s Way."
Abstract: The use of teammates has become very popular among the first and third person action genres in recent years, in both the simulation and arcade sub-genres. However, implementing convincing teammates who will not run in your path while you are shooting, nor disappear into a far corner of the map, is quite an involved process. By implementing some key rules it is possible to create teammates who can usefully back you up in the thick of the action, follow instructions reliably, and survive with you until the end of the game.
Applying Goal-Oriented Action Planning to Games |
Abstract: A number of games have implemented characters with goal directed decision-making capabilities. A goal-directed character displays some measure of intelligence by autonomously deciding to activate the behavior that will satisfy the most relevant goal at any instance. Goal-Oriented Action Planning (GOAP) is a decision-making architecture that takes the next step, and allows characters to decide not only what to do, but how to do it. A character that formulates his own plan to satisfy his goals exhibits less repetitive, predictable behavior, and can adapt his actions to custom fit his current situation. In addition, the structured nature of a GOAP architecture facilitates authoring, maintaining, and re-using behaviors. This article explores how games can benefit from the addition of a real-time planning system, using problems encountered during the development of Monolith Production's No One Lives Forever 2: A Spy in H.A.R.M.'s Way to illustrate these points.
Hierarchical Planning in Dynamic Worlds |
Goal Directed Behavior using Composite Tasks |
Abstract: This article will introduce the reader to goal directed behavior and offers several examples of games that have used it to increase the believability of the agents in those games. The article then goes on to discuss the implementation of the Composite Task concept that was designed and developed to provide goal directed behavior for the agents in a military tactical combat training simulator. Finally, the simulator itself is briefly discussed and references to additional information on goal directed behavior are provided.
Section 4: AI Animation Control
Simplified Animation Selection |
Abstract: This article describes an animation selection mechanism for determining the active animations of an arbitrary number of animation channels, based on a narrow set of discrete inputs and events, in a manner that's easy to manipulate for both artists and AI programmers. The system allows for just a few simple inputs (such as a character's cardinal movement direction, posture, weapon type, etc) and isolated triggered events (such as waves or taunts) to determine the entire animation state of a character at a given time, even in the presence of hundreds of animations.
The animation channels, input names and values, and control-flow "actions" are all configurable via a simple artist-friendly scripting language, allowing the artist to take nearly full control over the animation selection pipeline. In addition, the AI programmer's job is made easier due to the simplified conduit between a character's abstract behavior and its animation inputs. The result is an animation selection scheme that gives the artist a level of control usually only available to programmers, without losing the simplicity and flexibility of other data-driven approaches.
Abstract: This article discusses an extensible plug-in based animation pipeline that combines the handling of pre-built and dynamically-generated animation facilities into a single unified mechanism. This allows artists and AI programmers to take advantage of procedural animation effects in the same manner as regular animations, adding an additional level of flexibility and control to the look of your characters.
Animations are created based on a set of "abilities" that activate and deactivate at different points in time within the animation's length. These abilities can perform any number of effects on the character, from a simple application of pre-built animation frame data, to a complex on-the-fly Inverse Kinematics operation using external "satellite" points in space provided by an external source, to esoteric visual effects like bone attachment manipulation and vertex deformation. The abilities themselves are provided as plug-ins, and new abilities can be added during the development process (or in some cases even afterward, by "mod" authors) without changing the core of the animation pipeline. The process of creating of these kinds of animations can be made friendly to artists without much effort, via a simple GUI dialog box based primarily around a single list view control.
Intelligent Movement Animation for NPCs |
Abstract: This article describes an intelligent movement animation system for non-player characters (NPCs). This system is used in the PC and PS2 versions of Fellowship of the Ring and two upcoming games from Surreal Software. First, the article briefly explains steering behaviors and animation systems. Next, it describes the middle layer between them. This layer includes a system for NPC movement, a movement animation behavior, and an animation controller. The movement animation behavior ensures that the animation being played and the way it is being played are appropriate, given the NPC's current movement. The animation controller provides a simple high-level interface to the underlying animation system. Finally, the article also gives some tips on gotchas that can come up during implementation of the middle layer and some ideas for further enhancements.
Section 5: State Machines
The Ultimate Guide to FSMs in Games |
Abstract: The intention of this article is to give a comprehensive overview of FSMs in games. This article examines various FSM architectures and discusses the systems that surround them. The FSM is studied at the game integration level, the update scheme, and efficiency/optimization. Extensions are discussed for extending state functionality (OnEnter, OnExit), extending the structure into hierarchical and fuzzy state machines, and coordinating multiple FSMs. Various FSM schemes are compared and contrasted.
Stack-Based Finite-State Machines |
Abstract: Finite-state machines are a very popular technique for developing game AI, but they lack any intrinsic capability for remembering the way a client has traversed the state graph. We discuss a technique for extending the traditional finite-state machine with a state stack in order to allow it to remember previous states, thereby allowing AI agents to resume the execution of behaviors that were previously interrupted. In some cases, such as modeling behaviors with an FSM, this can often allow us to create much simpler and more concise finite-state machines than would be possible with a standard FSM.
Implementing a Data-Driven Finite-State Machine |
Abstract: This article describes an implementation of a data-driven Finite State Machine (FSM) class. Using a data-driven design allows quick tweaking of state transition logic without having to recompile any source code, as well as the ability to associate different character behavior to different AI characters through external data files. The FSM class presented in this article instantiates FSMs as defined in external data files, automates the evaluation of state transition logic and provides the functionality to define functions to be executed when entering, updating, and exiting states.
Finite-State Machine Scripting Language for Designers |
Abstract: AI is often implemented with finite state machines (FSM's) or layers of finite state machines, which are difficult for game designers to edit. Looking at typical AI FSM's, there are design patterns that occur repeatedly. We can use these patterns to make a custom scripting language that is both powerful and approachable. The technique can be further extended into a "stack machine" (pushdown automata) so that characters have better memory of previous behaviors.
Section 6: Architecture
A Subsumption Architecture For Character-Based Games |
Abstract: The Subsumption Architecture was invented in 1986 by Rodney Brooks to give robust real-world behavior to robots. The technique works equally well for the "virtual robots" of the video game world. It cleanly decomposes the implementation of an AI driven character into concurrently executing layers of finite state machines (FSMs). Lower layers take care of immediate goals; upper layers take care of long-term goals. The architecture solves three major problems with character AI: minor setbacks causing a character to lose focus on a long term goal, characters getting stuck on a goal that is no longer relevant, and robust handling of animation and character physics.
An Architecture for A-Life |
Abstract: This chapter presents Insect AI, a straight forward architecture, notation, and design methodology for artificial life. The principles and techniques are derived from neuroethology, the study of neural control of behavior. Simple computational units are introduced and examined, and the creation of Insect AI agents is demonstrated. Insect AI agents exhibit a number of interesting properties which satisfy the characteristics of motivated behavior as defined in the ethological literature - behaviors can be grouped and sequenced, the agents are goal directed, behavior can change based on the internal state of the agent, and behaviors can persist if stimuli are removed. A number of agents are created as examples, ranging from a simple light follower to an artificial insect that shows all the characteristics of motivated behavior.
A Flexible Tagging System for AI Resource Selection |
Abstract: As game designs increasingly evolve away from linear, scripted gameplay experiences and toward open-ended worlds and gameplay based on emergent behaviors, gameplay has become much less predictable, and it has become increasingly difficult to create content that exactly matches the specific situation the user will experience at any given moment. Although in an ideal world, it would be possible to create content that responds to all of the different possible game states, open-ended game designs present far too many unpredictable situations, and one can never hope to create enough audio or animation content to handle all of them. However, it is possible to fit some of the specifics of the situation some of the time, and create content at varying levels of specificity. We present a flexible tagging system that allows you to create art and audio content across a wide spectrum from the most general to the most specific, along with a simple resource-selection algorithm that allows you to select the most situation-specific piece of content to use in any given situation. We also discuss potential applications of this system for audio and animation assets in detail.
Motivational Graphs: A New Architecture for Complex Behavior Simulation |
Abstract: Recent research in cognitive science and ethology has led to the development of biologically-inspired autonomous behavior models. Such models differ from classical AI models since they account for both internal state and environmental constraints. They define a new generation of systems, closer to Artificial Life and situated cognition than to classical AI.
In the present article, we introduce a new architecture based on such models. Applied to game development, this architecture enables designers and developers to easily describe, model and implement realistic autonomous software agents. This architecture, called a motivational graph, is a hybrid between rule-based approaches and connectionist systems. Especially, it uses concepts such as activity propagation to trigger modules within a hyperconnected graph. In this article, we demonstrate the benefits of this approach: multitasking, opportunism, tradeoff and emergence.
Minimizing Agent Processing in Conflict Desert Storm |
Section 7: FPS, RTS, and Strategy AI
Using a Spatial Database for Runtime Spatial Analysis |
Abstract: AI developers have employed a number of different techniques for performing spatial reasoning about a game world using precomputed "hints" placed by level designers or automated game-world analysis tools. However, as game worlds increasingly feature larger numbers of AI characters and moveable physically-modeled objects, it becomes increasingly important to model the ways that the dynamic aspects of the ever-changing game world influence an AI's spatial reasoning. We discuss a spatial database technique that allows you to perform spatial reasoning about any number of different factors that can potentially affect an AI agent's reasoning about the game environment and techniques for combining multiple factors together to construct desirability heuristics. A spatial database can also allow you to implicitly coordinate the activities of multiple AI agents simply by virtue of sharing the same data structure.
Performing Qualitative Terrain Analysis in Master of Orion 3 |
Abstract: One challenge for many strategy game AIs is the need to perform qualitative terrain analysis. By qualitative we mean that the analysis is based on fundamental differences between different types of locations - for instance areas that are visible to our opponents, areas that are impassible, or areas vulnerable to enemy fire. In Master of Orion 3 we identify stars that are inside or outside of our empire's borders, those that are threatened by our opponents, and those that are contested (shared with an opponent). This information is used to identify locations where we need to concentrate our defenses and to help us expand into areas that minimize our defensive needs while maximizing the territory we control.
In this article we will present the algorithms used to make the qualitative distinctions given above and the ways in which the AI uses that information. The lessons we would most like the reader to take away from this article are not the specifics of the algorithms used but rather the thought processes involved in applying qualitative reasoning to terrain analysis. The important questions to address are: what are the qualitative distinctions we should look for, how can we recognize them, and what uses can the AI make of that information. Our algorithms are but a single example of how these questions can be answered.
The Unique Challenges of Turn-Based AI |
Abstract: Writing a turn-based AI presents a number of unique programming and game design challenges. The common thread uniting these challenges is the user's complete control over the game's speed. Players willing to invest extreme amounts of time into micro-management and players looking to streamline their gaming experience via automated decision-making present two very different problems for the AI to handle. Further, the ability to micro-analyze turn-based games makes predictability, cheating, and competitive balance extremely important issues. This article outlines how the Civilization III development team dealt with these challenges, using specific examples to illuminate some practical solutions useful to a programmer tasked with creating an AI for a turn-based game.
Random Map Generation for Strategy Games |
Abstract: While there are numerous articles dedicated to the generation of random maps for games, there is little published information on random maps for strategy games in particular. This subset of map generation presents distinct challenges as evident by the relatively few games that implement them. While the techniques described here can be used to create maps suitable for any type of game, this system is specifically designed to create a variety of successful random maps for real-time strategy games. This article describes the random map generation implementation as found in the RTS game Empire Earth (EE) developed by Stainless Steel Studios.
Transport Unit AI for Strategy Games |
Abstract: Unit AI refers to the micro-level artificial intelligence that controls a specific unit in a game and how that unit reacts to input from the player and the game world. Transports present a particular challenge for unit AI as many units must work together to achieve their common goal, all the while attempting to minimize player frustration. This article discusses the general transport unit AI challenge and a successful solution. Land, air, naval, and building transports (such as fortresses and town centers) will be discussed and a class hierarchy implementation will be suggested. Algorithms for the loading (including the calculation for rendezvous points) and unloading of transports will be presented as well as warnings for particular pitfalls.
This article assumes some sort of finite-state-machine-based unit AI system and is applicable to any game in which there are multiple units in need of transporting. This article details the transport unit AI as found in the Real-Time Strategy (RTS) game Empire Earth (EE) developed by Stainless Steel Studios.
Wall Building for RTS Games |
Abstract: Most real-time strategy games include walls or similar defensive structures that act as barriers for unit movement. Having a general-purpose wall-building algorithm increases the competitiveness of computer opponents and provides a new set of options for the random mission generation. The article discusses a wall building algorithm that uses the greedy methodology to build a wall that fits the definition, protects the desired location, and meets the customizable acceptance criteria. The algorithm takes advantage of the natural barriers and map edges to minimize the cost of building a wall. The algorithm discussion focuses on importance of traversal and heuristic functions, details of implementation, and various real world problems. Advanced topics such as minimum/maximum distance requirements, placement of gates and an unusual wall configurations are elaborated on. Full source code and a demo are supplied.
Strategic Decision-Making with Neural Networks and Influence Maps |
Abstract: Influence maps provide a strategic perspective in games that allows strategic assessment and decisions to be made based on the current game state. Influence maps consist of several layers, each representing different variables in the game, layered over a geographical representation of the game map. When a decision needs to be made by the AI player, some or all of these layers are combined via a weighted sum to provide an overall idea of the suitability of each area on the map for the current decision. However, the use of a weighted sum has certain limitations.
This article explains how a neural network can be used in place of a weighted sum, to analyze the data from the influence map and make a strategic decision. First, this article will summarize influence maps, describe the current application of a weighted sum and outline the associated advantages and disadvantages. Following this, it will explain how a neural network can be used in place of a weighted sum and the benefits and drawbacks associated with this alternative. Additionally, it will go into detail about how a neural network can be implemented for this application, illustrated with diagrams.
Multi-Tiered AI Layers and Terrain Analysis for RTS Games |
Abstract: RTS games tend to handle soldier AIs individually, giving each unit specific tasks from the computer player. Creating complicated, cooperative tactics are impossible for such systems without an immense effort in coding. To develop complex, large-scale plans, a mechanism is needed to reduce the planning devoted to the individual units. Some games already collect individual soldiers into squads. This reduces the planning necessary by a factor of ten, as one hundred soldiers can be collected into ten squads. However, this concept can be taken farther, with squads collected into platoons, platoons into companies, and so on. The versatility such groupings give an AI system are immense. This article will explore the implementation of a multi-tiered AI system in RTS-type games, including the various AI tiers, a set of related maps used by the AI tiers and an example to illustrate the system.
Designing a Multi-Tiered AI Framework |
Abstract: The MTAIF allows an AI to be broken up into three concrete layers, strategic, operational and a tactical layer. This allows for an AI programmer to have various AIs focus on specific tasks, while at the same time having a consistent overall focus. The MTAIF allows for the strategic layer to be focused exclusively on matters that can affect an empire on a holistic scale, while at the operational level the AI is in tune with reports from the tactical level. A differing factor from many other architectures is that the MTAIF does not allow decisions to be made on a tactical scale that would violate the overall strategic policies. This in turn forces highlevel strategic policies to be enforced in tactical situations, without the AI devolving into a reactionary based AI.
Section 8: Racing and Sports AI
Racing Vehicle Control using Insect Intelligence |
Abstract: Despite their simplicity and inability to adapt by learning, insects and other simple animals manage to survive and navigate in the complex and unpredictable real world very well. Since evolution tends to find very efficient solutions to the problems faced by living creatures a lot of the mechanisms used by simple animals are relatively efficient, and in addition often have a potential for behavioral richness far beyond the extra processing power it takes to model them.
This article presents a robust and extensible system architecture which is based around emergent behaviors, and several techniques which utilize principles derived from the results of academic AI research into modeling insect level intelligence - in particular vision based steering behavior utilizing simple compound eye-like sensors.
Fast and Efficient Approximation of Racing Lines |
Abstract: Racing game AI has developed to the point where it is able to challenge even the best players. To do this, an AI usually relies heavily on information stored along the length of a track, which provides it with instructions on how it should approach upcoming sections. Critically, this information is derived during a game's development, almost always from the way in which human players drive each track, and will therefore not be available for random or player created tracks. This prevents random track generators and track editors being shipped with many racing games, because it would not also be possible to provide a challenging AI that could compete against the player on all the resulting tracks. This article presents an algorithm that can be used to quickly and efficiently derive approximations to racing lines, thus providing information vital to an AI. A demonstration implementation of the algorithm in C++ is included with the article.
The Art of Surviving a Simulation Title |
Abstract: This article aims to simplify the task of writing simulation AI by providing a number of guidelines. These were adopted after working on the space simulation, "Independence War 2" (I-War 2) and continue to bring success to the futuristic racing game, "Powerdrome". The guidelines cover many aspects from higher-level design and keeping it simple to diagnostic support and impressing the user. While they far from guarantee a successful and stress free implementation, they at least put the developer on the right path.
Dead Reckoning in Sports and Strategy Games |
Abstract: Dead reckoning is a set of techniques used to calculate the motion of objects not entirely within an agent's control. This article explores the equations required to implement dead reckoning, and shows how it can apply in a variety of game contexts, for example the calculation of the optimal trajectory for a pass or a shot in a sports simulation, as well as multiple wargame problems.
Building a Sports AI Architecture |
Abstract: This article focuses on the sport of basketball; however, the concepts presented in the article are applicable to a wide variety of games. The goal of the article is to give the reader a solid understanding about the things to consider when designing an architecture for a sports game. The article also describes the concepts and critical components necessary to successfully design an AI system that is easy to understand, build, maintain and extend.
The article covers, in detail, the concepts of agent plans, team management, agent AI, and touches on the critical points of agent mechanics. The architecture presented in the article serves as the foundation for Microsoft's NBA Inside Drive franchise and has been used in three shipped versions of the game.
Section 9: Scripting
Optimized Script Execution |
Abstract: The slow speed with which script languages are executed (compared to native code) places many limitations on a script language's potential applications. Previously only infrequently executed code placed outside of the game's inner loops has been deemed suitable for scripting, and for this reason script languages have typically only been used for story telling or customizable event-handling purposes.
Using optimization techniques presented in this article, it possible to increase script execution efficiency to near-native performance levels, enabling the use of scripting in the game's core logic, or even in a high performance 3D rendering system. The flexibility gained from switching to script-based logic means that even modifying a program's innermost mechanics is trivial, and does not come with the performance penalties one would expect.
Three stages of script execution are individually examined, and optimizations for each are presented. The techniques and principles presented can be easily applied to any existing scripting engine.
Advanced Script Debugging |
Abstract: Poor or missing script debugging facilities are among the principal reasons for scripts not being fully exploited in a development environment. Often, errors encountered during script execution result in crashes of the game or a "screen of death" style representation of the virtual machine's internal state just after the crash has occured.
In-depth knowledge of the virtual machine is required to interpret such information, and often the virtual machine's source code needs to be examined in order to identify the problem, which may have been caused by a virtual machine command executed long before the crash. Because all external developers (including the mod community) and most in-house script programmers lack this in-depth information, they will restrict their programming style to simple constructs that can be fixed using a trial and error process in case of a problem. Therefore even the most powerful script languages are doomed to be misused if they do not support proper debugging mechanisms.
This article shows how to incorporate known debugging capabilities from common development environments into your script system, giving your script designers and the mod community the ability to create complex scripts and use the language to its full extent, while also shortening the development period because of improved debugging capabilities for scripts.
Adding Error Reporting to Scripting Languages |
Abstract: Custom scripting languages are a controversial game development tool. Scripting languages empower non-programmers by moving game AI logic out of the C++ code. While this empowerment certainly comes with some risks, the benefits are that additional team members can create behaviors, designers can tweak AI more directly, and the AI logic is more accessible to the mod community. The most common complaint about scripting languages is that they are difficult to debug. This concern is exacerbated if non-programmers intend to write scripts. If the scripting language compiler or interpreter only gives feedback like "syntax error," non-programmers are not going to get very far. Fortunately, this problem is easily solved. The same techniques used to define the grammar of valid syntax can be used to identify and report scripting errors in plain English. This article describes how to harness the power of Lex and Yacc to generate meaningful errors when compiling scripts. The article includes C++, Lex, and Yacc code for a simplistic language called Simple.
Empowering Designers: Defining Fuzzy Logic Behavior through Excel-Based Spreadsheets |
Abstract: Putting game development back into the hands of the game's designers is critical to keeping a project on schedule. How does that happen? What is the easiest way to let a game designer work on their own with a minimum amount of interaction from a technical source? Using Visual Basic for Applications and some basic applications, it is possible to design an interface which does both of these things, as well as having the added benefit of letting finished code stay finished.
A Modular Camera Architecture for Intelligent Control |
Abstract: Cameras play a vital role in the user experience of any game. A robust camera solution can make the difference between a game that is awkward to play and a game that plays smoothly and feels great. Unfortunately, cameras tend to be a low priority item in many game development schedules and the effort is limited to the point where the cameras stop being a nuisance. One of the reasons that the efforts stop early is the lack of a solid architecture that allows rapid, data driven experimentation with camera behaviors.
This article presents a component based camera architecture that allows non-programmers to take over the development of cameras at the point where they make the transition between technical coding and creative effort. The architecture will demonstrate the use of common AI techniques to enhance the robustness and creativity of the camera solution for any game. The techniques presented in the article will primarily benefit games that have a third-person perspective, but will also provide useful tips for other types of games.
Section 10: Learning
Player Modeling for Adaptive Games |
Abstract: This article describes a lightweight, flexible machine learning technique we call player modeling, designed to help add adaptivity to your game AI. The basic idea is simple: the game maintains a profile of each player that captures the skills, weaknesses, preferences, and other characteristics of that player. This model is updated by the game as it interacts with the player. In turn, the game AI can query the player model to determine how best to adapt its behavior to that particular player - for example, by asking which of several possible tactics will be most challenging to the player. Using player modeling, a game's AI can adapt both during the course of a single play as well as over multiple sessions, resulting in a computer opponent that changes and evolves with time to suit the player.
The article first defines the player model concept in more detail and then discusses strategies for designing a model to suit your game. It then presents a basic player model implementation. Subsequent sections describe how to actually integrate the modeling system with your game, including both how to update the model and how to make use of the information that it contains. The remainder of the article presents several advanced concepts, including a hierarchical player model, alternate model update methods, and other uses for the player model.
Constructing a Decision Tree Based on Past Experience |
Abstract: In recent years, decision trees have gained popularity within the game development community as a practical learning method that can help an AI adapt to a player. Instead of picking from a canned set of reactions to player action, the AI has the opportunity to do something much more powerful: anticipate the player's action before he acts. In this article, we discuss a decision tree learning algorithm called ID3, which constructs a decision tree that identifies the telltale features of an experience to predict its outcome. We then establish ID3's role in Black & White, building on an earlier article in the first edition of AI Game Programming Wisdom. Finally, we consider some important aspects and extensions to the approach, and provide s ample code which implements a simple form of ID3.
Understanding Pattern Recognition Methods |
Abstract: The task of pattern recognition is to abstract relevant information from the game world and, based on the retrieved information, construct concepts and deduce patterns for the use of higher level reasoning and decision-making systems. We view pattern recognition in computer games from two perspectives: functional and methodological. In the functional approach, we analyze what is required from pattern recognition. We conclude that it can act in different roles, which in turn affect the choice of a method and its implementation. These roles depend on the level of decision-making, the stance toward the player, and the use of the modeled knowledge. In the methodological approach, we review a branch of pattern recognition techniques arising from soft computing. We discuss methods related to optimization, adaptation, and uncertainty. Our intention is to clarify where these methods should be used.
Using Reinforcement Learning to Solve AI Control Problems |
Abstract: During the development of a game's AI many difficult and complex control problems often have to be solved. How should the control surfaces of an aircraft be adjusted so that it follows a particular path? How should a car steer to follow a racing line? What sequences of actions should a real time strategy AI perform to maximize its chances of winning? Reinforcement learning (RL) is an extremely powerful machine learning technique that allows a computer to discover its own solutions to these types problems by trial and error. This article assumes no prior knowledge of RL and introduces the fundamental principles of it by showing how it can be used to allow a computer to learn how to control a simulated racing car. C++ source code for RL and a skeleton implementation of racing game AI are included with the article.
Getting Around the Limits of Machine Learning |
Abstract: To some AI programmers, the Holy Grail of AI would be a game that learns in the field and gets better the more it is played. Multiplayer network games especially would become challenging to the most skillful players as the AI learns and uses the best plays from the best players. This article examines some of the limitations of machine learning and some of the ways around them. It analyzes learning in three current games. It considers technical and gameplay issues with learning in games.
How to Build Neural Networks for Games |
Abstract: Neural networks are a machine learning technique inspired by the human brain. They are a flexible technique that has a wide range of applications in a variety of industries. This article will first introduce neural networks, describing their biological inspiration. Then, it will describe the important components of neural networks and demonstrate how they can be implemented with example code. Next, it will explain how neural networks can be trained, both in-game and prior to shipping, and how a trained neural network can be used for decision-making, classification and prediction. Finally, it will discuss the various applications of neural networks in games, describing previous uses and giving ideas for future applications. Each of these sections will be illustrated with relevant game examples and sample code where appropriate.
How to Build Evolutionary Algorithms for Games |
Abstract: Evolutionary algorithm is the broad term given to the group of optimization and search algorithms that are based on evolution and natural selection, including genetic algorithms, evolutionary computation and evolutionary strategies. Evolutionary algorithms have many advantages, in that they are robust search methods for large, complex or poorly-understood search spaces and nonlinear problems. However, they also have many disadvantages, in that they are time-consuming to develop and resource intensive when in operation. This article will introduce evolutionary algorithms, describing what they are, how they work, and how they are developed and employed, illustrated with example code. Finally, the different applications of evolutionary algorithms in games will be discussed, including examples of possible applications in different types of games.
Adaptive AI: A Practical Example |
Abstract: Because most game AIs are either hared-coded or based on pre-defined scripts, players can quickly learn to anticipate how the AI will behave in certain situations. While the player will develop new strategies over time, the AI will always act as it did when the box was opened, suffering from strategic arrested development. This article describes the adaptive AI of a simple turn-based game called "Advanced Protection."
This practical example of an adaptive AI displays a number of advantages over a static AI. First, the system can dynamically switch between strategies depending on the actual performance of the player - experts will be treated like experts, and novices will be treated like novices. Next, the rules and parameters of the game will be exactly the same for all strategies, which means the AI will not need to "cheat" in order to challenge expert players. Finally, the system can ensure that the AI's "best" strategies truly are the best for each individual player.
Building Better Genetic Algorithms |
Abstract: Genetic algorithms are slowly but surely gaining popularity with game developers. Mostly as an in-house tool for tweaking NPC parameters such as ID used in the development of the bots for Quake3, but we are also beginning to see genetic algorithms used in-game, either as an integral part of the gameplay or as an aid for the user.
Unfortunately, many of today's programmers only know the basics of genetic algorithms, not much beyond the original paradigm devised by John Holland back in the mid sixties. This article will bring them up to date with some of the tools available to give improved performance. Techniques discussed will include various scaling techniques, speciation, fitness sharing, and other tips designed to help speedy convergence whilst retaining population diversity. In short, showing you how to get the most from your genetic algorithms.
Advanced Genetic Programming: New Lessons From Biology |
Abstract: Genetic programming is a powerful evolutionary mechanism used to create near-optimal solutions to difficult problems. One of the major issues with traditional GP paradigms has been the relative brittleness of the organisms generated by the process: many source code organisms do not compile at all, or produce other kinds of nonsensical results. Recent advances in genetic programming, namely the grammatical evolution scheme based on such biological concepts as degenerate and cyclical DNA and gene polymorphism, promise ways to eliminate this problem and create programs that converge on a solution faster. This article explains grammatical evolution, its biological underpinnings, and a handful of other ways to refine evolutionary computing schemes, like co-evolution
The Importance of Growth in Genetic Algorithms |
Abstract: The purpose of this article is to introduce some newer concepts relating to the field of Genetic Algorithms (GA). GAs can introduce variability and adaptability into a game leading to non-linear gameplay and opponents who tailor their strategies to that of the player. Many limitations of mainstream GA implementations can be overcome with some simple additions. Using growth, co-evolution, speciation and other new techniques can alleviate limitations on complexity, designer bias, premature convergence and many more handicaps. These additions can reduce the disadvantages of current GAs and allow the advantages to make games much more unpredictable and challenging.
Section 11: Speech Recognition and Dialogue
SAPI: An Introduction to Speech Recognition |
Abstract: This article looks at providing newcomers to SAPI an easy-to-follow breakdown of how to get a simple SAPI application working. It looks briefly at setting up SAPI, how to construct the XML grammar files, handling SAPI messages and using the SAPI text-to-speech functionality. All these concepts are tied together using an demonstration application designed to make learning SAPI simple yet entertaining.
SAPI: Extending the Basics |
Abstract: This article extends upon the previous one by discussing concepts like dynamic grammar, additional XML grammar tags, altering voices and more SAPI events. The chapter uses a simple implementation of Go Fish! to demonstrate the concepts presented.
Conversational Agents: Creating Natural Dialogue between Players and Non-Player Characters |
Abstract: The quality of interactions between non-player characters (NPCs) and the player is an important area of Artificial Intelligence in games that is still in need of improvement. Game players frequently express that they want to see opponents and NPCs that appear to possess intelligence in games. However, most dialogue between players and NPCs in computer games is currently scripted, which does not add to the appearance of intelligence in the NPC. This article addresses these problems by giving an overview of NPCs in current games and presents a method called conversational agents, for improving dialogue between players and NPCs. Conversational agents are software agents that consist of models of personality and emotion, which allow them to demonstrate believable conversational behavior. The advantages of conversational agents include their ability to portray emotions and personality through dialogue. However, they also have disadvantage, in that they can be time consuming to develop.
This article will begin by discussing the conversational behavior of NPCs in current games. We will not be looking at the artificial intelligence (AI) capabilities of NPCs, only their ability to interact with the player. We will then discuss the components of a conversational agent - how to give it the appearance of personality and emotion. We will also look at the input that the agent needs to get from the environment, and what we want the agent to say to the player. We will conclude with the advantages and disadvantages of using conversational agents in games.
|
