Simple FSM Framework Part 2: More on Actions

The FSM framework described in part 1 requires the user to make action classes. These action classes can then be reused in any state. This makes the framework very extensive and flexible. This is actually my favorite feature in Playmaker. Playmaker comes with a wide collection of premade action classes. At the same time, you can also add your own actions by extending a base class and the FSM editor can pick up these new actions. A framework of my own has to have the same system.

The following is one of my generic actions:

	public class MoveAction : FsmAction {

		private Transform transform;
		private Vector3 positionFrom;
		private Vector3 positionTo;
		private float duration;
		private string timeReference;
		private string finishEvent;
		private Space space;

		private CountdownTimer timer;

		public MoveAction(FsmState owner) : base(owner) {
			this.timer = new CountdownTimer(1); // uses default time reference
		}

		public MoveAction(FsmState owner, string timeReferenceName) : base(owner) {
			this.timer = new CountdownTimer(1, timeReferenceName);
		}

		public void Init(Transform transform, Vector3 positionFrom, Vector3 positionTo, float duration, string finishEvent, Space space = Space.World) {
			this.transform = transform;
			this.positionFrom = positionFrom;
			this.positionTo = positionTo;
			this.duration = duration;
			this.finishEvent = finishEvent;
			this.space = space;
		}

		public override void OnEnter() {
			if(Comparison.TolerantEquals(duration, 0)) {
				Finish();
				return;
			}

			if(VectorUtils.Equals(this.positionFrom, this.positionTo)) {
				// positionFrom and positionTo are already the same
				Finish();
				return;
			}

			SetPosition(this.positionFrom);
			timer.Reset(this.duration);
		}

		public override void OnUpdate() {
			timer.Update();

			if(timer.HasElapsed()) {
				Finish();
				return;
			}

			// interpolate position
			SetPosition(Vector3.Lerp(this.positionFrom, this.positionTo, timer.GetRatio()));
		}

		private void Finish() {
			// snap to destination
			SetPosition(this.positionTo);

			if(!string.IsNullOrEmpty(finishEvent)) {
				GetOwner().SendEvent(finishEvent);
			}
		}

		private void SetPosition(Vector3 position) {
			switch(this.space) {
			case Space.World:
				this.transform.position = position;
				break;

			case Space.Self:
				this.transform.localPosition = position;
				break;
			}
		}

	}

It’s basically an action that moves an object from point A to B at some duration. It also accepts a “Finished” event such that when the action is done, it sends/triggers this event towards the owning FSM which may cause a state change.

This is how it can be used:

        private void PrepareFsm() {
            // States
            FsmState goHome = fsm.AddState("GoHome");
            ...

            // GoHome actions
            {
                MoveAction move = new MoveAction(goHome);
                float duration = homeDistance / this.moveSpeed; // Calculate duration by speed
                move.Init(this.transform, this.transform.position, homePosition, duration, FINISHED);

                goHome.AddAction(move);
            }

            ...
        }

There are a lot of generic actions with this flavor. I have actions like RotateToTarget, ScaleByDuration, SetColorByDuration, TimedWait, etc. The good thing is I only have to write these actions once and they can be reused in any game.

Generic Delegate Action

So far I’ve shown that writing reusable action classes are good. They can also be bad. One of my gripes in Playmaker is making action classes that only uses single calls to other components. In my framework, I used to write action classes like this:

    public class Fire : FsmAction {

        private Ship ship;
        private string finishEvent;

        public Fire(FsmState owner, Ship ship, string finishEvent) : base(owner) {
            this.ship;
            this.finishEvent = finishEvent;
        }

        public override void OnEnter() {
            ship.Fire();
            GetOwner().SendEvent(this.finishEvent);
        }

    }

The only significant call here is ship.Fire(). But since I have to interface with the framework, I have to make a new class for it. Not only is this verbose, it kills productivity. This single line calls in an FSM happens a lot.

To fix this, I made a generic action that accepts delegates for its OnEnter(), OnUpdate(), and OnExit() routines. This way, I could call one liners such as ship.Fire() through an anonymous method thus avoiding making a new class altogether.

	public class FsmDelegateAction : FsmAction {

		public delegate void FsmActionRoutine(FsmState owner);

		private FsmActionRoutine onEnterRoutine;
		private FsmActionRoutine onUpdateRoutine;
		private FsmActionRoutine onExitRoutine;

		public FsmDelegateAction(FsmState owner, FsmActionRoutine onEnterRoutine) : this(owner, onEnterRoutine, null, null) {
		}

		public FsmDelegateAction(FsmState owner, FsmActionRoutine onEnterRoutine, FsmActionRoutine onUpdateRoutine, FsmActionRoutine onExitRoutine = null) : base(owner) {
			this.onEnterRoutine = onEnterRoutine;
			this.onUpdateRoutine = onUpdateRoutine;
			this.onExitRoutine = onExitRoutine;
		}

		public override void OnEnter() {
			if(onEnterRoutine != null) {
				onEnterRoutine(GetOwner());
			}
		}

		public override void OnUpdate() {
			if(onUpdateRoutine != null) {
				onUpdateRoutine(GetOwner());
			}
		}

		public override void OnExit() {
			if(onExitRoutine != null) {
				onExitRoutine(GetOwner());
			}
		}

	}

Now instead of making a new Fire action class, I could just use this action instead:

        // Say the Fsm instance is inside the Ship component
        private void PrepareFsm() {
            // States
            ...
            FsmState fire = fsm.AddState("Fire");
            ...

            // Fire actions
            {
                fire.AddAction(new FsmDelegateAction(fire, delegate(FsmState owner) {
                    Fire();
                    owner.SendEvent(FINISHED);
                }));
            }

            ...
        }

This is less verbose. I’m still interfacing with the framework but with less code. Most FSM actions don’t need to be a class of their own. If they need to be, then sure we could refactor that in another action class.

This is how a code based FSM becomes more interesting than an editor based one. You can do manipulations in code that you cannot do in an editor. You can manage the FSM better. You gain a lot of options to organize FSMs through code.

Advertisements

Simple FSM Framework Part 1: The Making

I remember a project which I lead that heavily used Playmaker for its systems. This was the time when Playmaker was still in its first couple of months and I got pretty excited when I tried it. For those of you who are not familiar, Playmaker is a Unity asset that helps you create FSM graphs and add functionality without code. It got so popular that it has become the leading “visual scripting” asset of Unity.

Short version of the story: that project became a disgusting pile of mess. The messiness of FSM wiring is way worse than spaghetti code. At least code could be refactored. It was so bad that I vow not to primarily use visual scripting to run the complex systems of a game ever again.

A part of Defender unit FSM. Looks like spaghetti, yum!
This is not part of that project but you get the idea.

However, I didn’t hate Playmaker. It showed a good data model on how a finite state machine works that can be applied to games. So I made my own bare bones FSM framework based from it so that I can still make FSM graphs through code. Used wisely, FSMs can be a great way to organize simple behavior. I’ve been using this framework ever since. I’m still using Playmaker but only as a visual reference. All of my FSMs are now in code.

I’m going to show you how I did it in this post. There will be no github repository for this because honestly, I’m too lazy to extract it from my library. My intent is to have you read code so you can make your own FSM framework and hopefully improve it on your own.

High Level Design

My design is based on Playmaker’s model. These are the main concepts:

  • FsmAction – Represents an action that is executed/executing on a single state
  • Events – It is that thing that causes state change. This can be easily represented as strings.
  • FsmState – Represents a state in the FSM. It has a collection of actions and transitions.
  • Transitions – Represents the link to another state. This can be easily represented as a pair of event (string) and FsmState.
  • Fsm – Contains a certain set of FsmState instances that comprises a single FSM graph. Provides methods to send events and thus changes the current state.

FsmAction Code

An FsmAction is just a base class for concrete actions to implement. The way the framework is used is that there will be a collection of predefined action classes that can be used such as Move, Rotate, TimedWait, etc. At the same time, custom actions could also be implemented. Obvious examples are actions that are specific to a game.

public abstract class FsmAction {

    private readonly FsmState owner;

    public FsmAction(FsmState owner) {
        this.owner = owner;
    }

    public FsmState GetOwner() {
        return owner;
    }

    public virtual void OnEnter() {
        // may or may not be implemented by deriving class
    }

    public virtual void OnUpdate() {
        // may or may not be implemented by deriving class
    }

    public virtual void OnExit() {
        // may or may not be implemented by deriving class
    }

}

This is pretty straightforward. The most important here are the three methods. OnEnter() is invoked when a state has been entered. OnUpdate() is called repeatedly every frame while on a certain state. OnExit() is invoked when the current state will be changed to a new one. The member FsmState is needed so that actions can send events to it (change the current state).

Why is it not an interface? The intent is that actions should be small modular classes deriving from FsmAction. An existing big class, say some kind of big manager, can’t just implement an interface and use that big class as an FsmAction. This also prevents usage of MonoBehaviour classes as FsmAction instances.

FsmState Code

FsmState is just a collection of actions and transitions to other states. It provides the methods appropriate to setup states.

public class FsmState {

    private readonly string name;
    private readonly Fsm owner;

    // Transitions are just pairs of event and FsmState
    // Events are just strings
    private readonly Dictionary<string, FsmState> transitionMap = new Dictionary<string, FsmState>();

    private readonly List<FsmAction> actionList = new List<FsmAction>();

    public FsmState(string name, Fsm owner) {
        this.name = name;
        this.owner = owner;
    }

    public string Name {
        get {
            return name;
        }
    }

    public void AddTransition(string eventId, FsmState destinationState) {
        // can't have two transitions for the same event
        Assertion.Assert(!transitionMap.ContainsKey(eventId), string.Format("The state {0} already contains a transition for event {1}.", this.name, eventId));
        transitionMap[eventId] = destinationState;
    }

    public FsmState GetTransition(string eventId) {
        // May return null if there's no such transition
        return transitionMap.Find(eventId);
    }

    public void AddAction(FsmAction action) {
        Assertion.Assert(!actionList.Contains(action), "The state already contains the specified action.");
        Assertion.Assert(action.GetOwner() == this, "The owner of the action should be this state.");
        actionList.Add(action);
    }

    public IEnumerable<FsmAction> GetActions() {
        return actionList;
    }

    public void SendEvent(string eventId) {
        // Just delegate to the owner Fsm
        this.owner.SendEvent(eventId);
    }

}

Fsm Code

Fsm is like the central hub of the framework. You make an instance of this class then it provides methods to create FsmState instances. Those FsmState instances can then be setup to your liking (actions and transitions).

public class Fsm {

    private readonly string name;

    private FsmState currentState;

    // Collection of all states using the state name as key
    private readonly Dictionary<string, FsmState> stateMap = new Dictionary<string, FsmState>();

    public Fsm(string name) {
        this.name = name;
        currentState = null;
    }

    public string Name {
        get {
            return name;
        }
    }

    public FsmState AddState(string name) {
        // state names should be unique
        Assertion.Assert(!stateMap.ContainsKey(name), "The FSM already contains a state with the specified name: " + name);

        FsmState newState = new FsmState(name, this);
        stateMap[name] = newState;
        return newState;
    }

    private delegate void StateActionProcessor(FsmAction action);

    private void ProcessStateActions(FsmState state, StateActionProcessor actionProcessor) {
        FsmState stateOnInvoke = this.currentState;

        IEnumerable<FsmAction> actions = state.GetActions();
        foreach(FsmAction action in actions) {
            actionProcessor(action);

            if(this.currentState != stateOnInvoke) {
                // this means that the action processing caused a state change
                // we don't continue with the rest of the actions
                break;
            }
        }
    }

    public void Start(string stateName) {
        FsmState state = stateMap.Find(stateName);
        Assertion.AssertNotNull(state);
        ChangeToState(state);
    }

    private void ChangeToState(FsmState state) {
        if(this.currentState != null) {
            // if there's an active current state, we exit that first
            ExitState(this.currentState);
        }

        this.currentState = state;
        EnterState(this.currentState);
    }

    private void EnterState(FsmState state) {
        ProcessStateActions(state, delegate(FsmAction action) {
            action.OnEnter();
        });
    }

    private void ExitState(FsmState state) {
        FsmState currentStateOnInvoke = this.currentState;

        ProcessStateActions(state, delegate(FsmAction action) {
            action.OnExit();
            if(this.currentState != currentStateOnInvoke) {
                // this means that the action's OnExit() causes the FSM to change state
                // note that states should not change state on exit
	        throw new Exception("State cannot be changed on exit of the specified state.");
            }
        });
    }

    public void Update() {
        if(this.currentState == null) {
            return;
        }

        ProcessStateActions(this.currentState, delegate(FsmAction action) {
            action.OnUpdate();
        });
    }

    public FsmState GetCurrentState() {
        return this.currentState;
    }

    public void SendEvent(string eventId) {
        if(currentState == null) {
            Debug.LogWarning(string.Format("Fsm {0} does not have a current state. Check if it was started.", this.name));
            return;
        }

        FsmState transitionState = this.currentState.GetTransition(eventId);
        if(transitionState == null) {
            #if UNITY_EDITOR
            // log only in Unity Editor since it lags the game even if done in build
            Debug.LogWarning(string.Format("The current state {0} has no transtion for event {1}.", this.currentState.GetName(), eventId));
            #endif
        } else {
            ChangeToState(transitionState);
        }
    }

}

The only thing special here is ProcessStateActions(). It is the common algorithm for traversing state actions. I made it this way so I don’t have to repeat this pattern whenever I traverse state actions. As you can see here, it is invoked in EnterState(), ExitState(), and Update().

This is pretty much it. The FSM framework is done.

How to use?

Let’s just say we’re making a runner game and we are developing the main runner character. Let’s say the following would be its FSM behavior graph:

RunnerFsm

This is self explanatory. That starting state would be the character running. When Jump event triggers, like the player presses the jump button, it goes to jumping state. From jumping, if it hits the ground, it goes back to running state. If it hits an obstacle, then it dies.

Their are many ways to use the framework. The most common one is to use it in a MonoBehaviour. This is how it is then set up:

public class RunnerCharacter : MonoBehaviour {

    [SerializeField]
    private float moveSpeed;

    private Fsm fsm = new Fsm("RunnerCharacter");

    private void Awake() {
        PrepareFsm();
    }

    // Only keeping constant of the starting state since it will be needed for starting the FSM
    private const string RUNNING = "Running";

    // Events
    private const string JUMP = "Jump";
    private const string HIT_GROUND = "HitGround";
    private const string HIT_OBSTACLE = "HitObstacle";

    private void PrepareFsm() {
        // States
        FsmState running = fsm.AddState(RUNNING);
        FsmState jumping = fsm.AddState("Jumping");
        FsmState die = fsm.AddState("Die");

        // Actions

        // Running
        {
            MoveConstantly move = new MoveConstantly(running);
            move.Init(this.transform, this.moveSpeed);
            running.AddAction(move);

            TriggerAnimator animationTrigger = new TriggerAnimator(running, "Run");
            running.AddAction(animationTrigger);
        }

        // Jumping
        {
            JumpAction jump = new JumpAction(jumping);
            jumping.AddAction(jump);

            TriggerAnimator animationTrigger = new TriggerAnimator(running, "Jump");
            running.AddAction(animationTrigger);
        }

        // Die
        {
            TriggerAnimator animationTrigger = new TriggerAnimator(running, "Die");
            running.AddAction(animationTrigger);
        }

        // Transitions
        running.AddTransition(JUMP, jumping);
        running.AddTransition(HIT_OBSTACLE, die);

        jumping.AddTransition(HIT_GROUND, running);

        // Auto start the FSM (sometimes it may be started else where)
        // Start() can be invoked anywhere like respawning a character
        this.fsm.Start(RUNNING);
    }

    private void Update() {
        // Process input
        if(Input.GetKeyDown(KeyCode.Space)) {
            this.fsm.SendEvent(JUMP);
        }

        // Don't forget to update
        this.fsm.Update();
    }

    private void OnCollisionEnter(Collision collision) {
        if(...) {
            // Collided with ground
            this.fsm.SendEvent(HIT_GROUND);
        }

        if(...) {
            // Collided with obstacle
            this.fsm.SendEvent(HIT_OBSTACLE);
        }
    }

}

I usually make a method for preparing the FSM. I usually name it PrepareFsm() and invoked on Awake(). In PrepareFsm(), I perform 3 preparations which are the states, actions, and transitions. I make the states first because those instances are needed when adding transitions. The classes MoveConstantly, JumpAction, and TriggerAnimator are defined FsmAction classes.

Events are natural candidates to become constants. They can be made as public if you want to expose the sending of events from other parts of the program. However, I don’t recommend that.

Every time you want to change the state, you just have to call Fsm.SendEvent() as can be seen here in Update() and OnCollisionEnter().

A common use case is to determine what the current state is. This can be done by caching the added state in a member variable instead of a local one. The cached state can then be compared with the state returned with Fsm.GetCurrentState().

private FsmState running;

private void PrepareFsm() {
    // States
    this.running = fsm.AddState(RUNNING); // Cache in member variable
    FsmState jumping = fsm.AddState("Jumping");
    FsmState die = fsm.AddState("Die");

    ...
}

private void Update() {
    // Process input
    if (Input.GetKeyDown(KeyCode.Space)) {
        if (this.fsm.GetCurrentState() == this.running) {
            // Jump only when on running state
            this.fsm.SendEvent(JUMP);
        }
    }

    this.fsm.Update();
}

This looks more tedious than Playmaker.

It is but it’s more useful for me. The reason I made the framework is so that I don’t have to use Playmaker if I ever do need FSMs. It forces me to ground my work using code. I’m afraid that if I start using Playmaker, it will creep out of control and will eventually become unmanageable. With FSMs done in code, I can apply a lot of tricks to make them manageable. Or if the FSM itself is messy, I could opt to refactor the whole thing without dealing with a Playmaker graph.

A Better A* Interface

I have made my own A* framework around 2012. I still use the same code until now. It has been improved a lot of times already but one thing that didn’t change much is the interface. What I mean by ‘interface’ here is the collection of public classes, methods, and interfaces to access the framework. In this post, I’m showing how I did it. First, I’ll show you the method that executes the A* search:

public void ResolvePath(AStarPath<T> path, NodeHandle<T> start, NodeHandle<T> goal, HeuristicCostCalculator<T> calculator, Reachability<T> reachability = null) {
    ...
}

I’m no longer showing the code on how A* works. There are better resources about that else where. What I’m focusing here is the interface and why I did it that way.

First thing you’ll notice is I’m using a generic type variable. This is important because each game or problem domain has its own way of representing their positions be it tiles or waypoints. It also implies that the algorithm should work for any type of position.

Let’s discuss the parameters:

AStarPath path – This is simply a custom class that contains the sequence of T items. It also stores whether the path is reachable or not. The method stores the A* search result in this object. It was done this way to prevent instantiating this class whenever an A* search is needed. The client code is required to maintain an instance of this class. The caller would then also use this class to traverse the path.

NodeHandle start – The start node (self explanatory). NodeHandle has methods related to adding neighbors or connected nodes. Underneath, it is implemented as a graph node.

NodeHandle goal – The goal node (self explanatory).

HeuristicCostCalculator calculator – This is the cost calculator to use during algorithm execution. Will explain the details later. I provided this interface because different problem domains have different implementations of such calculation.

Reachability reachability – Reachability is an interface that tells whether or not a tile is reachable or not. Will explain the details later. I provided such interface because there are instances where reachability differs in case to case basis. Reachability is optional because it may not be needed at all times. Most use cases for A* is really just shortest path.

HeuristicCostCalculator

HeuristicCostCalculator is implemented as an interface. It looks like this:

public interface HeuristicCostCalculator<T> {
    // Computes the heuristic cost from the specified starting position and the goal.
    float ComputeCost(T start, T goal);
}

Basically, it just computes the heuristic cost given two arbitrary positions. As you know, the heuristic cost is important to the algorithm. Without it, it’s no longer A*.

Reachability

Reachability is also implemented as an interface:

public interface Reachability<T> {
    // A reachability check on a single position
    // This is used to check if a goal is reachable at all
    // If not, the search ends abruptly
    // This is to avoid useless search when the position can't be reached at all
    bool IsReachable(T position);

    // Returns whether or not the specified movement of these two nodes is reachable. 
    bool IsReachable(T from, T to);
}

There are two methods. The first one with only one position parameter is used as a quick check to see if the position is reachable at all. For example, in a tile based game, if the tile has a blocker and thus unreachable, A* can be dropped. Or in another case, a tile is free but all its neighbors are blocked. If the position is not reachable, A* search may no longer be needed.

The second one with two parameters is used while the algorithm is being executed. The parameters are not necessarily the starting and goal nodes. The parameters passed here are nodes that are considered during the A* search. There are times where reachability changes for a certain pair of nodes.

For example, in our game Academia, when a tile is blocked, an agent can’t move diagonally along the tile’s diagonal neighbors like moving from bottom neighbor to right neighbor. The agent has to go through the right neighbor of the bottom tile first then move up to the right neighbor of the newly blocked tile. The bottom neighbor and the right neighbor are reachable by their graph node setup (we allow diagonal movement). By using the reachability interface, we can override this rule and mark the pair as unreachable because of the presence of such blocked tile.

Reachability
Moving from chair to water fountain is not allowed because of the wall. Agent has to go from chair to trash can then to water fountain.

Different games may also have game rules that override the graph node setup. A simple example I can think of is say land tile that is connected to a water tile. Only amphibian units can pass from land to water but not land only units. The Reachability interface can be used to express these rules.

Usage

This is how our A* class is then used:

// Say Tile is our "position" class
AStar<Tile> astar = new AStar();

// Prepare node handles
foreach(Tile tile in tileMap) {
    tile.NodeHandle = astar.Add(tile);
}

// Prepare neighbors
foreach(Tile tile in tileMap) {
    foreach(Tile neighbor in tile.Neighbors) {
        // TileLink here stores the weight for moving from the tile to the neighbor
        tile.NodeHandle.AddPath(neighbor.Handle, new TileLink(tile, neighbor));
    }
}

// To use A* search
AStarPath<Tile> path = new AStarPath<Tile>();
Tile start = ResolveStartTile(); // Let's just say this is how we resolve the starting tile
Tile goal = ResolveGoalTile();

// Say MyHeuristicCalculator and MyReachability are implemented as singletons
astart.ResolvePath(path, start.NodeHandle, goal.NodeHandle, MyHeuristicCalculator.Instance, MyReachability.Instance);

// Use the path if reachable or do something else if not
if(path.Reachable) {
    foreach(Tile tile in path) {
        MoveToTile(tile); // It's not really like this in an actual game but you get the idea
    }
}

GOAP Extensions

We use GOAP for our AI in Academia. It’s working well for us so far. New behaviour can be easily added and AI glitches can be easily fixed. But I’ve had problems with it as well. One of them which needed fixing is duplicate actions.

We use GOAP for our AI in Academia. It’s working well for us so far. New behaviour can be easily added and AI glitches can be easily fixed. But I’ve had problems with it as well. One of them which needed fixing is duplicate actions.

We have different classes of characters in the game. We have students, teachers, workers, cooks, nurses, and janitors (more are coming). Each of them have different set of actions but most of the time, they also have a common set of actions. For example, eating. If I fix the eating behavior in students, that means that I have to also apply the same fix to the other classes. This is maintenance nightmare. A character class could become broken if I just happen to forget a certain fix. Applying a fix to each of the classes is tedious, too.

GOAP Actions Refactoring

I needed a way to refactor GOAP actions in such that I could just edit one set of actions and it will be applied to all the character classes. Thus, I introduced “extensions” to our GOAP framework.

GoapExtensions

An extension is basically a reference to another GOAP data set. During parsing of this data, the system adds all the actions found in the extension. An extension can also have a set of preconditions. These preconditions are added to all the actions in the extension. For example, from the image above, the NeedsBehaviour extension will only be executed if HasRequestedTreatment = false.

The refactored actions that pertains to “needs” are now placed in its separate GOAP data set:

NeedsBehaviour

The specific GOAP data for each character class can simply reference this “needs” data to be able to execute such actions. I only need to fix this “needs” GOAP data if I have to fix a “needs” related behavior. No need to apply separate fixes to each character class.

This feature turned out to be very useful. Every time there’s a new set of behaviour that could be reused, I put them in a separate GOAP data. The character class that requires it could just add this new data as an extension. For example, for now, only students can use computers. So I made a separate GOAP data called “ComputerLabBehaviour” and added it as extension to the student’s GOAP data. Later on, if we decide that teachers could also use computers, I can simply add the “ComputerLabBehaviour” data as extension to the teacher’s GOAP data.

Behaviours
Our current set of behaviours