Artificial Intelligence  
Lecture 03 Finite State Machines  
Edirlei Soares de Lima  
<edirlei.lima@universidadeeuropeia.pt>  
Game AI Model  
Pathfinding  
Steering behaviours  
Finite state machines  
Automated planning  
Behaviour trees  
Randomness  
Sensor systems  
Machine learning  
Decision Making  
In game AI, decision making is the ability  
of a character/agent to decide what to  
do.  
The agent processes a set of information  
that it uses to generate an action that it  
wants to carry out.  
Input: agent’s knowledge about the world;  
Output: an action request;  
Decision Making  
The knowledge can be broken down into external and  
internal knowledge.  
External knowledge: information about the game environment (e.g.  
characters’ positions, level layout, noise direction).  
Internal knowledge: information about the character’s internal state  
(e.g. health, goals, last actions).  
Finite State Machines  
Usually, game characters have a limited set of possible  
behaviors. They carry on doing the same thing until some  
event or influence makes them change.  
Example: a guard will stand at its post until it notices the player, then it  
will switch into attack mode, taking cover and firing.  
State machines are the technique most often used for this  
kind of decision making process in games.  
What is a state machine?  
Finite State Machines  
Actions or behaviors are associated  
with each state.  
Each transition leads from one state  
to another, and each has a set of  
associated conditions.  
When the conditions of a transition  
are met, then the character changes  
state to the transition’s target state.  
Each character is controlled by one  
state machine and they have a  
current state.  
Hard-Coded Finite State Machines  
enum State {PATROL, DEFEND, SLEEP};  
State myState;  
function update(){  
if (myState == PATROL){  
if (canSeePlayer())  
myState = DEFEND;  
if (tired())  
myState = SLEEP;  
}
elseif (myState == DEFEND){  
if not canSeePlayer()  
myState = PATROL;  
}
elseif (myState == SLEEP){  
if (not tired())  
myState = PATROL;  
}
}
Exercise 1  
1
) Implement a hard-coded finite state machine to control an  
NPC based on the following diagram:  
[
can see the player]  
Patrol  
Chase  
[
can’t see the player]  
Hints:  
Use the pathfinding maze created  
in last lecture as the base project.  
Create a list of waypoints to define  
the patrol areas.  
Attack  
Hard-Coded Finite State Machines  
Although hard-coded state machines are easy to write and are  
very fast, they are notoriously difficult to maintain.  
Complex finite states machines require thousands of lines of  
code.  
Another weaknesses:  
Programmers are responsible for writing the AI behaviors of each  
character.  
The game has to be recompiled each time the behavior changes.  
Class-Based Finite State Machines  
class StateMachine{  
private List<State> states;  
private State initialState;  
private State currentState = initialState;  
List<Action> update(){  
triggeredTransition = Transition.None;  
for each Transition t in currentState.getTransitions(){  
if (t.isTriggered()){  
triggeredTransition = t;  
break;  
}
}
.
..  
Class-Based Finite State Machines  
...  
if (triggeredTransition)  
{
targetState = triggeredTransition.getTargetState();  
List<Action> actions = new List<Action>();  
actions.Add(currentState.getExitAction());  
actions.Add(triggeredTransition.getAction());  
actions.Add(targetState.getEntryAction());  
currentState = targetState;  
return actions;  
}
}
else  
{
return currentState.getAction();  
}
}
Unity Implementation  
[
can see the player]  
Patrol  
Chase  
[
can’t see the player]  
Attack  
Class Diagram  
Finite State Machine  
State  
Transition  
1
1.*  
1
1.*  
1
+
initialState: State;  
-entryAction: Action;  
-stateActions: Action[];  
-decision: Condition;  
-action: Action;  
-targetState: State;  
-
currentState: State;  
-
-transitions: Transition[];  
exitAction: Action;  
-
-
-
Start();  
Update();  
DoActions(actions);  
+IsTriggered(fsm):bool;  
+GetTargetState():State;  
+GetAction():Action;  
+GetActions():Action[];  
+
+
+
GetEntryAction():Action;  
GetExitAction():Action;  
GetTransitions():Transition[];  
1
1
.*  
1
Condition  
1
.*  
+abstract Test(fsm);  
Action  
1
+abstract Act(fsm);  
Can See Condition  
-
-
-
negation:bool;  
viewAngle:float;  
viewDistance:float;  
Patrol Action  
Chase Action  
Attack Action  
Stop Action  
+Act(fsm);  
+Act(fsm);  
+Act(fsm);  
+Act(fsm);  
+Test(fsm);  
Unity ScriptableObject  
In Unity, a ScriptableObject is a class that allows you to store  
data and execute code independent from script instances.  
They can also be used to create pluggable data sets.  
They work like the MonoBehaviour class, but they don’t need to be  
attached to GameObjects.  
Once a ScriptableObject-derived class have been defined, is  
possible to use the CreateAssetMenu attribute to make it easy  
to create custom assets of the class.  
Unity ScriptableObject  
ScriptableObjects allow us to create a pluggable finite state  
machine system.  
Action Classes  
Action Class:  
public abstract class Action : ScriptableObject  
{
public abstract void Act(FiniteStateMachine fsm);  
}
Action  
+abstract Act(fsm);  
Patrol Action Class:  
[CreateAssetMenu(menuName = "Finite State Machine  
/Actions/Patrol")]  
public class PatrolAction : Action  
{
Patrol Action  
public override void Act(FiniteStateMachine fsm)  
{
+Act(fsm);  
if (fsm.GetNavMeshAgent().IsAtDestionation())  
fsm.GetNavMeshAgent().GoToNextWaypoint();  
}
}
Action Classes  
Chase Action Class:  
[CreateAssetMenu(menuName = "Finite State Machine/Actions/Chase")]  
public class ChaseAction : Action  
{
public override void Act(FiniteStateMachine fsm)  
{
if (fsm.GetNavMeshAgent().IsAtDestionation())  
fsm.GetNavMeshAgent().GoToTarget();  
}
}
Stop Action Class:  
[CreateAssetMenu(menuName = "Finite State Machine/Actions/Stop")]  
public class StopAction : Action{  
public override void Act(FiniteStateMachine fsm)  
{
fsm.GetNavMeshAgent().StopAgent();  
}
}
Action Classes  
Attack Action Class:  
[CreateAssetMenu(menuName = "Finite State Machine/Actions/Attack")]  
public class AttackAction : Action {  
public GameObject shootPrefab;  
public float shootTimeInverval = 2;  
private float shootTime = float.PositiveInfinity;  
public override void Act(FiniteStateMachine fsm)  
{
shootTime += Time.deltaTime;  
if (shootTime > shootTimeInverval){  
shootTime = 0;  
GameObject bullet = Instantiate(shootPrefab,  
fsm.transform.position, fsm.transform.rotation);  
bullet.GetComponent<Rigidbody>().velocity =  
fsm.transform.TransformDirection(Vector3.forward * 10);  
}
}
}
Action Classes  
Condition Class:  
public abstract class Condition : ScriptableObject  
{
public abstract bool Test(FiniteStateMachine fsm);  
}
Condition  
+abstract Test(fsm);  
Can See Condition Class:  
[
CreateAssetMenu(menuName = "Finite State Machine  
Conditions/Can See")]  
public class CanSeeCondition : Condition {  
SerializeField]  
private bool negation;  
SerializeField]  
private float viewAngle;  
SerializeField]  
private float viewDistance;  
..  
Can See Condition  
/
-
-
negation:bool;  
viewAngle:float;  
[
-viewDistance:float;  
[
+Test(fsm);  
[
.
Condition Classes  
.
..  
public override bool Test(FiniteStateMachine fsm){  
Transform target = fsm.GetNavMeshAgent().target;  
Vector3 targetDir = target.position - fsm.transform.position;  
float angle = Vector3.Angle(targetDir, fsm.transform.forward);  
float dist = Vector3.Distance(target.position,  
fsm.transform.position);  
if ((angle < viewAngle) && (dist < viewDistance)){  
if (negation)  
return false;  
else  
return true;  
}else{  
if (negation)  
return true;  
else  
return false;  
}
}
}
Transition Class  
[CreateAssetMenu(menuName = "Finite State Machine  
/
Transition")]  
public class Transition : ScriptableObject{  
SerializeField]  
private Condition decision;  
SerializeField]  
private Action action;  
SerializeField]  
Transition  
[
-
-
decision: Condition;  
action: Action;  
-targetState: State;  
[
+
+
+
IsTriggered(fsm):bool;  
GetTargetState():State;  
GetAction():Action;  
[
private State targetState;  
public bool IsTriggered(FiniteStateMachine fsm){  
return decision.Test(fsm);  
}
public State GetTargetState(){  
return targetState;  
}
public Action GetAction(){  
return action;  
}
}
State Class  
[
CreateAssetMenu(menuName = "Finite State Machine/State")]  
public class State : ScriptableObject{  
SerializeField]  
private Action entryAction;  
SerializeField]  
private Action[] stateActions;  
SerializeField]  
private Action exitAction;  
SerializeField]  
[
[
[
State  
[
-
entryAction: Action;  
private Transition[] transitions;  
public Action[] GetActions(){  
return stateActions;  
-stateActions: Action[];  
-
-
exitAction: Action;  
transitions: Transition[];  
}
public Action GetEntryAction(){  
+
+
+
+
GetActions():Action[];  
GetEntryAction():Action;  
GetExitAction():Action;  
GetTransitions():Transition[];  
return entryAction;  
}
public Action GetExitAction(){  
return exitAction;  
}
public Transition[] GetTransitions(){  
return transitions;  
}
}
Finite State Machine Class  
public class FiniteStateMachine : MonoBehaviour {  
public State initialState;  
Finite State Machine  
private State currentState;  
private MyNavMeshAgent navMeshAgent;  
+initialState: State;  
-currentState: State;  
-
-
-
Start();  
Update();  
DoActions(actions);  
void Start(){  
currentState = initialState;  
navMeshAgent = GetComponent<MyNavMeshAgent>();  
}
void Update(){  
Transition triggeredTransition = null;  
foreach (Transition t in currentState.GetTransitions()){  
if (t.IsTriggered(this)){  
triggeredTransition = t;  
break;  
}
}
.
..  
Finite State Machine Class  
List<Action> actions = new List<Action>();  
if (triggeredTransition){  
State targetState = triggeredTransition.GetTargetState();  
actions.Add(currentState.GetExitAction());  
actions.Add(triggeredTransition.GetAction());  
actions.Add(targetState.GetEntryAction());  
currentState = targetState;  
}
else{  
foreach (Action a in currentState.GetActions())  
actions.Add(a);  
}
DoActions(actions);  
}
void DoActions(List<Action> actions){  
foreach (Action a in actions){  
if (a != null)  
a.Act(this);  
}
}
}
Nav Mesh Agent  
public class MyNavMeshAgent : MonoBehaviour {  
public Transform target;  
public Transform[] waypoints;  
private int currentWaypoint;  
private NavMeshAgent agent;  
void Start(){  
currentWaypoint = 0;  
agent = GetComponent<NavMeshAgent>();  
}
public void GoToNextWaypoint(){  
agent.destination = waypoints[currentWaypoint].position;  
currentWaypoint++;  
if (currentWaypoint >= waypoints.Length)  
currentWaypoint = 0;  
}
.
..  
Nav Mesh Agent  
public void GoToTarget(){  
agent.destination = target.position;  
}
public void StopAgent(){  
agent.isStopped = true;  
agent.ResetPath();  
}
public bool IsAtDestionation(){  
if (!agent.pathPending){  
if (agent.remainingDistance <= agent.stoppingDistance){  
if (!agent.hasPath || agent.velocity.sqrMagnitude == 0f){  
return true;  
}
}
}
return false;  
}
}
Finite State Machine Objects  
States:  
Actions:  
Finite State Machine Objects  
Transitions:  
Conditions:  
Class-Based Finite State Machines  
The class-based approach gives a lot of flexibility to the Finite  
States Machines, but reduces its performance due to the large  
number of method calls.  
Another alternative: Script-Based Finite States Machines  
Scripting languages: Lua, Pawn, GameMonkey, ...  
Allows designers to create the state machine rules but can be slightly  
more efficient.  
However, interpreting a script is at least as time consuming as  
executing a large number of method calls.  
Exercise 2  
2
) Implement the AI of an NPC using the following finite state  
machine and the pluggable FSM system:  
[
found the player]  
Search  
Attack  
[
player died or run away]  
[
escaped and energy is low]  
Recover  
Energy  
Run Away  
Finite State Machines  
On its own, a state machine is a powerful tool, but as the  
complexity of agent behavior increases, the state machine can  
grow uncontrollably.  
Even the visual representation becomes complex.  
It can also be difficult to express composed behaviors (e.g. a recharge  
behavior that can occur at any state).  
Hierarchical State Machines  
Solution to reduce the complexity of the finite state machines:  
Hierarchical State Machines  
Rather than combining all the logic into a single state machine, we can  
separate it into several state machines arranged in a hierarchy.  
Hierarchical State Machines  
While high level states represent abstract actions, low level  
states represent concrete actions.  
Further Reading  
Buckland, M. (2004). Programming Game AI by Example. Jones & Bartlett  
Learning. ISBN: 978-1-55622-078-4.  
Chapter 2: State-Driven Agent Design  
Millington, I., Funge, J. (2009). Artificial Intelligence for Games (2nd ed.).  
CRC Press. ISBN: 978-0123747310.  
Chapter 5.3: State Machines  
Web:  
https://unity3d.com/pt/learn/tutorials/topics/navigation/