|
|
|
|
Each article details implementations from a specific game.
|
 | |
Jumping, Climbing, and Tactical Reasoning: How to Get More Out of a Navigation System
Topics: Movement, Pathfinding; Genres: General
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.
|
 | |
Constraining Autonomous Character Behavior with Human Concepts
Topics: General; Genres: General, FPS
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
Topics: Strategy, Tactical, Coordinated Movement, Cooperation; Genres: FPS, Action
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."
|
 | |
A Flexible Tagging System for AI Resource Selection
Topics: Architecture, NLP; Genres: General
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.
|
| |
Using a Spatial Database for Runtime Spatial Analysis
Topics: Architecture; Genres: FPS
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.
|
 | |
Simplified Animation Selection
Topics: Animation; Genres: General
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.
|
| |
Pluggable Animations
Topics: Animation; Genres: General
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
Topics: Animation; Genres: General
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.
|
 | |
Finite-State Machine Scripting Language for Designers |  |
Topics: State Machines, Scripting; Genres: General
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.
|
| |
A Subsumption Architecture For Character-Based Games
Topics: Architecture; Genres: Action
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.
|
 | |
Minimizing Agent Processing in Conflict Desert Storm
Topics: Architecture; Genres: General
Abstract:
|
 | |
Performing Qualitative Terrain Analysis in Master of Orion 3 | |
Topics: Strategy, Tactical, Terrain Analysis; Genres: Strategy, RTS
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
Topics: Strategy, Tactical; Genres: Strategy
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
Topics: Strategy; Genres: Strategy, RTS
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
Topics: Strategy, Tactical; Genres: Strategy, RTS
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.
|
 | |
Building a Sports AI Architecture
Topics: General; Genres: Sports, Basketball
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.
|
| |
Adding Error Reporting to Scripting Languages | |
Topics: Scripting; Genres: General
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 | |
Topics: Scripting, Fuzzy Logic; Genres: Sports, Baseball
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 | |
Topics: Scripting, Camera; Genres: General
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.
|
| |
Terrain Analysis in an RTS-The Hidden Giant
Topics: Tactical; Genres: RTS
Abstract:
|
| |
Building an AI Diagnostic Toolset
Topics: General, Tools; Genres: General
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.
|
| |
Building a Near-Optimal Navigation Mesh
Topics: Pathfinding; Genres: General
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.
|
| |
Introduction to Bayesian Networks and Reasoning Under Uncertainty
Topics: Architecture, Bayesian Networks; Genres: General
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.
|
| |
First-Person Shooter AI Architecture
Topics: Architecture; Genres: FPS, Action
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.
|
| |
A General Purpose Trigger System | |
Topics: Architecture, Trigger System; Genres: General
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.
|
| |
Generic A* Pathfinding
Topics: A* Pathfinding; Genres: General
Abstract:
|
| |
Pathfinding Design Architecture
Topics: A*, Pathfinding; Genres: General
Abstract:
|
| |
How to Achieve Lightning Fast A*
Topics: A* Pathfinding; Genres: General
Abstract:
|
 | |
Simple Swarms as an Alternative to Flocking
Topics: Flocking, Movement; Genres: General
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.
|
| |
Formations
Topics: Formations, Coordinated Movement; Genres: RPS, RTS, FPS, Action
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.
|
| |
Architecting an RTS AI
Topics: Architecture; Genres: RTS
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.
|
 | |
The Basics of Ranged Weapon Combat
Topics: Weapon Selection, Weapon Handling; Genres: RTS, RPG, FPS, Action
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
Topics: Level-of-Detail AI, LOD AI, Optimizations; Genres: RPG
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.
|
 | |
Representing a Race Track for the AI
Topics: Driving; Genres: Racing
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.
|
| |
Racing AI Logic
Topics: Driving; Genres: Racing
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.
|
| |
Training an AI to Race
Topics: Driving, Learning; Genres: Racing
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
Topics: Driving; Genres: Racing
Abstract:
|
 | |
Camera AI for Replays
Topics: Camera AI, Replay AI; Genres: Racing, Sports
Abstract:
|
 | |
Agent Cooperation in FSMs for Baseball
Topics: FSM, State Machines, Cooperation; Genres: Baseball, Sports
Abstract:
|
 | |
Scripting for Undefined Circumstances
Topics: Scripting; Genres: General
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.
|
| |
How Not To Implement a Basic Scripting Language
Topics: Scripting; Genres: General
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.
|
| |
Varieties of Learning
Topics: Learning; Genres: General
Abstract:
|
| |
Practical Natural Language Learning
Topics: Learning, NLP; Genres: General
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
Topics: Learning, Testing; Genres: General
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.
|
 | |
An Architecture for RTS Command Queuing
Topics: Movement; Genres: RTS
Abstract: Explains the concept of Command Queuing in an RTS along with several ways to implement it. Command Queuing is the idea that the player should be able to queue up any sequence of command orders (Move, Attack, Patrol, Repair, etc) for a particular unit. Some commands that cycle, such as Patrol, present specific challanges in order to acheive the right behavior. Solutions to these difficulties are discussed along with detailed diagrams.
|
|
|
|
