Artificial Intelligence > General

An Introduction to Finite State Machines


		Nathaniel Meyer 29/08/2004

Introduction

This tutorial is aimed at explaining, providing tips and techniques, and gives an example to demonstrate the use and purpose of Finite State Machines (which will now be abbreviated FSM). The illustrations and example take use of the Unified Modeling Language (abbreviated UML) because it is a language best suited for it. Although understanding UML is not a requirement for this tutorial or FSMs in general, it is definitely a language you should get to know.

Feel free to review the glossary of terms used within this tutorial. It is best that you know what I am talking about before or while you read the content.

Applications of FSM

FSMs have been used broadly in the video game industry. Since ID Software released the source code to the Quake and Quake 2 projects, people have noticed that the movement, defensive, and offensive strategies of the bots were controlled by a simple FSM. ID is not the only company to take advantage of this either. The latest games like Warcraft III take advantage of complex FSM systems to control the AI. Chat dialogs where the user is prompt with choices can also be ran by FSMs.

Aside from controlling NPCs, bots, dialog, and environmental conditions within video games, FSMs also have a large role outside of the video game industry. For example, cars, airplanes, and robotics (machinery) have complex FSMs. You could even say websites have a FSM. Websites that offer menus for you to traverse other detailed sections of the website act much like a FSM does with transitions between states.

What is a FSM?

If you ever seen a flowchart before, you can think of a FSM as the same thing. It has a set of states that follow a certain path. A state has transitions to other states, which is caused by events or actions within a state. Here is a real world example.

You are in the kitchen (state) and you felt a sudden urge to drink water. You then decide to walk over to the cupboard and grab a glass. This is an event (walk to cupboard) and you are now in a new state with new options available to you. You then open the cupboard (action) and grab a glass (action). With the glass, you walk over to the sink (event) and turn on the tap (action). Water into poured into the glass (event) and you then drink it (action).

So in a nutshell, an event leads you to a state in which you perform an action or several actions (though you do not always have to perform an action). So when you walk to the cupboard, that leads you to the state "At Cupboard" where the typical action is "Open Cupboard". To better demonstrate a FSM, a robot example will be used throughout this tutorial.

Example - Robotics

With all things in life, careful planning is a must, especially with a FSM. The first step to developing a FSM is to list all the known entities in your problem. Let us start with the robot.

Figure 1.1: Bender, our robot
Here is Bender, as you may recognize him from Futurama. Bender would like to turn on and off, walk, run, raise and lower its arms, turn its head, and talk. There are many other features left to be desired, like ducking, jumping, repairing itself, reacting to environments, give it emotions, etc… As you can see, the list goes on and this is quite normal in a FSM. Keep in mind however, as the term finite implies you will need to limit the scope of the problem to a finite set of entities. For the purpose of this tutorial, a subset of functions is chosen. Given these entities, we should construct a table listing all the possible events and states associated with them.

Event	State

turnOn	Activated
turnOff	Deactivated (Idle)
stop	Stopped
walk	Walking
run	Running
raiseLeftArm	LeftArmRaised
lowerLeftArm	LeftArmLowered
lowerLeftArm	LeftArmLowered
raiseRightArm	RightArmRaised
lowerRightArm	RightArmLowered
turnHead	HeadTurned(direction)
speak	Talking(text)

Table: 1.1. Small list of known events with Bender

When developing FSMs, you should expect to see an even greater list of events and states to support. As you will see later, as logic errors are common in programming, event errors are common in FSMs.

Just before we move on, I would like to make a few notes about the selected states above. States do not have multiple roles. Every time Bender is turned on, the same flow of direction will always occur. If at any time in your projects there is a breech in that flow, it would need to be fixed. This is one of the problems with FSMs because sooner or later someone is going to pick up the pattern. Ways around this would be to add more events to a given situation or randomize the actions performed.

Secondly, states are unique. No two states should have the same reaction to a specified event. For example, having Bender "speak" and "shout" are synonymous in terms of speech; therefore we eliminate one while keeping the other and supplement arguments to dictate how a certain text is pronounced (be it calm, yelling, stutter, etc…).

Thirdly, state transitions do not normally branch. By branch I mean through the use of conditional statements. For example, Bender has a set of movement options. Such movements can be decided via IF/THEN statements, however it is best to avoid that since the purpose behind states is to replace the need for IF/THEN statements with events. Although states are flexible and do allow such conditional operations, it is always best to avoid them. It reduces complexity and lessens the chance for logic errors.

Now that we have a list of events and states, it is best to draw them out. When you visually see your model, it is easier to pick out where things may go wrong or where things could use improvements.

Figure 1.2: Sample state diagram of Bender
This model representation is actually wrong. You should note that in a state, you perform a certain action and when you leave that state, the action is no longer performed. In this model, we can only have one state at a time with no transition between them. It is possible for Bender to both walk and then run, so there should be a link between those two states. Since there are only a few movement states, the amount of transitions won't be all that bad. If you were to support a much larger base of states, then you will notice a massive set of transitions between them, undoubtedly creating confusion. Unfortunately there is no way around this. Diagrammatically speaking, you could specify a cleaner set of transitions, but ultimately when you program the states you will still have a complex amount of transitions to support. Here is another way to represent multiple states a bit cleaner.

Figure 1.3. Simplified State Model
Here we assign a new state Activity that holds all the activities Bender can do with transitions to itself. This also allows for multiple events to run in parallel so you could walk and talk at the same time. Inevitably, the programming will still be as complex. Take note that on events like talk, you would set up timers to display the text for X amount of seconds. When the timer expires, you would stop talking.

Now that we have a state diagram, we need to examine it further and construct a state table. A state table is nothing more than a table listing all the states, the actions to get to them, and the reaction performed by them. For example, when Bender turns on, it puts itself in the turned on state. From here, it is allowed to conduct various movements and shut itself down. When in the activity state, it cannot directly shut itself down. So the state table illustrates to us what and when can Bender perform certain actions.

#	Event	Actions	Comment	Caused By	Will Effect

1	turnOn	bootUp	Bender is turning on		2-10
2	bootUp	Activity	Allow various activities	1	3-8
3	walk	goWalk	Bender will begin to walk
4	run	goRun	Bender will begin to run
5	talk	say(text)	Bender will say "text"
6	turnHead	turningHead	Bender rotates head
7	raiseArm	raisingArm	Bender raises arm (left or right)
8	lowerArm	laweringArm	Bender lowers arm (left or right)
9	stop	powerDown	Bender stops current action		3-8
10	turnOff	shutDown	Bender will shut off		1-9

Table: 1.2. State Table for Random Scenarios
As you see, defining a complete FSM is an extremely long process and we have not even done any coding yet! The state table is left incomplete as the number of events and actions are quite large, but there should be enough presented to illustrate the idea.

Putting it all together, the state diagram helps illustrate what the functionality is like and the state table defines the types of inputs to those functions and the expected outputs. So, with a complete state diagram and state table, you have the blueprints to develop your FSM.

Example - Code

Knowing how to set yourself up for a FSM is one thing, going about programming it is another. There are many ways to program a FSM, so the method I present here is one that I just prefer. I tried to comment the code as best as possible so hopefully my coding style won't be a strain on your eyes =)

How The Code Works:
There are two major classes.

1) State:	The state class is responsible for setting transitions, specifying actions, and pointing to the right function that represents the action. In this code, a state supports the 3 preliminary specifications: OnEntry, Do, and OnExit, and supports an unlimited amount of OnEvent specifications. These specifications are used to define your actions. This should help you practice with designing much larger FSMs.

2) FSM:	The FSM class is a collection of states. Its sole purpose is to function as a controller between states and execute the necessary state actions based on the events passed to it.

The code does not make use of any conventional programming style. There are no switch statements and there are no IF/THEN expressions. Everything in the FSM is controlled by sending the correct events down the pipeline. After that, the FSM will choose the correct course based on how you configured your states.

Also, I have not placed any fancy reactions in the code (such as guard conditions). I simply want to demonstrate how state transitions occur and provide a clean and elegant interface to handling FSMs. Feel free to add new features and reactions to them.

Click here to download the code (.zip)
Code was developed in Visual Studio .NET 2003

Conclusion

Finite State Machines are widely used in video games to supplement AI given its easy structure and maintenance. When given the problem that requires finite number of solutions, FSMs are definitely an easy method to approach. Just remember the format to help you design and develop FSMs.

1) Review the problem. Write down all the entities involved
2) Design a state diagram from the work you did in 1)
3) Review the state diagram. Make sure it meets all the requirements and does not fail under simple transitions.
4) Develop a state table to clarify the state diagram and correlate to the code.
5) Design the code.

Glossary

Here is a list of terminology used throughout the tutorial. If any of these seem unfamiliar to you, it would be helpful to know what they mean before continuing on with the tutorial. They are as follows:

1) FSM	A collection of states and transitions that outline a path of actions that may occur.
2) State	A state is a position in time. For example, when you are at the bus stop, you are currently in a waiting state.
3) Event	An event is something that happens in time. For example, the bus has arrived.
4) Action	A task performed given a certain event that occurred. For example, you enter the bus.
5) Transition	A link between 2 states. May be unidirectional or bidirectional.

Download source code for this article

Discuss this article in the forums

Print article

Want to write for us? Click here