Finite State Machine (FSM) Based Agent

Finite state machines have been used for a long time to create illusion of intelligence for game agents. A finite state machine (FSM) is a computational model used to simulate sequential logic. It has a finite number of states a game agent can be in at any given time, make transitions from one to another, and can operate. There is one simple rule though, the state machine can only be in one state at any moment.

To apply this idea to game AI development, we decompose our agent’s behaviors into easily manageable states and construct a state machine based on some transition rules.

For example the ghosts in Pac-man has two states: Chase and evade. The agents start in their specialized state and if the player (Pac-man or Ms. Pac-man) eats one of the power pills, then they all transit to the evade state. When the power pill timer is done, they transit to the chase state.

For a bit more complex example, you can consider FPS/TPS bots. Usually, these bots have states, such as FindArmor, FindHealth, SeekCover, and so on. They move between one of these states depending on their self-condition.

Advantages and Disadvantages of FSMs

There are many advantages of FSM based game agent implementation. That’s also why FSM-based approach still exists after many years.

First of all, FSMs are quick and simple to code. They are also easy to debug since the behavior of the game agent is broken down into the easily manageable chunks (states). Since FSMs essentially follow hard-coded rules, they have little computational overhead. Easily manageable chunks also make it easy for you to discuss the design of your AI with non-programmers, such as level designers, game producers, and so on. Finally, FSMs let you add new states and rules. So, you can easily adjust, tweak, or expand the scope of the agent’s behavior. Finally, FSMs provide a solid backbone with which you can combine other techniques, such as fuzzy logic or neural networks.

The biggest disadvantage of FSMs comes from its nature. Because, FSMs naturally can only be in one state at any moment and there is no real thinking involved other than if-this-then-that sort of process, developing complex behaviors can be painful and requires you to introduce many states or hierarchical state machines.

FSMs also tend to become unmanageable easily and they cannot capture similar behaviors and benefit from behavior inheritance. Thus, they end up repeating the same behavior in many states.

Implementing a FSM

Even if there are many ways to implement a FSM (including an if-else based approach), it is better to use an approach based on state design pattern. In this way, you embed the rules into the states for the state transitions. So, you monitor the conditions and instruct to switch between the states. You can also easily control enter and exit actions. Thus, each state becomes a self-contained unit aware of the existence of any other states, and does not rely on any external logic for the state transitions. As a consequence, adding new states or replacing a set of states with a new set become straightforward.

So, each of a game agent’s states is implemented as a unique class and each agent holds a pointer (or reference for C#) to an instance of its current state. The logic for determining any state transitions is contained within each state and an agent implements a changeState() method to facilitate the state transition.

If your design and requirements let you, you can consider to make your states singleton for increasing the efficiency. In this way, you can share your state machine among the agents. However, if your states access some external data that may be different for each agent, you would require some extra logic to run your state machine properly. You may even consider to dispose the singleton design. But “friends don’t let friends create singletons“, anyway.

One of the last important points are making the base State class as reusable as possible. Not surprisingly the key thing for this is implementing the base class as template (or generic for C#).

So, here some code:

State.hpp

StateMachine.hpp

If you have some questions about null object pattern, please refer to this page for the details.

An improvement on the state class I would make would be applying template method pattern. Template method pattern intents to separate the interface and implementation as much as possible for making future changes and refactors easier. Virtual functions are considered as data members. Protected and private virtuals define the class’ customizable behavior, and there is no reason to make them public. A public virtual method would define both interface and a customization point, a duality that could reflect weak design. The class’ interface must remain consistent in all derived classes.

So, I would suggest to change the State.hpp as:

An Example of FSM Based Agent

I will use the enemy state machine I developed for Hands-On Game AI Development video course by Packt as an example.

In this example, our game agents have three states:

  • Wander around
  • Go to the alarm
  • Go to the player

As a design decision, the agents own the states and the state machine.

The default state is the wandering state and if the agent gets close enough to the player, then it transitions to GoToAlarm alarm state. After reaching the alarm or alarmed by the other agents, it transitions to GoToPlayer state. When the player gets caught, the agents go back to the wandering state.