Artificial Intelligence: Architecture
A Flexible AI Architecture for Production and Prototyping of Games |
Abstract: This article describes an architecture that is well suited for production or prototyping of a wide variety of games. The goal of the article is to give the reader a solid understanding of the factors to consider when designing a flexible AI architecture and focuses on 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 the architecture, decision making process, decision weighting, decision chaining, agent coordination and cooperation, as well as handling special cases.
Embracing Declarative AI with a Goal-Based Approach |
Abstract: The vast majority of computer games developed today use either scripting or FSMs for their high-level AI architecture. While these are both powerful techniques, they are what one might think of as "procedural AI," which leaves the bulk of the decision-making in the hands of the developer. Goal-based AI is an alternative architecture that has been used in a number of successful games across multiple genres. In contrast to the techniques listed above, one might think of it as "declarative AI." Rather than telling the AI what to do, the role of the developer is to tell the AI what factors to consider when selecting an action and how to weigh them. Using this information, the AI will examine the current situation and select its actions accordingly. This paper briefly discusses the most common procedural AI architectures, followed by one popular declarative alternative, goal-based AI. Finally, we will discuss hybrid approaches where we can capture some of the best of both worlds.
The MARPO Methodology: Planning and Orders | |
Abstract: This paper elaborates on a previously eluded to AI design paradigm, nicknamed MARPO, that continues to produce flexible and manageable AI from first principles. It applies the rationales behind these principles to create a goal-based, hierarchical state machine that embraces the beauty of rule-based reasoning systems. Grounded in industry experience, it avoids the common pitfalls of this approach, and shows how MARPO discipline maximizes efficiency, flexibility, manageability and successfulness of the end result.
Getting Started with Decision Making and Control Systems |
Abstract: A robust decision-making and control system is the best place to start with any AI engine. The behavior tree described in this article covers the major elements: implementing low-level tasks with latent execution, building a framework for managing them concurrently, assembling them in hierarchies using standard composites, and designing the system for depth-first search.
Knowledge-Based Behavior System: A Decision Tree/Finite State Machine Hybrid | |
Abstract: In the modern role-playing game (RPG) development environment, designing and implementing a behavior system that meets the diverse needs of designers and programmers can be a challenge. The article will first identify the requirements of a desirable behavior decision system from the points of view of designers and programmers. It will then introduce a knowledge-based approach stemming from the decision tree and finite-state machine methods, which meets the requirements of a desirable decision making system. Through an actual AI example where the three methods are applied, the article will illustrate their strengths and weaknesses, hence demonstrating the value of the knowledge-based approach.
The Emotion Component: Giving Characters Emotions | |
Abstract: In this article we discuss an "Emotion Component" that can be used to model complex emotions, allowing you to implement more human-like behavior in game characters. The Emotion Component is set to function either as a separate unit or in conjunction with other AI processes. With this component the emotions in a game character influence its behavior and color its perception of the world. Game characters using the Emotion Component internally keep track of ("feel") a condition ("emotional state") that influences their behavior and reactions in such a way that the human player is persuaded that the character is experiencing emotions such as fear, anger, admiration, love, and greed.
Generic Perception System |
Abstract: The perception system described in this article presents a way to simplify AI logic and expand the capabilities of NPCs by providing prioritized information about the environment as well as tactical data. The system has been designed to enable time slicing, priority scanning, goal negotiation, short- and long-term memory, and simulation of reflex times, among other features. This system can also be scaled to reduce the performance impact of a high number of agents interacting in the world and to incorporate new complex objects with attached goals and scripts, which make it very suitable for implementing complex character behaviors in current and next-generation games.
Peer-To-Peer Distributed Agent Processing |
Abstract: This article covers techniques for distributing agent processing in peer-to-peer (P2P) games. It discusses mechanisms to distribute processing to address both functional concerns (such as for streaming games) and performance concerns (distributing processing load). It also considers efficient communication mechanisms for agents running on separate machines to coordinate behavior and serialization of AI state for transferring ownership between peers.
AI Architectures for Multiprocessor Machines | |
Abstract: The proliferation of consoles with multiple cores means that games must now be threaded to run on these architectures. This changes the overall architecture for a game, but how can AI best be threaded? Options range from splitting the AI into individuals that run on different processing units to the more traditional planning system that has been functionally decomposed. Hybrid approaches such as a blackboard system are also possible and must be considered within the framework of a whole game system.
Level Up for Finite State Machines: An Interpreter for Statecharts | |
Abstract: Finite state machines have become the norm for game intelligence, be it to control the behavior of a non-player character or to formalize the game's rules. However, in practice they have a number of shortcomings that lead, for instance, to an explosion in the number of states or transitions. To solve many such issues, one can generalize finite state machines to statecharts, a notion introduced by David Harel in 1987. This chapter describes how statecharts overcome many of the limits of finite state machines, for instance by supporting nested states, parallel states, and continuous activities. The chapter focuses on the practical issues of building a statechart interpreter and integrating it with existing code. Two reference implementations are provided: first, a lean version in C++, ready to be added to your own game code; and second, a full-fledged demonstration in C# including a graphical statechart editor and debugger with automatic layout.
Building a Behavior Editor for Abstract State Machines | |
Abstract: This chapter describes the workflow and data structures used for scripting behaviors in the Abstract State Machine (ASM) framework. ASMs are introduced in the context of a behavior system for game agents. The focus of the paper is on how object-oriented extensions to ASM, Command Port integration of the Behavior Editor with Autodesk Maya, and a dual XML file format contribute to the usability of the behavior editor. The chapter also describes how offline manipulation of ASM definitions enabled the addition of parameters and referencing for behaviors without modifying the run-time code of the AI system.
Multi-Axial Dynamic Threshold Fuzzy Decision Algorithm | |
Abstract: The Multi-axial Dynamic Threshold Fuzzy Decision Algorithm (MADTFDA) allows the designer to combine two or more constantly changing values and then compare the result to a defined numerical threshold in order to make a decision. MADTFDA is designed as a more flexible replacement for the "weighted sum" approach to combining factors. The additional flexibility is a valuable tool, allowing the designer to easily visualize the interactions of the decision inputs and enabling the programmer to create quick, robust, parameterized decision calls that accurately reflect the needs of the designer. The article covers the concept behind MADTFDA, its various uses as an AI design tool, and the use of the code that is included on the CD-ROM.
An Advanced Motivation-Driven Planning Architecture |
Abstract: As game AI complexity increases, imperative techniques such as Finite State Machines become unmanageable, inflexible, and problematical for code maintenance. Planning architectures tackle with this complexity introducing a new decision making paradigm. This article describes a new hierarchical planning technique based on STRIPS, GOAP, and HTN. It features a motivational approach together with the capability to handle parallel goal planning which favors the appearance of emergent behaviors. Advanced characteristics include, among others, partial replanning or mixing of planning and execution with the use of parameters at planning time to represent the current world state. The architecture, used in the strategy game War Leaders: Clash of Nations, allows high levels of code reusability and modularity, being easily adaptable to game design changes that commonly arise during a complete game development.
Command Hierarchies Using Goal-Oriented Action Planning | |
Abstract: Goal-based AI agent architectures are a popular choice in character-driven games because of the apparent intelligence the agents display in deciding how to pursue their goals. These games often also demand coordinated behavior between the members of a group, which introduces some complexity in resolving the autonomous behavior of the individuals with the goal of the collective. This article introduces a technique for integrating military-style command hierarchies with the Goal-Oriented Action Planning (GOAP) architecture. An UnrealScript-based example of the framework is used to illustrate the concepts in practice for a squad-based first-person shooter (FPS), and practical optimizations are suggested to help the technique scale to the larger numbers of units required for real-time strategy (RTS) games.
Practical Logic-Based Planning | |
Abstract: An efficient, easy-to-implement planner is presented based on the principles of logic programming. The planner relies on familiar IF/THEN structures and constructs plans efficiently, but it is not as expressive as other proposed planners. Many easy extensions to the planner are discussed such as inserting and removing rules dynamically, supporting continuous values, adding negations, and finding the shortest plan. Accompanying source code provides easy-to-follow implementations of the planner and the proposed extensions.
Simulation-Based Planning in RTS Games | |
Abstract: Sophisticated cognitive processes such as planning, learning, and opponent modeling are still the exception in modern video game AI systems. However, with the advent of multi-core computer architectures and more available memory, using more computing intensive techniques will become possible. In this paper we present the adversarial real-time planning algorithm RTSplan which is based on rapid game simulations. Starting with a set of scripted strategies RTSplan simulates determines the outcome of playing strategy pairs and uses the obtained result matrix to assign probabilities to strategies to be followed next. RTSplan is constantly replanning and therefore able to adjust to changes promptly. With an opponent modeling extension, RTSplan is able to soundly defeat individual strategies in our army deployment application. In addition, RTSplan can make use of existing AI scripts to create more challenging AI systems. Therefore it is well-suited for video games.
A Goal Stack-Based Architecture for RTS AI |
Abstract: An RTS game may have dozens or hundreds of individual units. This presents some interesting challenges for the AI system. One approach to managing this complexity is to make decisions on different abstraction levels. The AI for the RTS part of the game War Leaders: Clash of Nations is divided in three levels. This article is focused on the architecture developed for the lower two of these three levels, which correspond to the AI levels for units, groups, and formations. This architecture is based on the concept of a goal stack as a mechanism to drive the entire agent behavior together with orders, events, and behaviors.
Declarative AI Design for GamesConsiderations for MMOGs |
Abstract: The design of behaviors in games and massively multiplayer online games (MMOGs) is based on a style of scripting that is consistent with a cinematic perspective of game design. This style is paradigmatic of how AI is conceptualized in games. This article claims that this approach is not likely to scale in the future and calls for a more declarative style of developing and conceptualizing AI. The objective of this article is to acquaint games AI developers with thoughts and techniques that form a declarative AI design.
Abstract: As gamers demand more realistic AI and more dynamic, non-linear, and interactive game worlds, traditional methods of developing AI are beginning to show their limitations in terms of salability, robustness and general fitness for purpose. Emergence and the broader "emergent approach" to game design hold great potential as an efficient tool for avoiding these limitations by allowing high-level behaviors and flexible game environments to emerge from low level building blocks without the need for any hard-coded or scripted behaviors. Our goals in this article are to both demonstrate this case, and to explain in practical terms how emergence can be captured by the game designer.
Strategies for Multi-Processor AI |
Abstract: With multi-processor hardware becoming commonplace, it is necessary to develop a new architecture that allows the AI engine to execute in parallel in multiple threads. We describe several approaches that try to minimize dependencies and avoid locking, in order to build an efficient concurrent system, while keeping productivity high and preventing threading bugs.
Insect AI 2: Implementation Strategies |
Abstract: The integration of AI into a game engine where the agent is simulated and run under physical control can be a challenge. The AI's internal model of the world is likely to be very simple relative to the complexity of the game world, yet the AI has to function in a reasonable and efficient manner. This article shows how to usefully integrate Insect AI into systems where the physics, collision, and animation systems are black boxes not directly under AI control, and are not even directly accessible by the AI. It also discusses practicalities of implementation including integration with pre-existing AI algorithms in a game engine.
Flexible Object-Composition Architecture |
Abstract: Object-composition architectures provide an easy way to assemble game objects as a collection of components, each of them with a specific and modular function. Archetypes are used to define what components an object consist of, and therefore what objects do. Archetype definition is data-driven, empowering designers to experiment with gameplay. The last ingredient in the mix is good tools, which might take advantage of data inheritance to increase productivity.
A Goal-Based, Multi-Tasking Agent Architecture |
Abstract: This article describes a goal-based, multi-tasking agent architecture for computer game characters. It includes some mechanisms for representing and requesting information about the game world, as well as a method for selecting a set of compatible goals to execute based on the availability of necessary items. Finally, the article includes a brief discussion of techniques for designing and debugging goal-based systems.
Abstract: The article explores a methodology for building game AI based on subsumption, command hierarchy, messaging and finite state machines. The approach is derived from a metaphor of bureaucratic dictatorship. This metaphor helps in the analysis and practical design of particular AI subsystems on both the individual and group layers. The resulting architecture is called an Orwellian State Machine (OSM).
A Flexible AI System through Behavior Compositing |
Abstract: This article proposes a new way of defining AI states as modular behaviors, so code can be reused between NPCs with a minimal amount of effort. With this system, state transitions are not explicitly recorded in a table like many finite state machine implementations. Every behavior has a "runnable" condition and a priority, so the state transitions are determined by checking these conditions in sorted order. Common issues that arise with this implementation are addressed including performance, ease of refactoring, and interdependencies.
Abstract: We present a generic AI architecture for implementing the behavior of game agents. All levels of behavior, from tactical maneuvers to path-following and steering, are implemented as goals. Each goal can set up one or more subgoals to achieve its aim, so that a tree structure is formed with the primary goal of the agent at its root. Potential primary goals are experts on when they should be selected, and scripts can also force behavior at any level by providing a sequence of primary goals. The architecture is more robust than a finite state machine (FSM) and more efficient than a full planning system.
A Unified Architecture for Goal Planning and Navigation |
Abstract: Graph networks, traversed by standard algorithms such as A*, are the staple of most pathfinding systems. The formalization of navigation algorithms into a search graph that represents spatial positioning is one of the most effective ideas in game AI. However ubiquitous graph networks may be in pathfinding, their use in more general problem domains in modern games seems to be less common. Couldn't we extend the standard pathfinding arsenalgraph networks and A*to other problem sets? This is the idea that we will be exploring in this article.
Prioritizing Actions in a Goal-Based RTS AI |
Abstract: In this article we outline the architecture of our strategic AI and discuss a variety of techniques that we used to generate priorities for its goals. This engine provided the opposing player AI of our real-time strategy games Kohan 2: Kings of War and Axis & Allies. The architecture is easily extensible, flexible enough to be used in a variety of different types of games, and sufficiently powerful to provide a good challenge for an average player on a random, unexplored map without unfair advantages.
Extending Simple Weighted-Sum Systems |
Abstract: Decision-making is an important function of every AI engine. One popular technique involves calculating a weighted sum, which combines a number of factors into a desirability value for each option, and then selecting the option with the highest score. Some extensions, such as the incorporation of behavioral inertia, the use of response curves, or the combination of the system with a rule-based engine, can turn the weighted sum into a very robust, flexible approach for controlling behavior.
AI Waterfall: Populating Large Worlds Using Limited Resources |
Abstract: This article presents an architecture that simplifies the process of populating large worlds with interesting and varied actors using a relatively small number of AI agents. The architecture derives its concept from faux waterfalls that recycle the same water to create the illusion of continuous flow. The architecture can be broken down into two distinct parts: a director class that moves the actors around the stage and provides them with a script for the role they play, and a set of game-specific actors that play the part they are assigned until they are asked to go back in the wings for a costume change. One section of the article is dedicated to optimization techniques for the architecture. The code for the underlying architecture is included with the article.
An Introduction to Behavior-Based Systems for Games |
Abstract: Behavior-based systems are an efficient way of controlling NPCs in video games. By taking advantage of simpler propositional logic, these systems are able reason efficiently and react quickly to changes in the environment. The developer builds the AI system one behavior layer at a time, and then aggregates the results of all the behaviors into a final output value using resolution system. The resulting systems are equivalent to finite state machines, but are not constructed in the traditional state-transition manner. The resulting behavior-based system can often be mostly stateless, hence avoiding most of the messy state transitions that need to be built into FSMs to handle various contingencies.
Abstract: The article describes a methodology of supplementing traditional FSMs with contextual information about the internal state of the agent and the environment that the agent is in, by defining game events and deriving rules for responses to a given game event. This creates a completely non-scripted experience that varies with every different player, because in essence the system responds to game events generated by the player himself. By defining simple rules for enemy behavior and environments in which those rules can be clearly seen, it is possible to simulate group behavior where no underlying code for it is present. The system described is completely deterministic, thus easy to maintain, QA, and debug. It is also not computationally expensive, so rather large populations of AI agents can be simulated using the proposed system.
A Combat Flight Simulation AI Framework |
Abstract: This article covers the AI framework requirements specific to an air combat based flight simulation. It explains the general AI framework that should already be in place before continuing on to describe the air combat flight simulation specific data structures, algorithms and requirements that need to be in place to deliver a playable AI opponent for such simulations.
Using STL and Patterns for Game AI | |
Abstract: Game AI programmers are notorious for reinventing the wheel. But many of the data structures, algorithms and architectures they need have already been done in flexible and reusable ways. This article is intended to serve as a reference for a variety of patterns. While entire volumes have been written to discuss the STL and design patterns in general, this article will provide an introductory overview of the STL and inspect those specific design patterns that have proven the most useful in game AI development. We need to talk about the STL because it provides a series of pre-defined data structures that will not only make life simpler, but which take much of the burden of nuts and bolts implementation away and allow the AI developer to focus on what's really interesting anywaythe AI.
Declarative AI Design for GamesConsiderations for MMOGs |
Abstract: The design of behaviors in games and massively multiplayer online games (MMOGs) is based on a style of scripting that is consistent with a cinematic perspective of game design. This style is paradigmatic of how AI is conceptualized in games. This article claims that this approach is not likely to scale in the future and calls for a more declarative style of developing and conceptualizing AI. The objective of this article is to acquaint games AI developers with thoughts and techniques that form a declarative AI design.
Applying Model-Based Decision-Making Methods to Games: Applying the Locust AI Engine to Quake III |
Behavior-Based Robotic Architectures for Games |
Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Behavior Networks |
A Goal-Oriented Unreal Bot: Building a Game Agent with Goal-Oriented Behavior and Simple Personality Using Extended Behavior Networks |
Designing a Multilayer, Pluggable AI Engine |
A Fuzzy-Control Approach to Managing Scene Complexity |
Parallel AI Development with PVM |
NPC Decision Making: Dealing with Randomness |
An Object-Oriented Utility-Based Decision Architecture |
A Distributed-Reasoning Voting Architecture |
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.
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 |
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.
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 |
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 |
A Extensible Trigger System for AI Agents, Objects, and Quests |
Managing AI with Micro-Threads |
Micro-Threads for Game Object AI |
Abstract: Presents code and concepts to create hundreds of low-overhead threads by manipulating the stack. This technique has notable benefits in terms of AI load balancing and the author has implemented the architecture on systems ranging from the PC to the GameBoy.
An Architecture for RTS Command Queuing |
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.
Designing A General Robust AI Engine |
|