Go to Top

In the first part of our tutorial we dig in to the reason for using finite state machines and show an example of the most simple way to implement one: using switch statements.

Getting in a State?

Every program you write is a state machine.  The moment you write an if statement you have created code that can be in at least one of two states - the more code you write the more states the program can be in.  An explosion of switch and if statements can quickly get out of hand, with strange bugs appearing for apparently impossible to fathom reasons as the complexity of the solution increases and interactions between components causes unexpected consequences.  Your project becomes hard to extend and even harder to conceptualise.

When we wrote the Quaternions tutorial which forms the basis of this series, we deliberately allowed the code to expand as it often does when prototyping - building on this logic as a foundation for a real game would probably lead to disaster. It works but its not thought through as well as it might be.  One day we'd hit a brick wall and the feature we desperately wanted for our AI would require massive refactoring to realise.

Finite State Machines are as much a style of programming as they are the code that realises them.  We strongly urge you to consider thinking about your game and everything in it in terms of the states that they can maintain.

What are Finite State Machines?

The clue is in the word finite - in other words: limited, known and understood.  When you build a finite state machine you define clearly all of the states that an object can occupy and you think about the object being in just one of those states at a time.

Thinking about your project in terms of finite state machines helps you conceptualise your game at a higher level, enabling you to keep more of it in your head at one time and more clearly see the path to implementing the killer feature you just thought up or your play testers demanded.

With a finite state machine you may process input differently depending on the state, you might move the object using a different algorithm or display different GUI messages.

Think about a television for a moment - let's consider a simplified case.  A television can be turned off or turned on, when it's on it can be showing a TV programme or it could be displaying a tuning menu.

Mode Remote Control Functions
Off
  • Only the power button has any function.
  • Pressing power moves the TV into the On state.
On
  • Pressing the power button moves the TV to the Off state.
  • Pressing channel buttons changes the programme being received.
  • Pressing the up/down buttons surfs through the channels.
  • Pressing the menu button moves the TV to the Menu state.
Menu
  • Pressing the power button moves the TV to the Off state.
  • Pressing the up/down buttons moves through the menu.
  • Pressing the menu button moves the TV to the On state.

Now clearly the logic that works within those states may have some additional state such as an if statement - but the skill is in making that very limited indeed and quickly inventing another state if the logic would start to get complicated.

For example: you would probably have an if statement to work out if you are on the first menu item when you press the up button and either loop through the menu, or block attempts to move to a previous item.  You could (and purists would say you should) have a  state based on which menu item you were on - but I find that to be overkill and leads to complex coding.

Code legibility and comprehension are the primary factors that you should use when designing software.

Endless indented if statements are not readable and quickly make it a puzzle to work out what is actually happening.

Massive numbers of tiny states make it hard to follow your code and comprehend the possible states of an object.

Mastering this balance is the skill in finite state machine design that this series of tutorials will seek to teach you.

Types of Finite State Machine

Obviously there are a lot of graphical tools that help you build finite state machines - this tutorial is about code based FSMs.  Check out PlayMaker or one of its competitors if you want to use a graphical tool - though they are very much more constrained than the code you can build yourself.

There are really two primary types of code based FSM.

Discoverable FSM/On Demand FSM

Sometimes you only need to know the state of something at a particular time or perhaps for a particular set of purposes.  A discoverable FSM lets you define a state by sampling the environment and resolving it down to a define set of candidate states.

Imagine you have a dishwasher (this is a real example, honest).  You can open the dishwasher, close it and when it's open you can mess with the drawers etc.  There's a control button to open and shut the washer.

When you press the control button you need to know the state of the dishwasher - lets say that it can be shutopen, or drawers open.

Now you don't really define the state of the washer per se - because in its open state the drawers could be anywhere and the effort of testing whether they're open or fully shut would be a lot of processing each time that they moved.  So this could be a good use for a discoverable state machine.

When you press the control button (and potentially at other times) you can have a piece of code sample the state of the washer components and return one of the three states - all other code then uses which ever state is returned.  For example pressing the close button when the drawers are open, first animates the drawers closing, then closes the door.

Using states like this helps you keep your code DRY.
DRY stands for Don't Repeat Yourself and you should try to keep to this motto.

If you have two or more pieces of code that are effectively the same then you will one day end up fixing one of them and forget about the others.  Try to keep your code as DRY as possible and you will find that hard to spot bugs and other head slapping moments are minimised.

Discoverable finite state machines are very simple and are little more than coding practice.  By their nature a discoverable state machine is a simplified model of reality used to make coding decisions easier.  In this tutorial we are going to learn about state transitions, callable sub-states and state injection - none of this will ever apply to the discoverable model.

It's perfectly normal to mix state machine types, DFSMs are a technique that can be employed in circumstances where the if's are getting out of hand, being repeated etc, but the object is too simple to be a candidate for a full state machine.

Functional Finite State Machines

The meat of this tutorial covers functional finite state machines, these are more than a programming technique for added DRYness, they enable you to think about your objects in a different way and can provide amazingly logic pluggability which makes extending your game far easier.

The key difference of an FFSM when compared to a DFSM is that you put objects into a state - which they inhabit until you move them into another state.  FFSMs will frequently perform actions on entering and exiting the state, as well as performing specific logic within a state.

The simplest FFSM is implemented as an enumeration describing the states, a current state variable and a whole bunch of switch statements that implement different logic when the program is in each state.  We are going to start there, but that is just the start, this is going to be a long (and hopefully interesting) journey.

The Tutorial Project

You can download the tutorial project from here.  Be aware that this is the complete tutorial so you can skip ahead and see what's coming.  The Tutorial contains the whole of our Quaternions tutorial but also contains another project folder beneath Tutorial - called unsurprisingly Finite State Machines.

The Part 1 folder will show us building up a state machine framework that takes us through a series of design decisions and technologies that culminate in the final framework and demo game that lives in the Part 2 folder.

The articles in this series will identify which scene is relevant using this:

Part 1/Scene 1

Where We Came In

Scene 1 is the same as the final scene in the Quaternions tutorial and we are focussing on the enemy to start with.

The enemy in this scene is controlled by MovementStateMachine3.

	IEnumerator Start () {

		//Redacted for brevity

		//Loop while this object is alive
		while(true)
		{
			//Wait for a random amount of time between 3 and 9 seconds
			yield return new WaitForSeconds(Random.value * 6f + 3);
			//Check if the enemy is currently asleep
			if(sleeping)	
			{
				//Create a new Zzzzz object above the enemies head
				var newPrefab = Instantiate(sleepingPrefab, _transform.position + Vector3.up * 3f, Quaternion.identity) as Transform;
				//Make sure that the new prefab aligns to the camera
				newPrefab.forward = Camera.main.transform.forward;
			}
		}

	}

The Start function knows a bit about the state of the enemy - it has a coroutine while loop that instantiates Zzzzzz above the head of sleeping enemies, presuming that they are still asleep.  This works fine, but the logic is kind of buried in there.

What happens is that when Start has finished its initialization it enters the while(true) loop, this will keep running for as long as the object is enabled.  The loop checks whether the enemy is sleeping and if it is then it instantiates the prefab.

There's more states and indented ifs in the Update function:

	void Update()
	{
		//Check if something else is in control -
		//later we will have coroutines that basically take control
		//of the enemy and in that case we need to ignore this
		//Update loop
		if(_busy)
			return;
		//Check if the enemy is sleeping
		if(sleeping)
		{
			//If the enemy is asleep then check how far it is from the player
			//we square all of the distances to remove the need for a performance
			//costly square root
			if((_transform.position - _player.position).sqrMagnitude < _attackDistanceSquared)
			{
				//If we are close to the player then turn off sleeping
				sleeping = false;
				//Set the target to be the player, the enemy will move towards this
				target = _player;
				//Where this enemy wants to stand to attack, basically make them sneaky
				//and not approach the player head on
				_attackRotation = Random.Range(60,310);
			}
		}
		else
		{
			//If the target is dead then go back to sleep
			if(!target)
			{
				sleeping = true;
				return;
			}

			//Work out the vector to the target
			var difference = (target.position - _transform.position);
			//Ignore some of the height difference
			difference.y /= 6;
			//Get the size of the vector (squared for performance reasons)
			var distanceSquared = difference.sqrMagnitude;

			//Too far away to care?
			if( distanceSquared > _sleepDistanceSquared)
			{
				//Put the enemy back to sleep
				sleeping = true;
			}
			//Close enough for an attack?
			else if( distanceSquared < _maximumAttackEffectRangeSquared && _angleToTarget < 40f)
			{
				//Start the coroutine that will handle the attack
				//this will disable the Update function for its duration
				StartCoroutine(Attack(target));
			}
			//Otherwise time to move
			else
			{
				//Decide target position by taking where the target is and then
				//projecting a vector in the direction of the attack angle we
				//decided on when we woke up.  Note the length of this vector
				//is 80% of the attacks effective range
				var targetPosition = target.position + (Quaternion.AngleAxis(_attackRotation, Vector3.up) * target.forward * maximumAttackEffectRange * 0.8f);
				//Work out the basic movement towards the target
				var basicMovement = (targetPosition - _transform.position).normalized * speed * Time.deltaTime;
				//Zero out the Y movement as we will adjust for terrain height later
				basicMovement.y = 0;
				//Only move when facing the target - so get the angle between the
				//movement vector and the current heading of the enemy
				_angleToTarget = Vector3.Angle(basicMovement, _transform.forward);
				//Are we within 70 degrees of the taget angle?
				if( _angleToTarget < 70f)
				{
					//If so then move - first give it some gravity
					basicMovement.y = -20 * Time.deltaTime;
					_controller.Move(basicMovement);
				}
			}
		}
	}

We're using a nifty coroutine technique for attacks so the Update function needs to decide whether it's actually in control to start with, if it is then a bunch of nested ifs work out whether its time to wake up or go to sleep; if the enemy is awake then it needs to decide whether to chase or attack the player or one of its rivals.  After that it also handles moving the enemy in the direction of its intended victim.

Again this code works, but I hate it - it's classic prototype stuff that sadly often gets left in for far too long and just messes you up later.  The split of the logic here in Update from that which lives in Start is also confusing - it's not clear what is happening in the sleeping state without reading the whole file.

	IEnumerator Attack(Transform victim)
	{
		//The enemy definitely isn't sleeping now
		sleeping = false;
		//Turn off the Update loop for now
		_busy = true;
		//Make sure the target is the victim we called this function with
		//this allows us to call Attack and specify a new enemy if we want to
		//(not used in the current example)
		target = victim;
		//Enable the attack animation
		_attack.enabled = true;
		//Reset the animation to the start
		_attack.time = 0;
		//Make it have its full weight
		_attack.weight = 1;
		//Wait for half way through the animation
		yield return StartCoroutine(StateMachineBase.WaitForAnimation(_attack, 0.5f));
		//Check if still in range
		if(victim && (victim.position - _transform.position).sqrMagnitude < _maximumAttackEffectRangeSquared)
		{
			//Apply the damage
			victim.SendMessage("TakeDamage", 1 + Random.value * 5, SendMessageOptions.DontRequireReceiver);
		}
		//Wait for the end of the animation
		yield return StartCoroutine(StateMachineBase.WaitForAnimation(_attack, 1f));
		//Stop the attack animation having any impact
		_attack.weight = 0;
		//Re-enable the Update loop
		_busy = false;
	}

Calling Attack changes the state of the object, because it affects sleeping, but it might also be called due to state machine processing in Update - that's the problem with ifs - they are far too easy to modify and leave the object in a potentially valid, but hard to define state.  What will happen is down to either head scratching or lots of testing.  The next thing it does is affect _busy - so that affects the processing of Update too, while sleeping affects both Update and Start - confused yet?

I could go on, but I won't.  I think you can agree this perfectly functional piece of code is really a disaster waiting to happen.

Our First Functional Finite State Machine

Ok, let's resolve to think more carefully about our enemies, define some states and put them into a single state at a time.

Our enemies can be in one of these states: sleeping, following, attacking, being hit or dying.

We really want our states to work like this:

Part 1/Scene 2

We have create the file FiniteStateMachine1.cs and in that file the first thing we need to do is create an enumeration that defines our states:

	
	public enum EnemyStates
	{
		sleeping = 0,
		following = 1,
		attacking = 2,
		beingHit = 3,
		dying = 4
	}

	public EnemyStates currentState = EnemyStates.sleeping;

Woo hoo we're on our way!  Right now we need to change all of the logic to support only being in one state at a time and to centralise our processing so its easier to find the code that relates to each state.

To do this simply we've get rid of our fancy coroutine stuff so we can concentrate on the code unification.  So it's goodbye to Start, Attack, Hit and Dead being a coroutines and hello to a switch statement and a few new variables that we need to make up for the missing coroutine functionality.  Nearly everything happens in Update now:

	void Update()
	{
		//Run code based on which state is currently active
		switch(currentState)
		{
		case EnemyStates.sleeping:
			//The enemy is sleeping

			//Check the current time against the time for the next Zzzzz to appear
			if(timeOfNextZZZZ < Time.time)
			{
				//If its time then create the sleeping prefab above the enemies
				//head
				var newPrefab = Instantiate(sleepingPrefab, _transform.position + Vector3.up * 3f, Quaternion.identity) as Transform;
				newPrefab.forward = Camera.main.transform.forward;
				//Calculate a time between 2 and 8 seconds for the next
				//Zzzzz
				timeOfNextZZZZ = Time.time + 2 + (6 * Random.value);
			}
			//Now check if the player has appraoched, using sqrMagnitude to avoid
			//a performance expensive square root
			if((_transform.position - _player.position).sqrMagnitude < _attackDistanceSquared)
			{
				//Move the enemy into the following state
				currentState = EnemyStates.following;
				//Make the enemy target the player
				target = _player;
				//Where this enemy wants to stand to attack
				_attackRotation = Random.Range(60,310);
			}
			break;

		case EnemyStates.following:
			//The enemy is following a target

			//If the target has been destroyed then we go back to sleep
			//(Destroyed objects return null and false)
			if(!target)
			{
				currentState = EnemyStates.sleeping;
				return;
			}
			//Calculate the vector to the target
			var difference = (target.position - _transform.position);
			//Ignore a big part of the height difference by dividing it
			//by 6
			difference.y /= 6;
			//Calculate the square of the distance (avoid expensive square root)
			var distanceSquared = difference.sqrMagnitude;

			//Too far away to care?
			if( distanceSquared > _sleepDistanceSquared)
			{
				//If we've got too far away then go to sleep
				currentState = EnemyStates.sleeping;
				return;
			}

			//Close enough to attack
			if( distanceSquared < _maximumAttackEffectRangeSquared && _angleToTarget < 60f)
			{
				//Move the enemy into the attacking state
				currentState = EnemyStates.attacking;
				//Enable the attack animation
				_attack.enabled = true;
				//Reset the animation to the start
				_attack.time = 0;
				//Make the animation just play once and hold
				//this is so .normalizedTime will become =1
				_attack.wrapMode = WrapMode.ClampForever;
				//Make the attack animation full power
				_attack.weight = 1;
				//Indicate that we have yet to strike the target
				hasStruckTarget = false;

				return;
			}

			//Move towards the target

			//First decide target position based on the angle of attack we decided on waking up
			var targetPosition = target.position + (Quaternion.AngleAxis(_attackRotation, Vector3.up) * target.forward * maximumAttackEffectRange * 0.8f);
			//Calculate the basic movement toward the target
			var basicMovement = (targetPosition - _transform.position).normalized * speed * Time.deltaTime;
			//Zero out the y movement so we can get a bearing angle
			//we will apply gravity later
			basicMovement.y = 0;

			//Only move when facing the target - so calculate
			//the angle between the heading of the enemy and the target
			_angleToTarget = Vector3.Angle(basicMovement, _transform.forward);
			//Only move the enemy if it is within 70 degrees
			if( _angleToTarget < 70f)
			{
				//Provide some gravity
				basicMovement.y = -20 * Time.deltaTime;
				_controller.Move(basicMovement);
			}

			break;
		case EnemyStates.attacking:
			//The enemy is attacking

			//Work out if we are half way through the animation and haven't
			//yet added any damage to the target
			if(!hasStruckTarget && _attack.normalizedTime > 0.5f)
			{
				//Ready to hit, so flag that it is done so we
				//only come in here once
				hasStruckTarget = true;
				//Check if still in range
				if(target && (target.position - _transform.position).sqrMagnitude < _maximumAttackEffectRangeSquared)
				{
					//Apply the damage
					target.SendMessage("TakeDamage", 1 + Random.value * 5, SendMessageOptions.DontRequireReceiver);
				}

			}
			//See if the animation is complete yet (normalizedTime will be 1)
			if(_attack.normalizedTime >= 1 - float.Epsilon)
			{
				//Set the state of the enemy based on whether the target is
				//dead or not
				currentState = target ? EnemyStates.following : EnemyStates.sleeping;
				//Make sure the animation has no effect
				_attack.weight = 0;
			}
			break;

		case EnemyStates.beingHit:
			//The enemy is being hit

			//Check whether the animation is complete
			if(_hit.normalizedTime >= 1 - float.Epsilon)
			{
				//Animation is complete so set the state based on whether
				//the enemy is still alive (in which case chase it).
				currentState = target ? EnemyStates.following : EnemyStates.sleeping;
			}
			break;

		case EnemyStates.dying:
			//Wait for the end of the death animation
			if(_die.normalizedTime >= 1 - float.Epsilon)
			{
				//Animation is complete, destroy the enemy
				Destroy(gameObject);
			}
			break;
		}

	}

Our code has become far more legible - we can clearly see the logic that is being applied in each state - at least as far as the game loop is concerned.  We've also added code to our trigger - but again, it's fairly clear to see which states it is going to be used in.

	void OnTriggerEnter(Collider hit) 
	{
		//Make sure that we are not impacting another collider on the same object
		if(hit.transform == _transform)
			return;
		//Choose what to do based on the state
		switch(currentState)
		{
		case EnemyStates.sleeping:
		case EnemyStates.following:
			//Have we hit the player?
			if(hit.transform == _player)
			{
				//If the player is in the trigger then start following him
				target = _player;
				currentState = EnemyStates.following;
			}
			else
			{
				//See if the thing we hit has an EnemyMood
				var rival = hit.transform.GetComponent<EnemyMood>();
				if(rival)
				{
					//If the item hit has an EnemyMood then it is an
					//enemy 
					//Get a random number and see if it is bigger than
					//the mood - so the lower the mood the more likely
					//it is that the subsequent code will run
					if(Random.value > _mood.mood/100)
					{
						//We are going to attack this other enemy
						target = hit.transform;
						currentState = EnemyStates.following;
					}
				}
			}
			break;
		}

	}

And we can also clearly see the state transitions and we know exactly what will happen in the game loop and the trigger when each state is activated.

So that's it then right? A fully working FFSM, clearly a much better basis for development than our hotch-potch of cool ideas we had before...

Actually there are still some problems - let's face it those switch statements can get pretty big, we might forget which routine we were in if there were many more (is this Update? Trigger?) also each new state means another check for an enumeration value which is all taking some time.  It would be much nicer to have our code for each state together too - not split by the code for a massive number of other states (already it takes a while to get from the Sleeping Update logic to the Sleeping Trigger logic and there's only so many times you can punch your page up and page down keys before they fail!)   Perhaps more importantly it is hard to hold the entirety of logic for a particular state in your head when you have to scroll so much to see it all.

In fact what if you could write your code like this instead:

	#region Sleeping

	IEnumerator Sleeping_EnterState()
	{
		while(true)
		{
			yield return new WaitForSeconds(Time.time + 2 + (6 * Random.value));
			var newPrefab = Instantiate(sleepingPrefab, transform.position + Vector3.up * 3f, Quaternion.identity) as Transform;
				newPrefab.forward = Camera.main.transform.forward;

		}
	}

	void Sleeping_Update()
	{
		if((transform.position - _player.position).sqrMagnitude < _attackDistanceSquared)
		{
			target = _player;
			//Where this enemy wants to stand to attack
			_attackRotation = Random.Range(60,310);

			currentState = EnemyStates.Following;

		}
	}

	void Sleeping_OnTriggerEnter(Collider hit)
	{
		Following_OnTriggerEnter(hit);
	}

	#endregion

Wouldn't that be cool - it's all together, no switch statements just clean unindented code.  It's really easy to see where you are and what other logic applies to your current state.  We can even use some of those cool coroutine techniques!

In the second article in this series we will see exactly how we can achieve that functionality and build upon a framework to make something much more performant that our ever growing switch statements.  Get ready to learn about reflection caching and delegates, because we're going to need them to make our FSM framework fly.

Video

You can watch the following video to see the scenes in action and get some more insight into these first steps in creating an FSM framework.

, , , , ,

11 Responses to "Finite State Machine Tutorial #1"

  • PallidFingers
    February 20, 2013 - 6:13 am Reply

    The project crashes on import :(

  • sKipper
    March 11, 2013 - 8:50 am Reply

    How do you handle two states being valid at the same time? If the player and the enemy are standing and fighting each other then both the ‘attacking’ and ‘Being Hit’ states will be true. Which state will the player be in?

    • whydoidoit
      March 11, 2013 - 9:38 am Reply

      Well each individual can only be in one state, but there’s no reason why two individuals can’t be using the same script but be in different states (as they each have their own copy of the variables).

      • sKipper
        March 14, 2013 - 4:58 am Reply

        I meant that if the player is attacking and the enemy is hitting him back then the player will be in both states: ‘attacking’ and ‘being hit’.

        I guess the frame in which the player gets hit he will be in the ‘being hit’ state and not in the ‘attacking’ sate. But only for that one frame. Before that frame and after that frame he will be in ‘attacking’ state right?

        • whydoidoit
          March 16, 2013 - 11:02 am Reply

          I would presume that as the player is being hit, he cannot be attacking – the attack would be aborted.

          The other choice is to have 2 state machines, one that controls attacking and one that controls the body of the player. That’s not a great idea in my mind. You might also consider not having a being hit state if all you want to do is decrease some health and flash the screen or something – that’s fine, the point of a being hit state is to allow the abort on the attack state.

          The point of an FSM is to be in control by having a finite set of states. If you are being hit, normally you are no longer able to attack. You might as you are exiting the attacking state want to wildly fire the weapon etc.

          • whydoidoit
            March 16, 2013 - 11:03 am

            You could also automatically renter the attacking state as you exit the being hit state (after an ouch animation, or a judder).

      • Jim
        March 16, 2013 - 3:35 am Reply

        I have the same question of sKipper ,

        what if two states happen in the same time?

        • hawken king
          February 18, 2014 - 2:10 pm Reply

          State machines are linear in some respects, the case leading another case is always the winner. So if the case attacking state is above the hit state, that would be chosen before the hit state, however on the next cycle of the cpu, if the hit state becomes true, it would be chosen as the state above it is now false.

          switch (thing)
          case thing1:
          case thing2:

          thing2 can never happen before thing1.

    • Sceceron
      May 11, 2013 - 5:27 am Reply

      you must have only one state at the time, you have to decide if the being hit go primary over the attacking, It must always send you to one state at the time. Depending of the type of game you are coding for ex: hack and slash, the attack should be a priority for the avatar/player, but in a zelda like game you may prefer to have the being hit in priority. This is more a design decision than a coding problem.

  • Martin Whittington
    May 16, 2013 - 7:36 am Reply

    Can I ask about the #region tags around Sleeping?

    Does including the region tags allow the prefixing of the tag to the functions e.g. Sleeping_Update?

    Or is it just a method to keep relevant code together?

    • whydoidoit
      May 16, 2013 - 10:14 am Reply

      It just lets you collapse the region in the editor to make viewing the source easier…

Leave a Reply