|
Artificial Intelligence: State Machines
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.
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.
Implementation Walkthrough of a Homegrown "Abstract State Machine" Style System in a Commercial Sports Game |
Abstract: When I began working at Sony Computer Entertainment of America in 2002, the AI system they were using was very dated. Over the next few years, I designed and developed an almost completely data driven system that has proven to be very powerful, extremely extensible, and designer friendly. This system uses a homegrown data structure, the use of which in many ways resembles the software method of using Abstract State Machines for decomposing complex logical constructs iteratively. This paper will provide an overview of the construction and usage of the system, as well as the pros and cons of this type of game AI engine.
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).
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.
Constructing a Goal-Oriented Robot for Unreal Tournament Using Fuzzy Sensors, Finite-State Machines, and Behavior Networks |
Large-Scale Stack-Based State Machines |
Visual Design of State Machines |
Practical Application of Parallel-State Machines in a Client-Server Environment |
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.
Parallel-State Machines for Believable Characters |
Designing a GUI Tool to Aid in the Development of Finite State Machines |
Implementing a State Machine Language |
Abstract: This article presents a robust way to structure your state machines with a simple language. This State Machine Language will not only provide structure, but it will unleash some powerful concepts that will make programming games much easier. While the language itself is simple, it embodies some very important software engineering principles such as simplicity, maintainability, robustness, and ease of debuggine. The following article, "Enhancing a State Machine Language through Messaging," expands on this language with a powerful communication technique using messages. Each article has full soure code on the accompanying CD-ROM.
Enhancing a State Machine Language through Messaging |
Abstract: The previous article, "Implementing a State Machine Language," set the groundwork for a powerful language that can structure state machines in a simple, readable, and very debuggable format. In this article, that language will be expanded to encompass the problem of communication between AI game objects. This communication technique will revolutionize the State Machine Language by allowing complicated control flow and timers. Full source code is included on the accompanying CD-ROM.
Function Pointer-Based, Embedded Finite-State Machines |
A Generic Fuzzy State Machine in C++ |
Abstract: Fuzzy Logic provides an attractive alternative to more crisp forms of finite state decision making. This article builds on the presentation of the Finite-State Machine class from the first Game Programming Gems book, by introducing a generic Fuzzy-State Machine class in C++. The concepts of fuzzy logic are presented and an example of applicability for computer game AI is offered. The FSMclass and FSMstate classes from the first GEMS book are converted into fuzzy logic versions, and source code is provided for review.
Designing A General Robust AI Engine |
A Finite-State Machine Class |
Abstract: Simple Finite-State Machines are powerful tools used in many computer game AI implementations. This article introduces a generic C++ class that implements a Finite-State Machine that is useful to the novice for learning about Finite-State Machines and as a building block for more complex AI implementations in development projects. The processes of a Finite-State Machine are presented, an example game implementation is offered as an example of Finite-State Machine usage, and source code illustrates how finite-state functionality can be implemented in a generic manner.
|
