What is a Finite State Machine?
A finite state machine is a quite popular software pattern used in games development to implement behavior, for example the behavior of an enemy unit or a complex object. A state machine, also known as finite state automaton, is quite easy to diagram and code and can be used to represent a broad range of behaviors.
As defined in AI-depot.com (great resource for A.I. stuff btw), a finite state machine consists of four main elements:
- states which define behavior and may produce actions
- state transitions which are movement from one state to another
- rules or conditions which must be met to allow a state transition
- input events which are either externally or internally generated, which may possibly trigger rules and lead to state transitions
I won’t go into FSMs in more detail, since there are great resources on the internet doing that already (check the Reference section in the end).
Motivation
As I currently need an FSM to implement the main character’s behavior based on user input in a game I’m working on, I decided to implement a generic C# version. What I currently have is far from complete, but it has the core functionality I want, which is:
- Initialize the state machine with a set of transitions, defining the character’s behavior,
- When some input events occur, try to advance the state machine to the next state, and
- If that transition is allowed, change the state and call the user defined callback function.
Specifically, I wanted something that would allow me to easily implement the following diagram, which defines my player character’s behavior. Also I wanted the system to be easily extendable with new states and transitions.
Design & Implementation
So I looked around and decided that using C# delegates will be the best choice at the moment. Delegates in C# are basically function pointers, allowing you to call a function from anywhere and are easy to use, flexible and quite fast to execute (almost the same as a direct function call).
FSM Class diagram
In the class diagram above you can see the StateTransition which implements the IEquatable interface and the FiniteStateMachine which implements the functionality of a state machine of course. Both classes are templates allowing the state type to be user defined. I use them with enums that define the states the entity can take.
The StateTransition is basically a C# tuple, allowing me to use it as a key with two values in the state transition dictionary. After I implemented that I found out that you can also use the System.Collections.Generic.KeyValuePair<k, v=””>, replacing K and V with the state enum, to achieve the same behavior. I am not sure if there’s any performance difference between my version and the KeyValuePair, but so far I can’t see any noticeable difference.
I’ve uploaded the C# source file of my implementation at the end of this post. Just unzip the file and follow the steps below to use it in your projects. As I said earlier my state machine is far from complete but it provides the core functionality I need and it might be a good starting point for other projects as well.
How to use it
First you create an enum with all the desired states of your entity and pass it to the FiniteStateMachine class.
|
1 2 3 4 5 6 7 |
// Add the possible states here public enum eCharacterState { IDLE, RUN, // ... }; |
public class CharacterFSM : FiniteStateMachine {};
You should create a bunch of functions that implement the behavior of your entity, for example I have Run(), Idle(), IdleJump(), etc for my character. Then calling AddTransition() adds the desired state transitions to the machine. When certain conditions are met, you call the Advance() function to try and advance the FSM to the desired state. If the transition occurs, the user defined function will be called.
The code below implements part of my character’s behavior. I won’t post the whole file yet as I have a bunch of code, but it should give a good idea of its usage.
|
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 |
public class Player : CatGameItem { // ... public CharacterFSM mFSM; void Start () { mFSM = new CharacterFSM(); // Add state transitions here mFSM.AddTransition(eCharacterState.IDLE, eCharacterState.RUN, Run); mFSM.AddTransition(eCharacterState.RUN, eCharacterState.IDLE, Idle); // This calls the Run() function while on run state. // I will probably replace it with with a state callback or something similar sometime in the future to avoid calling TryGetValue all the time. mFSM.AddTransition(eCharacterState.RUN, eCharacterState.RUN, Run); // ... } // FSM Delegates void Run() { //Debug.Log("RUN!"); float curMoveSpeed = Controller.GetGroundSpeed(); AnimationController.SetSpeed("Cat_Run", curMoveSpeed/RunSpeed); AnimationController.Play("Cat_Run"); } void Idle() { AnimationController.Play("Cat_Idle_Breath"); } // ... void UpdateInput() { mCurAxisInput.x = Input.GetAxis("LeftAxisH"); // Get Horizontal axis (XBox360 xAxis OR 'A', 'D') mCurAxisInput.y = Input.GetAxis("LeftAxisV"); // Get Vertical axis (XBox360 yAxis OR 'W', 'S') } void UpdateStateMachine() { // Based on the input events, advance to desired state // Run, Idle if (mCurAxisInput.magnitude > 0) mFSM.Advance(eCharacterState.RUN); else mFSM.Advance(eCharacterState.IDLE); // ... } void FixedUpdate() { // Update the state machine here UpdateStateMachine(); } void Update () { // Update user input UpdateInput(); UpdateCharacterMovement(); } } |
References
- https://en.wikipedia.org/wiki/Finite-state_machine
- http://ai-depot.com/FiniteStateMachines/FSM.html
- http://jessewarden.com/2012/07/finite-state-machines-in-game-development.html
- http://unitygems.com/fsm2/
I’d love to check out your source for this, download link does not work though. 🙂
Seems the images & source were broken :(. Should work now.
Let’s say I have 3 states: “Idle”, “Walking” and “Falling”. And a grounded flag which says if i am on the ground or not (recalculated once every FixedUpdate).
IDLE:
if (Input.moveX > 0.3) TransitionTo(“Walking”)
WALKING:
if (Input.moveX <= 0.3) TransitionTo("Idle")
else { }
FALLING:
if (grounded) TransitionTo(“Idle”)
Let’s say i am currently in “Falling” (and holding my Input.moveX > 0.3 so when I land i immediately start walking) and after a few FixedUpdates I land on something and my “grounded” flag gets set to true and the current state gets changed to “Idle”.. but I don’t immediately start walking because this is still the FixedUpdate of the “Falling” state.
So the next FixedUpdate runs and the current state is “Idle” and Input.moveX > 0.3 so the state changes to “Walking”.. but I’m still not moving because this is the FixedUpdate of the “Idle” state.
So only when the next FixedUpdate runs I start moving.
But for 3 FixedUpdates I just stand there waiting for the transition conditions to process so I can get to my “Walk” state and start actually moving. I actually tried this and it has a visible glitchy effect.
Am I missing something? Am I doing this wrong?
You probably are right. I’ve written this code about 2 years ago and haven’t touched it ever since to be honest :). You could add another transition from “Falling” to “Walking” but if the code takes 1 frame to advance to a state and execute it you would have managed to reduce the processing from 3 to 1 frame which is not ideal. If I remember correctly this was happening in my case as well (not sure if I coded it like that on purpose or if it’s a bug). I guess you’ll have to tweak the code (or write a new FSM) to switch to the desirable state as soon as the conditions are met. That’s what I’ll be doing at least as I need to write an FSM for another project.