Finite State Machine

Ever since it was first announced, the game S.T.A.L.K.E.R. has captured the imagination of avid gamers fascinated by the idea of a massive world populated by an A-Life system. The game also piqued the interest of AI developers here at AiGameDev.com, making it into the finalists for best AI and runner up for technical […]

This article looks into the publicly available SDK for Half-Life 1, analyzing the various aspects of the AI such as the task scheduling system, its state-machine like implementation, and the sensory system. Even ten years later, looking into the codebase of this critically acclaimed game is a great way to learn about designing simple but effective AI systems.

Over the last few months, AiGameDev.com has grown into a wonderful little community thanks to you guys! On Fridays, I take the time to answer your questions, either from the blog or the increasingly busy forums.
Finite state machines have become extremely popular over the last decade, and helped game developers build some pretty […]

This Saturday in the build-up to the festive shopping season, there’s an avalanche of interesting Smart Links about game development and artificial intelligence! Feel free to contact me if you have any news or tips for next week.
Remember there’s a mini-blog (RSS) which gets updated with game AI news from the web as […]

Quite a few people asked for a PDF of my slides from my lecture at the GDC in Lyon, but I promised to do better and release a video with the animations an the whole audio. Here is the first part of the talk; it’s exactly 22:37 minutes long.

In the video, I go […]

Next-gen animation is proving to be quite a challenge to integrate with AI! This article takes a detailed look at the kind of technology that’s used in CryEngine 2 for AI and animation. It also analyze exactly why it’s so difficult to get it working in game generally — not just for Crytek.

Planners have a reputation for being hard to debug. Even once you have your core algorithm fully tested, it’s often time-consuming to figure out exactly how new situations cause the planner to generate a particular solution. It’s often like the protagonist in Memento, never being able to make new memories and having to replan from scratch every few seconds.

Thursdays at AiGameDev.com is dedicated to the theory behind game AI. Since the Lyon GDC 2007 has just finished, what better opportunity than to go through some of the research sessions relating to artificial intelligence. I’ll start off with the sessions I attended while I gather more details about the others…

Photo 1: […]

There’s one piece of technology you’re certain to find in most software: a finite state machine. However, they’re almost always implemented differently! In games, there are three major ways to implement FSM in the context of AI, logic, or animation. Naturally, each approach has its own benefits.
This week’s question comes from […]

When it comes to building powerful decision-making and control systems, robotics research is the best place to turn to for decades of experience. Many of the popular ideas in game AI today can be traced back to robotics controllers. In particular, PRS provides design methodologies and tricks for building behaviors that are responsive and purposeful.

Sundays at AiGameDev.com is dedicated to explaining problems visually using sketches. This article extrapolates from last week’s discussion (thanks Sergio) and explains different ways of looking at hierarchies.
Most developers say they use a “HFSM” in their games. But you’ll be surprised how different their technology can be — despite them using the […]

In last week’s sketches, you saw two different ways to implement simple suspicious behaviors for an action game. This Sunday you’ll see how well these two systems handle an additional attack behavior.

In last week’s sketches about game AI, you learned how to create behaviors by dealing with parts of the problem space at a time. This Sunday’s sketches shows how two different AI techniques solve the same in-game scenario.
What’s the Challenge?
“Implement the suspicious behavior of an immobile soldier. The soldier should respond to unexpected […]

In the previous sketches, you learned what a behavior lookup table looks like in practice, and how it can grow very quickly in size as you add more variables to the problem.
The way to reduce complexity in practice is to “divide and conquer” by breaking down the table into smaller parts. To do […]

Since there were no questions about game AI this week, I’m going to ask myself one! Spare me the embarrassment of doing this next week by contacting me with your queries.
An obviously astute reader (hehe :-) asks “Why are you so harsh with finite state machines? Don’t game developers use them all […]

Thief pioneered the first-person sneaker genre, and is a cornerstone of single player action games in general. The game is an interesting blend of suspense and strategy, which requires some interesting artificial intelligence technology. In particular, this article looks into the sensory system and the design of the behaviors to support that kind of gameplay.

One of the primary goals of game AI is finding a simple and scalable solution for editing logic. Finite state machines have the advantage of being quite simple, but for large systems you’ll need a hierarchical FSM to provide reusable transitions between states.
Such HFSMs are certainly a popular way for making scalable logic. […]

This previous article discussed how traditional finite state machines don’t scale very well. FSM don’t provide ways for reusing logic in different contexts, which leaves you with a choice of two evils: redundancy or complicatedness.
Game developers have found many different solutions to this problem, but one is most popular these days.

Figure: A simple […]

Theoretically speaking, finite state machines (FSM) provide a specific type of logic, similar to regular grammars recognized by finite state automata. In practice also, FSMs are highly tuned to the problem they solve.
This is both a blessing and a curse for games — most of which use FSMs. They start off very simple, […]

This is the last article of the Siggraph 2007 coverage on AiGameDev.com. Feel free to catch up with all the previous posts here (1, 2, 3, 4, 5, 6).
This paper is from the University of British Columbia and introduces techniques for physically-based biped locomotion control. There are two contributions in this paper:

It provides […]

The last post about Game::AI++ was very popular, so here are more details since I’m busy writing some documentation anyway! It’s more of an executive summary this time, so feel free to comment or ask further questions…

Note: You can still sign-up to the newsletter in time for the first release on August 1st.

What […]

Finite state machines (FSM) work well for linear control, as only one state is active at the same time. That’s what they’re intended for, so pretty quickly, your design starts to take advantage of this. Since only one state runs at any moment, the FSM becomes a resource allocation strategy — deciding […]

Cast your thoughts back a few years… Picture the Yahoo! Directory, with many categories but all submissions get pigeonholed, clumsy browsing and no search, let alone a way to subscribe. This structure didn’t work so well in the end did it? Still, that’s what most game developers use every day to organize […]

Most high-level languages support functions that can suspend their computation and later resume where they left off, commonly known as coroutines. However, despite being the standard language of choice for game developers, C++ doesn’t provide much in that department. Luckily, there are many ways to implement simplified coroutines — which is good […]