7 days of WordPress plugins, themes & templates - for free!* Unlimited asset downloads! Start 7-Day Free Trial

The Power of Finite State Machines: Concept and Creation

Read Time: 26 mins

This two-part tutorial will cover creating a multi-state car using a finite state machine. We will start with Procedural FSM and progress into the State Pattern design pattern. Concept and creation will be our main focus during this first part; we will then proceed into application and extension during the second part.

Final Result Preview

Let's take a look at the final result we will be working towards:

What Is a Finite State Machine?

Wikipedia defines an FSM (Finite State Machine) as a mathematical abstraction sometimes used to design digital logic or computer programs. It is a behavior model composed of a finite number of states, transitions between those states, and actions, similar to a flow graph in which one can inspect the way logic runs when certain conditions are met.

It has finite internal memory; an input feature that reads symbols in a sequence, one at a time, without going backward; and an output feature, which may be in the form of a user interface, once the model is implemented. The operation of an FSM begins from one of the states (called a start state), goes through transitions (depending on the inputs) to different states, and can end in any of those available - however, only a certain set of states mark a successful flow of operation.

In my own words, an FSM is a device used by developers to create objects that have different behaviors determined by the current state they are in. Depending on the input, the object can react and/or transition to a different state.

One good example would be a 1970 HK VP70Z machine pistol, which has three firing modes: safety, single shot, and semi-automatic three-round burst. Depending on the current mode you have it set to (state), the result (output) is different when you pull the trigger (input).

Tools: When conceptualizing an idea (the multi-state object you're trying to create), it's best to use a State Transition Table to know what states and actions for those states you will need to add.

Step 1: Setup

It's time to start a new project. With FlashDevelop, create a new AS3 project. For the name, put CarFSM. Click "Browse..." and save it to your desired location. Go into the Package slot and enter "com.activeTuts.fsm". Make sure the "Create directory for project" checkbox is selected then click "OK" to finish.

Once the project is loaded in FlashDevelop, click "View" and select "Project Manager". See the "src" folder? Right-click that and choose "Explore".

When you have that folder open, you should see the "com" folder you created earlier. Open the sourcecode I've included with this tutorial and drag the "assets" folder into "src"; make sure you don't drop it into the "com" folder.

Next, go inside the sourcecode "com" folder and drag the "bit101" folder into the "com" folder inside "src". You can also download minimalComps here if you prefer getting it straight from the source.

Finally, drill down inside the "com" folder (within "src") all the way into "fsm" and double-click Main.as. This should now be open inside FlashDevelop (assuming you have FD as your default .as extension application).

Step 2: Warm Up

We'll start by considering the two states of an even more simple example: MinimalComps's Checkbox.

Let's say we want a Checkbox that will reflect its current state by changing its label. Below is the Transition Table for the Checkbox.

Now for the code. Inside Main.as, one line below the class imports, add the metadata shown below.

Next, go inside the init() method and set your cursor below where it says "entry point". Then add a method call simpleExample(). Next, make sure you have the cursor active somewhere inside the method call, and press the "CTRL + SHIFT + 1" keys. A prompt will show; pick "Generate private function" and hit the "Enter" key.

Now just copy and paste the code below inside the newly created method. Next, put your cursor inside the word "CheckBox" and press "CTRL + SHIFT + 1" to automatically import the required class. Once done, hit "CTRL + ENTER" to run the application.

From here on, if you run into any errors, please compare your classes with the ones I've included with the source download.

You should have something similar to what you see above this line. There are your two states, ON and OFF. Every time you click , the checkbox toggles states and also changes its label as a form of output.

On to the real "Car" FSM project. Make sure you have the project set to run in "debug" mode to enable trace() statements.

Step 3: The Procedural Car FSM

Okay, let's forget the preview at the top of the page and start the Car FSM from scratch. In Main.as, highlight the init() method along with the simpleExample() method and hit the "BACK" key to remove them.

Go one line above the constructor and add the variables below.

The variables _past, _present, _tick, and _counter will all be used for timed execution. I'll explain more about that soon. The _car variable will hold reference for the Car class that will encapsulate the procedural Car FSM actions. The rest are Boolean properties used for triggering timed actions.

Let's work on the timed execution. Add the code below inside the constructor.

Get your cursor inside the word "update" and press "CTRL + SHIFT + 1" and choose "Generate Event handler". When you test the application, you'll see a print out similar to "Start of constructor = 2.119 seconds" (it could be less if you have a faster PC). It's the same as dividing the value of getTimer() with 1000 but they say multiplication is faster.

Let's proceed to the update() method. Add the code below into it.

Now, when you test it again, you'll notice a trace() statement pop-out every two seconds. The _counter is then reset to whatever overlap it had to maintain timing accuracy.

Try using a different value other than two seconds and run it a couple more times.

On to the Car class. Before proceeding, go ahead and remove that if() statement inside the update() method.

Step 4: The Car Class

As I mentioned earlier, we're starting with a fresh idea of creating a multi-state car. Let's say we decided to have a car that can be turned on and off, also driven forward and can run out of gas. That would give us four different states - ON, OFF, DRIVE_FORWARD, and OUT_OF_FUEL.

The very first thing to do is work out the different states and actions for those states in a State Transition Table. You can use a pencil and a blank piece of paper to quickly jot down all the states and actions the Car object would need. See the image below.

Always have an " update()" method to have real time control over your states. Like consume a higher amount of fuel when driving than when the engine's idling at park.

It's easy to tell how each state should respond for each of the actions. It seems simple because we (being human) all think of objects to be in one state or another.

Now we're ready to code the class.

Inside the constructor method in Main.as, go one line before the ENTER_FRAME event listener and add the code below.

Now since there is no Car class, get your cursor inside the "Car" word and press "CTRL + SHIFT + 1", select "Create new class" and hit the "ENTER" key.

Use the same information as shown below. Click "OK" to finish.

You should now have the Car class open in FlashDevelop.

Step 5: Car Variables

Add the code below one line above the class constructor.

The Car is setup to only consume fuel 6 times per second. This is represented by the class constant ONE_SIXTH_SECONDS. In addition, the consumption amount depends if the car is on idle or driving forward. We'll use IDLE_FUEL_CONSUMPTION and DRIVE_FUEL_CONSUMPTION for those purposes.

The four states are represented by String constants with ENGINE_OFF set as default.

The _engineTimer property will be used to trigger consumeFuel() every 1/6 seconds but only if the state is either ENGINE_ON or ENGINE_DRIVE_FORWARD.

Finally, _fuelSupply (which is what consumeFuel() will slowly take away) takes in the value of _fuelCapacity for a full tank.

Step 6: Methods From the State Transition Table

Leave the Car constructor empty for now. Go below it and add the update() method shown below.

We'll have Main.as call this method at every ENTER_FRAME event passing in the elapsed time between frames. Once called, it checks the Car's current state and runs the appropriate action.

If left alone, state transition can only occur through consumeFuel() which sets it to OUT_OF_FUEL when _fuelSupply runs out.

Note: Actions that are on your State Transition Table will always be public access used as input controls. This holds true whether you're using Procedural FSM or the State Pattern.

Step 7: Turning the Car On

Add the code below after the update() method.

Just like the update() method, _currentState is checked and the appropriate action is run. It pretty much explains itself.

Step 8: Turning the Car Off.

The same goes for turning the Car off. Add it next.

It becomes very easy to create the methods. Just copy and paste the previous one, then make a few changes here and there.

Step 9: Driving Forward

Always go back to your State Transition Table to see what needs to happen for each state when you call the input method you're currently working on.

Add the code below the turnKeyOff() method.

Step 10: Consuming Fuel

This method is private since only the Car needs access to it. It's called six times per second from update().

Put the code next after the driveForward() method.

Now you see how the code goes as explained earlier at the Class variables section.

Step 11: Refueling the Car

This method is private since only the Car needs access to it.

Put the code next.

The method first checks to see if the Car has a full tank. If so, it tells you it has a full tank and exits the method.

If the Car doesn't have a full tank on the other hand, it goes through the familiar case/switch statement and runs the proper trace() statement.

The last bit of code calculates the amount of consumed fuel and replenishes only that to keep a full tank. It then prints the value of a full tank.

Step 12: Using toString() to Help trace() Statements

This method had to be overridden since the Car inherits from Sprite which in turn inherits from EventDispatcher.

All it does is return a String statement shown below. Add it as the last method for the Car class.

So now, whenever you call trace(_car) from Main.as, instead of getting "[object Car]", you get a statement like "The car is currently off with a fuel amount of 1.00 gallon(s)."

Let's go back to Main.as for testing. Be sure to save your work before moving forward.

Step 13: Stress Testing

Inside Main's constructor, right after where you added the ENTER_FRAME event listener. Enter the code below.

At this point the Car will perform all six actions without any time lapse. The ENTER_FRAME event has not started yet.

Next, get inside the update() method just below where _tick is added to _counter and paste the code shown next.

I know it's a lot of code but again, it's self-explanatory. Run the application and check your output.

If you get errors, make sure to compare your code with the classes I've included with this tutorial.

Try changing _fuelCapacity in Car and mix-up the methods on some or all of the test sections and run it again. You'll see that the code is solid and this Procedural FSM is effective. And That's it! We're done.

Wait a minute. Since all is well, why don't we add the ability to drive backward and turbo? While at it, we might as well add animation and sound. Now, imagine just how bloated the Car class would get if you make it do all the things the car does at the top of page. We're looking at maybe 2000 lines of code - at least. LOL! I'd probably say, Ya, sure, I can hack that. But the code becomes very fragile and easy to break. So it might be a good idea to use a different technique.

If the FSM object has simple behavior, by all means, use this technique. But if you have a complex object that might need to add new features in the future. Maybe even add a few more states - well, that's where the State Pattern comes in.

Step 14: Introducing the State Pattern

Say hello to the "big brother" of Procedural FSM. Using this Design Pattern will make your states easy to maintain and make changes to, but the best part - other states can now be added without the risk of ruining the code.

To apply this pattern, we will again refer to our trusted State Transition Table. See Step 4. The State Pattern consists of three parts. First is the State Interface, this will contain all the actions you see in the State Transition Table. In addition, this State Interface may also contain methods that are shared by all State classes. Second, the State classes that correspond for each state shown in your State Transition Table. And third, the State Machine - which is normally your converted Procedural FSM object (the Car class). When converted, the Car will provide public accessors and modifiers to allow external control from all State classes. The Car will delegate actions to the currently active State.

Step 15: Beginning the Conversion

Click "View" and select "Project Manager". Within "src", drill down until you see the "fsm" folder. Right-click that and choose "Add > New Interface..." then hit "ENTER".

Name it "IState". Interfaces start with "I" for naming convention.

Once FlashDevelop opens the class, add the code below in it.

This IState interface will be implemented by all the State classes. The last function toString() has nothing to do with controlling the Car but all the State classes use it.

For more info about Interfaces, see AS3 101: Introduction to Interfaces. Let's start adding the state classes.

Step 16: The EngineOff Class

Follow the same procedure when you created the IState Interface but instead, choose "Add new class".

Name it "EngineOff". For the interface slot, click add and type "IState", this should find the IState class from within the same folder. Also, the checkbox for "Generate interface methods implementations" should be selected. Click "OK" to complete.

The new class comes out half-way finished. It should look very similar to what shows below.

These state classes won't need to extend Sprite since all Media assets (second part) will be added and controlled via the car. The states will be instantiated through the Car class passing itself as reference. A two-way composition structure will be used to allow communication between the Car and the state classes.

Step 17: Finishing Our EngineOff Class

Change the constructor method to match the code below.

I've included the _car variable above the modified constructor. Now we can control the Car class from within this state.

Let's move on to the interface method implementations.

Get inside the turnKeyOff() method. Check your State Transition Table to see what happens here. Next, compare that with the procedural turnKeyOff() method inside the Car class. Remember, we still have the Car class in Procedural FSM. Once you see the match. Copy the action for the ENGINE_OFF state into the empty method. The turnKeyOff() method should reflect what you see below.

The trace() statement has been replaced by print() which we'll add to the Car class later.

Now go inside the turnKeyOn() method and add the code listed next.

Check it against you State Transition Table and procedural turnKeyOn() method for the ENGINE_OFF state to see if it's the same. The changeState() method is delegated back to the car passing in the retrieved state it needs to change to.

The rest of the methods are processed the same way. Copy the code below and replace the empty methods with it.

The driveForward() method does the same as the procedural driveForward() methods with _currentState set as ENGINE_OFF

reFuel() asks the car to see if the tank is not full. If not, the car will then refill with fuel. You'll see how those two methods work when we change the Car class later.

The update() method remains empty since the car won't be running.

toString() works the same as the car's toString() method.

This completes the EngineOff class.

Before creating the rest of the other state classes, let's modify the Car class and convert it into its own State Machine.

Step 18: The Car State Machine

Important: Create a duplicate Car class before following the procedure below. A text copy would suffice but make sure to save it as reference for later.

Instead of going through the changes item by item, just copy the code below then paste and replace the content of your Car class with it.

Let's go over the changes.

Starting at variable definition. You'll notice that the four states have changed type to IState and are no longer static constants.

Next, the constructor now calls init() which in turn calls initializeState(). All the state classes are instantiated through that method.

Then comes the easy part, no more switch statements. The car just delegates the actions to the current state. See turnKeyOff() down to reFuel()

The consumeFuel() method had to become public access for EngineOn and EngineDriveForward.

And then the two methods we used in EngineOff's reFuel() method - hasFullTank() and refillWithFuel().

Below them are the explicit getters that provide access for all four states. It may seem like it's weird protocol but it's just encapsulation at work.

The changeState() does exactly what it says, it changes the _currentState.

Again, following the strict rule of OOP, the _engineTimer property can be accessed and modified through these two methods: get engineTimer() and set engineTimer().

print() for now will just pass the String parameter to a trace() statement. And then the toString() method.

Step 19: Creating the Other Three States

To simplify creation of the three other classes, get inside the Car class from within the initialize() method. Place your cursor inside the "EngineOn" word and press "CTRL + SHIFT + 1" to generate a prompt. Select "Create new class" and hit "ENTER".

Match the information as shown in the image below then click "OK".

This is similar to Step 16 when you created the EngineOff class. Only this time, we used FD's shortcut keys. Also, you'll notice a refence to the car object in the constructor which was passed in at instantiation. Don't forget to add that "\$" sign to the car parameter for your constructor and the only class variable _car on top.

Compare it with the code below.

Now go back inside the initialize() method in Car and repeat the process for the last two remaining state classes.

Step 20: Completing the EngineOn Class

Do you think you can piece it together using the Car.txt (duplicate) and State Transition Table?

Give it a shot, just follow Step 17 and you'll do great. Just remember that you're working on action results for ENGINE_ON now.

Excellent! When you're done, compare your code with the classes inside the folder "StatePatternPartial1" included with the source download.

Step 21: Final Testing

Once you finish work with all your state classes, go back to Main.as and run your application.

Hopefully everything went well and you didn't get any errors. Information should start printing out of your output panel.

We'll end the first part of the tutorial here. For the second part, we'll start by adding the two other states "EngineDriveReallyFast" and "EngineDriveBackward". Then we'll add controls for animation and sound proving how easy it is to modify and scale.

Conclusion

Of all the design patterns I've played with, this one is by far the most important (for me), especially in the realm of game design. You'll see why when you start using it to build your next game object. Why don't you try creating the pistol I mentioned at the beginning of this tutorial. You'll enjoy creating it! Just remember to start small. Always build it from Procedural FSM then convert it to the State Pattern.

Here are the steps:

1. Sketch up the State Transition Table for your Object.
2. Create your Procedural FSM Object.
3. Once Procedural FSM works, if you need to add a lot more feature and/or states, convert it to the State Pattern.
4. Build your IState Interface first.
5. Create the first/default State class (Consult State Transition Table and Procedural FSM actions).
6. Duplicate a copy of your Procedural FSM Object, then allow public access to all properties the State classes need to control.
7. Create the rest of the State classes.
8. Add features/states as per your requirements. These usually present themselves while you're working on your State actions.

See you in the second part!

As always, for any comments, suggestions, or concerns, please post a note in the comments section.