# Finite-State Machines: Theory and Implementation

Difficulty:IntermediateLength:MediumLanguages:

A finite-state machine is a model used to represent and control execution flow. It is perfect for implementing AI in games, producing great results without a complex code. This tutorial describes the theory, implementation and use of simple and stack-based finite-state machines.

All icons made by Lorc, and available on http://game-icons.net.

Note: Although this tutorial is written using AS3 and Flash, you should be able to use the same techniques and concepts in almost any game development environment.

## What Is a Finite-State Machine?

A finite-state machine, or FSM for short, is a model of computation based on a hypothetical machine made of one or more states. Only a single state can be active at the same time, so the machine must transition from one state to another in order to perform different actions.

FSMs are commonly used to organize and represent an execution flow, which is useful to implement AI in games. The "brain" of an enemy, for instance, can be implemented using a FSM: every state represents an action, such as `attack` or `evade`:

An FSM can be represented by a graph, where the nodes are the states and the edges are the transitions. Each edge has a label informing when the transition should happen, like the `player is near` label in the figure above, which indicates that the machine will transition from `wander` to `attack` if the player is near.

## Planning States and Their Transitions

The implementation of a FSM begins with the states and transitions it will have. Imagine the following FSM, representing the brain of an ant carrying leaves home:

The starting point is the `find leaf` state, which will remain active until the ant finds the leaf. When that happens, the current state is transitioned to `go home`, which remains active until the ant gets home. When the ant finally arrives home, the active state becomes `find leaf` again, so the ant repeats its journey.

If the active state is `find leaf` and the mouse cursor approaches the ant, there is a transition to the `run away` state. While that state is active, the ant will run away from the mouse cursor. When the cursor is not a threat anymore, there is a transition back to the `find leaf` state.

Since there are transitions connecting `find leaf` and `run away`, the ant will always run away from the mouse cursor when it approaches as long as the ant is finding the leaf. That will not happen if the active state is `go home` (check out the figure below). In that case the ant will walk home fearlessly, only transitioning to the `find leaf` state when it arrives home.

## Implementing a FSM

An FSM can be implemented and encapsulated in a single class, named `FSM` for instance. The idea is to implement every state as a function or method, using a property called `activeState` in the class to determine which state is active:

Since every state is a function, while an specific state is active the function representing that state will be invoked every game update. The `activeState` property is a pointer to a function, so it will point to the active state's function.

The `update()` method of the `FSM` class must be invoked every game frame, so that it can call the function pointed by the `activeState` property. That call will update the actions of the currently active state.

The `setState()` method will transition the FSM to a new state by pointing the `activeState` property to a new state function. The state function doesn't have to be a member of FSM; it can belong to another class, which makes the `FSM` class more generic and reusable.

## Using a FSM

Using the `FSM` class already described, it's time to implement the "brain" of a character. The previously explained ant will be used and controlled by an FSM. The following is a representation of states and transitions, focusing on the code:

The ant is represented by the `Ant` class, which has a property named `brain` and a method for each state. The `brain` property is an instance of the `FSM` class:

The `Ant` class also has a `velocity` and a `position` property, both used to calculate the movement using  Euler integration. The `update()` method is called every game frame, so it will update the FSM.

To keep things simple, the code used to move the ant, such as `moveBasedOnVelocity()`, will be omitted. More info on that can be found in the Understanding Steering Behaviors series.

Below is the implementation of each state, starting with `findLeaf()`, the state responsible for guiding the ant to the leaf position:

The `goHome()` state, used to guide the ant home:

Finally, the `runAway()` state, used to make the ant flee the mouse cursor:

The result is an ant controlled by a FSM "brain":

## Improving the Flow: Stack-Based FSM

Imagine that the ant also needs to run away from the mouse cursor when it is going home. The FSM can be updated to the following:

It seems a trivial modification, the addition of a new transition, but it creates a problem: if the current state is `run away` and the mouse cursor is not near anymore, what state should the ant transition to: `go home` or `find leaf`?

The solution for that problem is a stack-based FSM. Unlike our existing FSM, a stack-based FSM uses a stack to control states. The top of the stack contains the active state; transitions are handled by pushing or popping states from the stack:

The currently active state can decide what to do during a transition:

It can pop itself from the stack and push another state, which means a full transition (just like the simple FSM was doing). It can pop itself from the stack, which means the current state is complete and the next state in the stack should become active. Finally, it can just push a new state, which means the currently active state will change for a while, but when it pops itself from the stack, the previously active state will take over again.

## Implementing a Stack-Based FSM

A stack-based FSM can be implemented using the same approach as before, but this time using an array of function pointers to control the stack. The `activeState` property is no longer needed, since the top of the stack already points to the currently active state:

The `setState()` method was replaced with two new methods: `pushState()` and `popState()``pushState()` adds a new state to the top of the stack, while `popState()` removes the state at the top of the stack. Both methods automatically transition the machine to a new state, since they change the top of the stack.

## Using a Stack-Based FSM

When using a stack-based FSM, it's important to note that each state is responsible for popping itself from the stack. Usually a state removes itself from the stack when it is no longer needed, like if `attack()` is active but the target just died.

Using the ant example, just a few changes are required to adapt the code to use a stack-based FSM. The problem of not knowing the state to transition to is now seamlessly solved thanks to the very nature of stack-based FSM:

The result is an ant able to run away from the mouse cursor, transitioning back to the previously active state before the threat:

## Conclusion

Finite-state machines are useful to implement AI logic in games. They can be easily represented using a graph, which allows a developer to see the big picture, tweaking and optimizing the final result.

The implementation of a FSM using functions or methods to represent states is simple, but powerful. Even more complex results can be achieved using a stack-based FSM, which ensures a manageable and concise execution flow without negatively impacting the code. It's time to make all your game enemies smarter using a FSM!