Finite-State Machines: Theory and Implementation

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.

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:

public class FSM {
	private var activeState :Function; // points to the currently active state function

	public function FSM() {
	}

	public function setState(state :Function) :void {
		activeState = state;
	}

	public function update() :void {
		if (activeState != null) {
			activeState();
		}
	}
}

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:

public class Ant
{
	public var position   :Vector3D;
	public var velocity   :Vector3D;
	public var brain      :FSM;

	public function Ant(posX :Number, posY :Number) {
		position 	= new Vector3D(posX, posY);
		velocity 	= new Vector3D( -1, -1);
		brain		= new FSM();

		// Tell the brain to start looking for the leaf.
		brain.setState(findLeaf);
	}

	/**
	 * The "findLeaf" state.
	 * It makes the ant move towards the leaf.
	 */
	public function findLeaf() :void {
	}

	/**
	 * The "goHome" state.
	 * It makes the ant move towards its home.
	 */
	public function goHome() :void {
	}

	/**
	 * The "runAway" state.
	 * It makes the ant run away from the mouse cursor.
	 */
	public function runAway() :void {
	}

	public function update():void {
		// Update the FSM controlling the "brain". It will invoke the currently
		// active state function: findLeaf(), goHome() or runAway().
		brain.update();

		// Apply the velocity vector to the position, making the ant move.
		moveBasedOnVelocity();
	}

	(...)
}

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:

public function findLeaf() :void {
	// Move the ant towards the leaf.
	velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);

	if (distance(Game.instance.leaf, this) <= 10) {
		// The ant is extremelly close to the leaf, it's time
		// to go home.
		brain.setState(goHome);
	}

	if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
		// Mouse cursor is threatening us. Let's run away!
		// It will make the brain start calling runAway() from
		// now on.
		brain.setState(runAway);
	}
}

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

public function goHome() :void {
	// Move the ant towards home
	velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);

	if (distance(Game.instance.home, this) <= 10) {
		// The ant is home, let's find the leaf again.
		brain.setState(findLeaf);
	}
}

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

public function runAway() :void {
	// Move the ant away from the mouse cursor
	velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);

	// Is the mouse cursor still close?
	if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
		// No, the mouse cursor has gone away. Let's go back looking for the leaf.
		brain.setState(findLeaf);
	}
}

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:

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:

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:

public class StackFSM {
	private var stack :Array;

	public function StackFSM() {
		this.stack = new Array();
	}

	public function update() :void {
		var currentStateFunction :Function = getCurrentState();

		if (currentStateFunction != null) {
			currentStateFunction();
		}
	}

	public function popState() :Function {
		return stack.pop();
	}

	public function pushState(state :Function) :void {
		if (getCurrentState() != state) {
			stack.push(state);
		}
	}

	public function getCurrentState() :Function {
		return stack.length > 0 ? stack[stack.length - 1] : null;
	}
}

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:

public class Ant {
	(...)
	public var brain :StackFSM;

	public function Ant(posX :Number, posY :Number) {
		(...)
		brain = new StackFSM();

		// Tell the brain to start looking for the leaf.
		brain.pushState(findLeaf);

		(...)
	}

	/**
	 * The "findLeaf" state.
	 * It makes the ant move towards the leaf.
	 */
	public function findLeaf() :void {
		// Move the ant towards the leaf.
		velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);

		if (distance(Game.instance.leaf, this) <= 10) {
			// The ant is extremelly close to the leaf, it's time
			// to go home.
			brain.popState(); // removes "findLeaf" from the stack.
			brain.pushState(goHome); // push "goHome" state, making it the active state.
		}

		if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
			// Mouse cursor is threatening us. Let's run away!
			// The "runAway" state is pushed on top of "findLeaf", which means
			// the "findLeaf" state will be active again when "runAway" ends.
			brain.pushState(runAway);
		}
	}

	/**
	 * The "goHome" state.
	 * It makes the ant move towards its home.
	 */
	public function goHome() :void {
		// Move the ant towards home
		velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);
		
		if (distance(Game.instance.home, this) <= 10) {
			// The ant is home, let's find the leaf again.
			brain.popState(); // removes "goHome" from the stack.
			brain.pushState(findLeaf); // push "findLeaf" state, making it the active state
		}
		
		if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
			// Mouse cursor is threatening us. Let's run away!
			// The "runAway" state is pushed on top of "goHome", which means
			// the "goHome" state will be active again when "runAway" ends.
			brain.pushState(runAway);
		}
	}
	
	/**
	 * The "runAway" state.
	 * It makes the ant run away from the mouse cursor.
	 */
	public function runAway() :void {
		// Move the ant away from the mouse cursor
		velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);
		
		// Is the mouse cursor still close?
		if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
			// No, the mouse cursor has gone away. Let's go back to the previously
			// active state.
			brain.popState();
		}
	}
	(...)
}

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!

1	public class Ant
2	{
3	public var position :Vector3D;
4	public var velocity :Vector3D;
5	public var brain :FSM;
6
7	public function Ant(posX :Number, posY :Number) {
8	position = new Vector3D(posX, posY);
9	velocity = new Vector3D( -1, -1);
10	brain = new FSM();
11
12	// Tell the brain to start looking for the leaf.
13	brain.setState(findLeaf);
14	}
15
16	/**
17	* The "findLeaf" state.
18	* It makes the ant move towards the leaf.
19	*/
20	public function findLeaf() :void {
21	}
22
23	/**
24	* The "goHome" state.
25	* It makes the ant move towards its home.
26	*/
27	public function goHome() :void {
28	}
29
30	/**
31	* The "runAway" state.
32	* It makes the ant run away from the mouse cursor.
33	*/
34	public function runAway() :void {
35	}
36
37	public function update():void {
38	// Update the FSM controlling the "brain". It will invoke the currently
39	// active state function: findLeaf(), goHome() or runAway().
40	brain.update();
41
42	// Apply the velocity vector to the position, making the ant move.
43	moveBasedOnVelocity();
44	}
45
46	(...)
47	}

1	public class StackFSM {
2	private var stack :Array;
3
4	public function StackFSM() {
5	this.stack = new Array();
6	}
7
8	public function update() :void {
9	var currentStateFunction :Function = getCurrentState();
10
11	if (currentStateFunction != null) {
12	currentStateFunction();
13	}
14	}
15
16	public function popState() :Function {
17	return stack.pop();
18	}
19
20	public function pushState(state :Function) :void {
21	if (getCurrentState() != state) {
22	stack.push(state);
23	}
24	}
25
26	public function getCurrentState() :Function {
27	return stack.length > 0 ? stack[stack.length - 1] : null;
28	}
29	}

1	public class Ant {
2	(...)
3	public var brain :StackFSM;
4
5	public function Ant(posX :Number, posY :Number) {
6	(...)
7	brain = new StackFSM();
8
9	// Tell the brain to start looking for the leaf.
10	brain.pushState(findLeaf);
11
12	(...)
13	}
14
15	/**
16	* The "findLeaf" state.
17	* It makes the ant move towards the leaf.
18	*/
19	public function findLeaf() :void {
20	// Move the ant towards the leaf.
21	velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y);
22
23	if (distance(Game.instance.leaf, this) <= 10) {
24	// The ant is extremelly close to the leaf, it's time
25	// to go home.
26	brain.popState(); // removes "findLeaf" from the stack.
27	brain.pushState(goHome); // push "goHome" state, making it the active state.
28	}
29
30	if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
31	// Mouse cursor is threatening us. Let's run away!
32	// The "runAway" state is pushed on top of "findLeaf", which means
33	// the "findLeaf" state will be active again when "runAway" ends.
34	brain.pushState(runAway);
35	}
36	}
37
38	/**
39	* The "goHome" state.
40	* It makes the ant move towards its home.
41	*/
42	public function goHome() :void {
43	// Move the ant towards home
44	velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y);
45
46	if (distance(Game.instance.home, this) <= 10) {
47	// The ant is home, let's find the leaf again.
48	brain.popState(); // removes "goHome" from the stack.
49	brain.pushState(findLeaf); // push "findLeaf" state, making it the active state
50	}
51
52	if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) {
53	// Mouse cursor is threatening us. Let's run away!
54	// The "runAway" state is pushed on top of "goHome", which means
55	// the "goHome" state will be active again when "runAway" ends.
56	brain.pushState(runAway);
57	}
58	}
59
60	/**
61	* The "runAway" state.
62	* It makes the ant run away from the mouse cursor.
63	*/
64	public function runAway() :void {
65	// Move the ant away from the mouse cursor
66	velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y);
67
68	// Is the mouse cursor still close?
69	if (distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) {
70	// No, the mouse cursor has gone away. Let's go back to the previously
71	// active state.
72	brain.popState();
73	}
74	}
75	(...)
76	}