Home    General Programming    Artificial Intelligence    Math    Physics    Graphics    Networking    Audio Programming   
Audio/Visual Design    Game Design    Production    Business of Games    Game Studies    Conferences    Schools    Contact   
State of the Industry
Architecture
State Machines
Learning
Scripting
A* pathfinding
Pathfinding / Movement
Group Movement
Group Cooperation
Strategy / Tactical
Animation Control
Camera Control
Randomness
Player Prediction
Fuzzy Logic
Neural Nets
Genetic Algorithms
Natural Language
Tips and Advice
Tools and Libraries
Genre: RTS / Strategy
Genre: RPG / Adventure
Genre: FPS / Action
Genre: Racing
Genre: Sports
Genre: Board Games
Middleware
Open Source
All Articles
Game Programming Gems
Game Programming Gems 2
Game Programming Gems 3
Game Programming Gems 4
Game Programming Gems 5
Game Programming Gems 6
Game Programming Gems 7
AI Game Programming Wisdom
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4
AI Summit GDC 2009
GPU Gems
GPU Gems 2
GPU Gems 3
ShaderX
ShaderX2
ShaderX3
ShaderX4
ShaderX5
Massively Multiplayer Game Development
Massively Multiplayer Game Development 2
Secrets of the Game Business
Introduction to Game Development
GDC Proceedings
Game Developer Magazine
Gamasutra


Artificial Intelligence: State Machines


Knowledge-Based Behavior System: A Decision Tree/Finite State Machine Hybrid

Nachi Lau (LucasArts)
AI Game Programming Wisdom 4, 2008.
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

Philipp Kolhoff (KING Art), J�rn Loviscach (Hochschule Bremen)
AI Game Programming Wisdom 4, 2008.
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

Igor Borovikov (FrameFree Technologies), Aleksey Kadukin (Electronic Arts)
AI Game Programming Wisdom 4, 2008.
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

Brian Schwab (Sony Computer Entertainment of America)
PDF link, Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2008.
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.

Orwellian State Machines

Igor Borovikov (Sony Computer Entertainment America)
AI Game Programming Wisdom 3, 2006.
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).

Simulating a Plan

Petar Kotevski (Genuine Games)
AI Game Programming Wisdom 3, 2006.
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

Hugo Pinto and Luis Otavio Alvares
Game Programming Gems 6, 2006.

Large-Scale Stack-Based State Machines

James Boer
Game Programming Gems 5, 2005.

Visual Design of State Machines

Scott Jacobs
Game Programming Gems 5, 2005.

Practical Application of Parallel-State Machines in a Client-Server Environment

Jay Lee, (NCsoft Corporation)
Game Programming Gems 4, 2004.

The Ultimate Guide to FSMs in Games

Ryan Houlette, Dan Fu (Stottler Henke Associates, Inc.)
AI Game Programming Wisdom 2, 2003.
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

Paul Tozour (Retro Studios)
AI Game Programming Wisdom 2, 2003.
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

Gilberto Rosado (DigiPen Institute of Technology)
AI Game Programming Wisdom 2, 2003.
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

Eric Yiskis (Sammy Studios)
AI Game Programming Wisdom 2, 2003.
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

Thor Alexander (Hard Coded Games)
Massively Multiplayer Game Development, 2003.

Designing a GUI Tool to Aid in the Development of Finite State Machines

Phil Carlisle (Team17 Software)
AI Game Programming Wisdom, 2002.

Implementing a State Machine Language

Steve Rabin (Nintendo of America)
AI Game Programming Wisdom, 2002.
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

Steve Rabin (Nintendo of America)
AI Game Programming Wisdom, 2002.
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

Charles Farris (VR1 Entertainment)
Game Programming Gems 3, 2002.

A Generic Fuzzy State Machine in C++

Eric Dybsand (Glacier Edge Technology)
Game Programming Gems 2, 2001.
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

Steve Rabin (Nintendo of America Inc)
Game Programming Gems, 2000.

A Finite-State Machine Class

Eric Dybsand (Glacier Edge Technology)
Game Programming Gems, 2000.
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.

40% off discount
"Latest from a must have series"
Game
Programming
Gems 7



"Cutting-edge graphics techniques"
GPU Gems 3


"Newest AI techniques from commercial games"
AI Game
Programming
Wisdom 4




Home