Unity Design Patterns - Finite State Machines

发表于 | 分类于 |

Here is a basic understand on finite state machines in Unity after reading < Game Design Patterns > by Bob Nystorm.

Why State Pattern

Before going into state pattern, we firstly discuss about the following case.
Suppose we have a enemy object which will simply search player and attack him.

1
2
3
4
5
6
7
8
public class Enemy: MonoBehaviour{
    
    ...

    void Update(){
        Attack(SearchPlayer());
    }
}

Here comes one problem. In the above code, the enemy will search for player in each flame, and in most of the time the player is the same one. We want that the enemy keeps searching before finding a target, and once the target is found, it will stop searching and try to attack the player.
In order to realize this, one possible solution is use a ‘if’ statement.

1
2
3
4
5
6
7
8
9
10
11
12
public class Enemy: MonoBehaviour{

    private GameObject target;
    ...

    void Update(){
        if(target)
            Attack(target);
        else
            target = SearchPlayer();
    }
}

Well then suppose the enemy will also search for place to sleep if it doesn’t find a target player.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Enemy: MonoBehaviour{

    private GameObject target;
    private GameObject place;
    ...

    void Update(){
        if(target)
            Attack(target);
        else
            target = SearchPlayer();
            place = SearchPlace();
            if(place)
                Sleep(place);
    }
}

Then comes another problem. What if both a target and a place are found. In this case you should also add another if statement to do the stuff if both of them are found.

And if your enemy has many other behaviours, e.g. talk, patrol and so one. You need to add a lot of if statements and flags to check the state. And it’s not that easy to verify whether your logic is correct or not.

That’s why we would like to use a state pattern to better model your object.

State Pattern

General Definition:

Allow an object to alter its behavior when its internal state changes. The object will appear to change its class.

State pattern is also known as Finite State Machines (FSM) in Unity.
The gist is:

  • State: The object has a state for each time. For each state, specific behaviours are allowed (Enter, Stay, Exit).
  • Action: The behaviours to do when the object enters a new state, stays in a state and exits a previous state.
  • Condition: Condition decides whether the object should move from one state to another state.
  • Transaction: The process when the object moves from one state to another state, which contains a condition and actions.

The workflow can be simply expressed as following:

Initial State -> StayAction() -> Condition() == true -> ExitAction() -> TransactionAction() -> EnterAction() -> New State

General Benefits Using State Pattern

  1. Control your character’s behaviors in a higher level. You design the states and transaction for the FSM, and FSM automatically works on the character. By using FSM, you don’t have to manually do the control.
  2. By using FSM, codes for each state are implemented in state’s class, which is more readable and maintainable.
  3. According to your demands, you can easily create subclass from the base state class and extend the functionalities.

Finite State Machines

Delegation Based

There are two ways to realize a finite state machines.

One is to use delegation to pass all needed variables (Action, Transaction) to the state you create. In this way, you don’t have to use abstract base state class. Instead you instantiate several state instances for your states, and pass your actions and transactions to that instance.

Implementation in Unity:

FSM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

// Defer function to trigger activation condition
// Returns true when transition can fire
public delegate bool FSMCondition();

// Defer function to perform action
public delegate void FSMAction();

// boolean that start the transition


public class FSMTransition {

	// The method to evaluate if the transition is ready to fire
	public FSMCondition Condition;

	// A list of actions to perform when this transition fires
	private FSMAction[] fireActions;

	public FSMTransition(FSMCondition condition, FSMAction[] actions = null) {
		Condition = condition;
		fireActions = actions;
	}

	// Call all  actions
	public void Fire() {
		if(fireActions != null) foreach (FSMAction Action in fireActions) Action();
	}
}

public class FSMState {

	// Arrays of actions to perform based on transitions fire (or not)
	public FSMAction[] enterActions = new FSMAction[0];
	public FSMAction[] stayActions = new FSMAction[0];
	public FSMAction[] exitActions = new FSMAction[0];

	// A dictionary of transitions and the states they are leading to
	private Dictionary<FSMTransition, FSMState> links;

	public FSMState() {
		links = new Dictionary<FSMTransition, FSMState>();
	}

	public void AddTransition(FSMTransition transition, FSMState target) {
		links [transition] = target;
	}

	public FSMTransition VerifyTransitions() {
		foreach (FSMTransition t in links.Keys) {
			if (t.Condition()) return t;
		}
		return null;
	}

	public FSMState NextState(FSMTransition t) {
		return links [t];
	}
	
	// These methods will perform the actions in each list
	public void Enter() { foreach (FSMAction a in enterActions) a(); }
	public void Stay() { foreach (FSMAction a in stayActions) a(); }
	public void Exit() { foreach (FSMAction a in exitActions) a(); }

}

public class FSM {

	// Current state
	public FSMState current;

	public FSM(FSMState state) {
		current = state;
		current.Enter();
	}

	// Examine transitions leading out from the current state
	// If a condition is activated, change the current state and
	// take all the actions linked to:
	// 1. Exit from the current state
	// 2. The activated transition
	// 3. Enter to the new state
	// If no transition is activated, take the actions associated
	// to staying in the current state

	public void Update() { // NOTE: this is NOT a MonoBehaviour
		FSMTransition transition = current.VerifyTransitions ();
		if (transition != null) {
			current.Exit();
			transition.Fire();
			current = current.NextState(transition);
			current.Enter();
		} else {
			current.Stay();
		}
	}
}

Use Example

1
2
3
4
5
6
7
8
9
10
11
12
13
FSMState chasing = new FSMState();
chasing.enterActions = new FSMAction[] { Chase };
chasing.stayActions = new FSMAction[] { Chase };
FSMState killing = new FSMState();
killing.enterActions = new FSMAction[] { Kill };

//Defining transitions
FSMTransition t1 = new FSMTransition(isInDeathRange);
//Link states with transitions
chasing.AddTransition(t1, killing);

//Setup a FSM at initial state
fsm = new FSM(chasing);

This patrern is more suitable for FSM with several states (Usually less than 5). It’s easy to use, and provides nearly all functionalites of FSM. Howerver, there are several disavantages for this delegation way.

  1. By using delegation, all your implementation codes are in one script in an adhoc way. It makes your codebase messy and hard to maintain.
  2. Using only one class for state is not much flexible for inheritance and polymorphism. For example, a hierarchical FSM.

Therefore, a class-based FSM should be more suitable if you want to implement a large FSM structure.

Class Based

In this pattern, state and transaction are in an abstract level. You create your state class derived from the abstract base, and implement your actions in that class. For transaction it’s the same. Just implement the transaction’s decision and actions.

Implementation in Unity:

FSM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using System.Collections;
using System.Collections.Generic;

public abstract class State{
	
	protected Dictionary<Transaction, State> transaction = new Dictionary<Transaction, State> ();

	public void AddTransaction(Transaction _transaction, State _state){
		transaction.Add (_transaction, _state);
	}

	public void RemoveTransaction(Transaction _transaction){
		transaction.Remove (_transaction);
	}

	public KeyValuePair<Transaction, State> CheckTransaction(){
		foreach (KeyValuePair<Transaction, State> kv in transaction) {
			if (kv.Key.Decision ())
				return kv;
		}

		return default(KeyValuePair<Transaction, State>);
	}

	public virtual void Enter () {}
	public virtual void Stay () {}
	public virtual void Exit () {}
}

public abstract class Transaction{

	public virtual void Fire() {}

	public abstract bool Decision ();
}

public class FSMSystem{

	private State state;

	public FSMSystem(State _state){
		state = _state;

		state.Enter ();
	}

	public void Update(){
		KeyValuePair<Transaction, State> kv = state.CheckTransaction ();
		if (!kv.Equals(default(KeyValuePair<Transaction, State>))) {
			state.Exit ();
			kv.Key.Fire ();
			state = kv.Value;
			state.Enter ();
			state.Stay ();
		} else {
			state.Stay ();
		}
	}
}

Derived State and Transaction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class AState : State{

	public override void Enter (){
		AToB tA_B;
		foreach (Transaction t in transaction.Keys) {
			if (t.GetType () == typeof(AToB))
				((AToB)t).time = Time.time;
		}

		Debug.Log ("Enter A");
	}

	public override void Exit(){
		Debug.Log ("Exit A");
	}
}

public class BState : State{

	public override void Enter (){
		Debug.Log ("Enter B");
	}

	public override void Exit(){
		Debug.Log ("Exit B");
	}
}

public class CState : State{

	public override void Enter (){
		Debug.Log ("Enter C");
	}

	public override void Exit(){
		Debug.Log ("Exit C");
	}
}

public class AToB : Transaction{

	public float time = Time.time;
	private float delay = 3.0f;

	public override bool Decision(){
		if (Time.time - time > delay)
			return true;
		else
			return false;
	}
}

public class BToC : Transaction{

	public override bool Decision(){
		if (Input.GetKeyDown (KeyCode.C))
			return true;
		else
			return false;
	}
}

public class CToA : Transaction{

	public override bool Decision(){
		if (Input.GetKeyDown (KeyCode.A))
			return true;
		else
			return false;
	}
}

Use FSM

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class UseFSM : MonoBehaviour {

	private FSMSystem fsm;

	// Use this for initialization
	void Start () {
		AState sA = new AState ();
		BState sB = new BState ();
		CState sC = new CState ();

		AToB tA_B = new AToB ();
		BToC tB_C = new BToC ();
		CToA tC_A = new CToA ();

		sA.AddTransaction (tA_B, sB);
		sB.AddTransaction (tB_C, sC);
		sC.AddTransaction (tC_A, sA);

		fsm = new FSMSystem (sA);
	}
	
	// Update is called once per frame
	void Update () {
		fsm.Update ();
	}
}

You can see that the codebase is more clear and readable. Also it’s easy for you to extend any functionalites for the FSM.

Conclusion

FSM is very useful when:

  1. You have an entity whose behavior changes based on some internal state.
  2. That state can be rigidly divided into one of a relatively small number of distinct options.
  3. The entity responds to a series of inputs or events over time.

FSM is generally used in simple AI or menu architecture (each submenu can be a state). Furthermore, you can also adopt state pattern in everything whose bahaviors differ in different conditions.

For more complex AI, behavior trees and planning systems should be better choices.