Subscribe to GameFromScratch on YouTube Support GameFromScratch on Patreon


29. June 2016

 

Welcome to a new tutorial series here on GameFromScratch.com where we will be looking at core concepts of game programming.  This includes data structures, design patterns and algorithms commonly used in game development.  We start the series off with Finite State Machines.

 

There is an HD video version of this tutorial available here and embedded below.

 

What is a Finite State Machine?

 

A Finite State Machine (or FSM for short) is one of those concepts that sounds much scarier than it actually is.  In the simplest form it’s a datatype that can have only one value (state) from a finite selection of values(states).  The easiest way is to understand the finite state machine is to look at a real world example.

 

trafficLight

 

Yep, a traffic light is a perfect example of a FSM, or at least, the logic controlling it is.  Consider the three possible states this particular traffic light can be in.  At any given point (assuming I suppose the power is working...) the light will be one of three states, red, yellow or green.  It can never been more than one of those states at a time, it’s always red or yellow or green.  These are the two keep concepts of a finite state machine.  There are a finite number of states ( 3 in this case ) and only one is true or active at a time.

 

It’s a very simple concept, but extremely useful in game development.

 

What are FSMs Used For?

 

In game development, one of the most common uses for finite state machines is artificial intelligence.  Consider the example of PacMan’s ghosts.  A state machine can be used to control how they behave.  A ghost may have one of several different operating modes for example waiting to be released, hunting, hunted and dead.  The state machine is what is used to drive the ghost’s actions and to switch between states.  You will find AI examples absolutely loaded with state machines, often with some fuzzy logic controlling the transition between states to give a layer of unpredictability to your characters.

AI isn’t the only place of course, think of all the different things in a game that are related, there are multiple different states they can be in, but only one can be active at a time.  Game states are a very common example, where you break your game up into a series of states, for example Loading, Main Menu, Playing, High Score, Exiting.  Many game engines ( one such example is Phaser ) split your game up into a series of states.  The ultimate controller of these states is a finite state machine.  A sequential UI ( think of a sequence of dialogs controlled by next/back buttons ) can also be implemented using FSMs.  They are also commonly used to control elements in a games world.  Consider a game with a weather system, be it day or night cycles or season cycles like Spring, Summer, etc...  these would most likely be controlled via FSMs.

 

Implementing a Finite State Machine

 

The example we are going to use here is to implement a traffic light via FSM.  At it’s core the data is going to be stored in an enum, a natural fit for state machines, but stack based or array based options are also viable.  This example is not only going to switch the traffic lights periodically, it’s also going to implement callbacks so the world at large can interact with the light.  This example is implemented using C#, but should be easily adapted to most modern programming languages.

 

using System;

namespace GameFromScratchDemo
{

    public class TrafficLight{
        // This enum represents the three possible values our state machine can 
        be
        public enum States { Green, Yellow, Red };    
        // This is the amount of time for the timer to wait before changing 
        between states
        private const int LIGHT_DURATION = 5000;

        // An actual instance of our enum.
        private States _state;

        // The timer object that is going to be used to switch between states 
        private System.Threading.Timer _timer;

        // This function is called by the timer when it's time for a light to 
        change
        public void lightChanged(){
            System.Console.WriteLine("Light Changed");
            
            //  For each state, move to the next appropriate state.  I.e, red 
            becomes green, etc. 
            switch(_state){
                case States.Green:
                _state = States.Yellow;
                break;

                case States.Yellow:
                _state = States.Red;
                break;

                case States.Red:
                _state = States.Green;
                break;
            }

            // Reset our timer, so this will all happen again and again
            _timer.Change(LIGHT_DURATION,System.Threading.Timeout.Infinite);

            // Call our event.  This is used to communicate with the outside 
            world that our state change occured
            onStateChange(_state);
        }

        // In our constructor we simply set out default state (green) and 
        create/start our timer
        public TrafficLight() {
            _state = States.Green;
            System.Console.WriteLine("Light Created with initial Green state");

            _timer = new System.Threading.Timer( _ => lightChanged(), null, 
            LIGHT_DURATION,
                System.Threading.Timeout.Infinite);
        }

        // these two work together to provide the callback functionality
        // Implementing callback is going to differ greatly from langauge to 
        language
        public delegate void StateChangedResult(States newState);
        public event StateChangedResult onStateChange;
    }

    // Our actual program.  Simply create a traffic light instance
    // Register a callback that will simply print the current state returned 
    when the light state changes
    // And finally wait for the user to hit enter before ending the program
    public class Program
    {
        public static void Main(string[] args)
        {
            TrafficLight light = new TrafficLight();
            light.onStateChange += (TrafficLight.States state) => { Console.
            WriteLine(state); };
            Console.ReadLine();
        }
       
    }
}

The example is pretty well documented in the code above.  Essentially we are creating a class TrafficLight that can internally have one of three states Green, Yellow or Red.  It also implements a timer that switches between those states.  To make the code actually useful, it also implements a callback system so code external to the TrafficLight can interact with it as a black box.  The callback will be passed the current state value every time the light changes.

 

This is obviously a simple example of a state machine but the same basic premise remains regardless to complexity.  It is a very useful data structure for organizing code, especially the flow of logic.  Coupled with callbacks, it is also a great way of keeping systems decoupled as much as possible.

 

The Video

Programming, Design , ,

blog comments powered by Disqus

Month List

Popular Comments