Advertisement
  1. Game Development
  2. Artificial Intelligence
Gamedevelopment

Finite-State Machines: Theory and Implementation

by
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:

FSM representing the brain of an enemy.

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:

FSM representing the brain of an ant.

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.

FSM representing the brain of an ant. Notice the lack of a transition between run away and go 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:

FSM of ant brain with focus 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":

Ant controlled by a FSM. Move the mouse cursor to threaten the ant.

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:

Ant FSM updated with new transitions.

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:

Stack-based FSM

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

Transitions in a stack-based FSM: pop itself + push new; pop itself; push new.

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:

Ant controlled by a stack-based FSM. Move the mouse cursor to threaten the ant.

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!

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.