Modular FSM

Modular finite state machine for Unity
https://github.com/GandhiGames/modular_fsm
1 forks.
0 stars.
0 open issues.
Recent commits:

 

What is it?

A Finite-state Machine (FSM) is possibly one of the most popular data structures for game AI programming (and it also has proven popular outside the domain of game AI). Implementing a FSM will help you break down an initial problem into a number of smaller, more manageable sub-problems.

Most FSMs contain three things states, transitions and boundaries (also called conditions). The states contain the actual AI behaviour, transitions provide a method or moving between states, and boundaries/conditions provide the reason so move between states. An agent will maintain a state until a certain condition is met and then it will transition to a new state, it’s as simple as that.

A simple example of a FSM layout for a typical enemy is shown below.

An example Finite state machine diagram for an enemy. The FSM has the following states: evade, attack, wander, and find aid (when hurt).
Simple state machine outline for an enemy. Image found here.

When implemented the enemy will start wandering around the environment (the initial state) and will then transition into attacking the player if the player is near (the condition). Once in the attacking state, the enemy can either move back into the wandering state (if the player moves out of sight) or move into an evade state if the player begins attacking back (another condition). Lastly the enemy will check its current hit points while in the evade state and if it is below a certain threshold, transition into a ‘find aid’ state. While this is a basic example, you can see how a FSM helps to split complex problems into smaller ones.

So we can say a FSM has:

  • A fixed number of states that the machine can be in. The smaller the number of states the better in most cases, as entities that contain a large number of states can become cumbersome.
  • An entity can only be one state at any one time, although a state can have a number of actions and transitional checks (more on that later).
  • Each transition points to another state so that when the transitions criteria are met the entity moves to the associated state.

A FSM is relatively simple (at least when compared to other AI systems) and can replace a cumbersome set of switches/if statements with associated flags. However, it is not the only data structure out there, alternatives to FSM include: Goal Oriented Action Planning and Behaviour Trees.

 

How do you use it?

The FSM (link to the GitHub project at the top of the page) contains four main classes:

  • FSM: controls the state machine transitions and contains all the states.
  • FSMState: composed of a number of actions and reasons.
  • FSMAction: an action to be performed while the agent is in the state.
  • FSMReason: a transitional test. Contains the condition and ID of the state that should be transitioned to when the condition has been met.

The FSM class maintains a list of all associated states. It contains methods for adding and removing states, and performing transitions between states.

public class FSM : MonoBehaviour
{
private List<FSMState> fsmStates = new List<FSMState>();
public GlobalStateData.FSMStateID PreviousStateID { get { return previousState.ID; } }
public GlobalStateData.FSMStateID CurrentStateID { get { return currentState.ID; } }
private FSMState previousState;
public FSMState PreviousState { get { return previousState; } }
private FSMState currentState;
public FSMState CurrentState { get { return currentState; } }
private FSMState defaultState;
void OnDisable()
{
if (currentState != null)
currentState.Exit();
}
public void AddState(FSMState state)
{
if (state == null)
{
Debug.LogWarning(SCRIPT_NAME + ": null state not allowed");
return;
}
// First State inserted is also the Initial state
//   the state the machine is in when the simulation begins
if (fsmStates.Count == 0)
{
fsmStates.Add(state);
currentState = state;
defaultState = state;
return;
}
// Add the state to the List if it´s not inside it
foreach (FSMState tmpState in fsmStates)
{
if (state.ID == tmpState.ID)
{
Debug.LogError(SCRIPT_NAME + ": Trying to add a state that was already inside the list, " + state.ID);
return;
}
}
//If no state in the current then add the state to the list
fsmStates.Add(state);
}
public void DeleteState(GlobalStateData.FSMStateID stateID)
{
if (stateID == GlobalStateData.FSMStateID.None)
{
Debug.LogWarning(SCRIPT_NAME + ": no state id");
return;
}
// Search the List and delete the state if it´s inside it
foreach (FSMState state in fsmStates)
{
if (state.ID == stateID)
{
fsmStates.Remove(state);
return;
}
}
Debug.LogError(SCRIPT_NAME + ": The state passed was not on the list");
}
public void PerformTransition(GlobalStateData.FSMTransistion trans)
{
// Check for NullTransition before changing the current state
if (trans == GlobalStateData.FSMTransistion.None)
{
Debug.LogError(SCRIPT_NAME + ": Null transition is not allowed");
return;
}
// Check if the currentState has the transition passed as argument
GlobalStateData.FSMStateID id = currentState.GetOutputState(trans);
if (id == GlobalStateData.FSMStateID.None)
{
Debug.LogError(SCRIPT_NAME + ": Current State does not have a target state for this transition");
return;
}
// Update the currentStateID and currentState		
//currentStateID = id;
foreach (FSMState state in fsmStates)
{
if (state.ID == id)
{
// Store previous state and call exit method.
previousState = currentState;
previousState.Exit();
// Update current state and call enter method.
currentState = state;
currentState.Enter();
break;
}
}
}
}

In this modular implementation of a FSM. A state can consist of any number of actions (or behaviour) and reasons (or boundaries/conditions).

The basic FSMState structure consists of the following methods:

  • Enter: invoked when entering state. Calls Enter method for each action and reason.
  • Exit: invoked when exiting state. Calls Exit method for each action and reason.
  • Reason: checks transition conditions. Should be invoked in Update.
  • Act: performs current action. Should be invoked in Update.

/// <summary>
/// Abstract base class for a state
/// Provides functionality for storing and retrieving transitions between states.
/// </summary>
public abstract class FSMState
{
// Each state has an ID that is used to identify the state to transition to.
protected GlobalStateData.FSMStateID stateID;
public GlobalStateData.FSMStateID ID { get { return stateID; } }
// Stores the transition and the stateid of the state to transistion to.
protected Dictionary<GlobalStateData.FSMTransistion, GlobalStateData.FSMStateID> map =
new Dictionary<GlobalStateData.FSMTransistion, GlobalStateData.FSMStateID>();
/// <summary>
/// Called when entering the state (before Reason and Act). 
/// Place any initialisation code here.
/// </summary>
public abstract void Enter();
/// <summary>
/// Called when leaving a state. 
/// Place any clean-up code here.
/// </summary>
public abstract void Exit();
/// <summary>
/// Decides if the state should transition to another on its list.
/// While the state is active this method is called each time step.
/// </summary>
public abstract void Reason();
/// <summary>
/// Place the states implementation of the behaviour in this method.
/// While the state is active this method is called each time step.
/// </summary>
public abstract void Act();
/// <summary>
/// When implemented should return true when it is ok for the character to perform the actions in the Act method.
/// Place behaviour specfic tests in this method.
/// </summary>
protected abstract bool OkToAct();
}

The FSMAction contains four methods:

  • Enter: invoked when transitioning into associated state.
  • Exit: invoked when exiting associated state.
  • PerformAction: the action to perform while the agent is in this state.

public abstract class FSMAction
{
public abstract void PerformAction();
protected abstract bool OkToAct();
public abstract void Enter();
public abstract void Exit();
}

The FSMReason has three methods:

  • Enter: (same as FSMAction) invoked when transitioning into associated state.
  • Exit: (same as FSMAction) invoked when exiting associated state.
  • ChangeState: performs transitions if conditions met.

It also contains the ID of the state that should be transitioned into and a number of helper methods that are used by multiple reasons.

public abstract class FSMReason
{
public GlobalStateData.FSMTransistion Transition { get; set; }
public GlobalStateData.FSMStateID GoToState { get; set; }
public abstract bool ChangeState();
public virtual void Enter() {}
public virtual void Exit() {}
protected bool LayerInPath(Vector2 objPosition, Vector2 characterPos, LayerMask mask)
{
var heading = objPosition - characterPos;
var distance = heading.magnitude;
var dir = heading / distance;
Ray2D ray = new Ray2D(characterPos, dir);
Debug.DrawRay(ray.origin, ray.direction, Color.black);
var hit = Physics2D.Raycast(ray.origin, ray.direction, distance, mask);
if (hit.collider != null)
{
return true;
}
return false;
}
protected bool CloseToObject(Vector2 objPos, Vector2 characterPos, float distance)
{
return Vector2.Distance(characterPos, objPos) < distance;
}
}

For more in depth example of how to implement the FSM see the code associated with the book I am currently writing. It has a number of simple FSMs setup for different enemies, with more examples to come in future.

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *