An introduction to finite state machines and the state pattern for game development

the finite state machine is something that plenty of game developers have never heard of but have almost certainly come very close to implementing a crude version of at some point or another it's a fundamental design pattern that's fairly intuitive with uses in character controllers simple ai and even ui components but many including myself wouldn't come up with the complete implementation of it on their own without guidance from those that are smarter than us it's important to understand this design pattern because it offers a lot of bang for your buck letting you write code of this cleaner easier to maintain and easily expandable for little effort so this week i'm going to kick off a two-part discussion on state machines and how to implement them in this first video i'll talk about why you should care about state machines and introduce the state pattern which will show us how we can implement a state machine in code i'm going to stick to pseudo code this week so we don't get too bogged down in engine specific details then in the next video we'll step into godot and look at how we can implement the state pattern there taking advantage of the features that the engine offers so let's dive in to kick things off let's first talk about what our code might look like without the state pattern so that we can understand the benefits it offers consider a simple platformer game we start off with a clean project and throw in our idle animation as the default state for our player we then add a run animation and some basic code based on what input the player is pressing the switch between the two so far so good but now i want to let the player jump and if they can jump then they can also fall which oftentimes will be a different animation in your game so we go ahead and add animations and code for jumping and falling states except that as written the jump animation will only play for one frame before defaulting to the following animation and the player can no longer move when they're in the air so we need to do some more checks to this code and add in a little bit of refactoring and we might end up like something what i have here now it's serviceable but what if we want to add in a double jump or maybe an attack for the double jump we'll need a variable to track whether or not we've already double jumped since at this point all we know is whether or not we're in the air not what we've done while in the air so we add that in and some additional checks to handle the double jump for the attack we'll need an animation we'll need a timer or some sort of callback so we know when the attack is over and so that we know when we can transition to the base states of idling moving jumping or falling we might also want to show a different animation when in the air versus on the ground when we attack and so you can already see where this is going pretty soon we'll end up with a long stretch of code filled with nested if statements and half a dozen or more variables that are used solely to track different states it's ugly it's error prone it's hard to debug and later on if we decide we want to go full metroidvania and add a dozen more power-ups and abilities it'll become a giant mess of hundreds of lines of code that we'll never want to go near and we'll probably never get it completely bug-free so let's take a step back put down our keyboard and step over to the white board for a moment to figure out what it is we're really trying to do and if i ask you to draw me a flow chart showing the rules of our character and what they should do and when you could do so pretty easily drawing our basics out of idle walking jump states we might end up with something like this and note that i've reworded a few of our checks just for the sake of brevity here the overall functionality is the same and so now we can further expand on this to include a false state a double jump or whatever other states we want we know what the rules of our character are and they're not even that complicated since most of what we have so far is just depending on whether or not we're on the ground what is complicated is telling the computer the rules for switching between states when we have no concept of state as we saw with even our basic platformer code base a series of if statements just doesn't cut it when we have more than two or three states we can be in but what we've just done with our flowcharts is describe a finite state machine which can be summed up with a few simple rules first there is a fixed number of states our character can be in such as idling walking jumping etc secondly the player can only be in one state at a time you obviously can't be walking and idling simultaneously for instance thirdly each state is responsible for doing one thing and one thing only so the walking state lets us walk the jumping state lets us jump etc and finally the active state receives inputs logical inputs in this case and not necessarily key inputs from the player though those are also valid and it then takes these inputs and follows its own rules as to when the transition to another state as an example if we're falling and landing on the ground that's one input into the machine but then we can either begin walking or idling depending on what keys if any the player is pressing and that's it as far as the concept of a finite state machine is concerned if you can draw the behavior you want with the flowchart you can make a finite state machine out of it and as one additional note before we look at how to implement a finite state machine i'll mention that you'll often see people including myself use the term finite state machine and state machine interchangeably for most people's purposes the two are the same thing as even wikipedia redirects the term state machine to finite state machine but a state machine is technically the more generalized form of the finite state machine and it does not necessarily have a fixed or finite number of states it can be in but that's as much as i can speak to the distinction since a non-expert on ai and or computational models get your local math professor or computer science professor drunk if you really want to dive into the differences especially in a game development context and so we've established that finite state machines are great for laying out organizing the flow of state in our game but we still don't know how to actually implement one in code so let's do that now in the most basic form of implementation if we have a fixed set of unique states and only one can be active at a time we can get away with representing our current state using enumerators and branching our code as needed this lets us turn our player code class from this into this it still doesn't completely get rid of the problems we ran into above as we still have to manage several variables and timers for different states but it does at least let us segregate our logic for each state into separate functions and give us a fairly readable stretch of code once more and makes it very clear what our current state always is and with this setup we can at least follow the branches of code easily enough that we can get where we need to for low mental effort if we need to debug something this is the version of the state machine that i figure some of you have either implemented or come close to implementing in the past as taking a glob of complex code and breaking into smaller functions is a pretty natural step to take as your code base grows the enum is just one more layer to help us keep track of everything which will quickly outgrow this implementation for many or even most use cases but it is worth mentioning as it's a great fit for very simple objects in fact i find myself reaching for this technique when i'm making an object with a basic on off state such as a door or switch or maybe a simple turret that's either scanning the room firing on a target or recharging its shot so this method is okay and is useful but there is a better way to implement a state machine and that's where the state pattern comes in the state pattern describes an object-oriented way for an object to change its behavior on the fly based on the inputs it receives the term object orion is the giveaway for what we're about to do create an interface representing a generic state implement the interface with a class for each state that the parent entity our player in this case delegate all state dependent logic to the class representing the active state and then provide a way for the states to transition to one another so let's look at each in order first we create an interface to describe a generic state that has a virtual method for everything we normally have a switch and or if statement controlling implementing input and update methods is a good start but you may also want to connect your physics update loop if it's separate from your regular update loop like it is in godot and many other engines you may want to connect your collision callbacks etc everything that we need to act differently based on the state we're in gets a method that way we have a consistent interface our parent entity can rely on and reference we then need to create a class for each state that implements the state dependent logic in our case that would be idle walking jumping etc we'll use our jump state as an example for this code block excluding the code for transitioning to another state since we'll come back to that in just a moment with each state now identified in its own class the parent entity our player class just needs to track what the current state is and delegate all logic to it when an event occurs our base class can now look something like this so we now have the general idea of how everything works but we've left out a pretty important detail how the state change actually happens and there's actually a few different ways to implement this i'm just going to show you my preferred method today so let's go back to our interface and now make it so that each virtual method can optionally return a new state to the player class this makes our jump class now look like this and every time we want to change states we'll simply return a new instance of the state we want to transition to updating our player class we can now check for a returned value after each call to the active state and if we'll return to new state we switch states and delete our old state now this method results in a fair bit of data churn but it generally shouldn't be a problem for performance we won't look at alternative implementations in this lesson as i want to keep things as straightforward as possible and not overwhelm you with every possible way of implementing the state machine but if you do want to prevent this churn you could also consider using static states if there's only one instance of an object in the world such as the player in a single player game or keeping one instance of each state in the memory and using a service to get a reference to each one at runtime and resetting their behavior whenever you switch to them and in fact this second method is what i used in liberation mutagenics my lemmings-esque game that had multiple layers of state machine to sort through there was one layer for the genetic state each character could be in and then there was another one for the specific action they were currently doing while in that genetic state and so we're already in a pretty good spot with our code and you could use it more or less as is but let's do one more expansion of it and add logic that runs when we enter or exit the state that way we can easily do things like switching animations upon entering a new state cancelling any asynchronous calls that may be running when we exit the state etc and doing that our interface turns our jump class into this and note that we still have to implement the exit method even if we don't need it for this particular state this is important so that our player class never has to concern itself with what methods are and are not implemented on a specific state by the end of this video i will mention another way that you can implement this without having to have an empty method in every state if you don't need it but speaking of our player class it now changes to this nothing too crazy we just now let our previous state exit before switching to the new state and then calling its enter function and now we have a robust state machine expanding on this say to add a dash attack or ground slide just means writing a new class that implements our standard interface no other parts of our code will care and they just have to instance any new classes if and when they should switch to them and so this ends up being a lot cleaner and neater than what we were doing previously with lots of nested if statements and even the enumerator operation i'll also mention that you may find yourself duplicating a lot of code or maybe just doing the same thing each time under state just slightly differently such as playing an animation and a sound upon entering every state and you may also run into a situation where for instance on our jump class we don't need to call the exit method in that state but we still have to anyways and so in such a case you may find it useful to create a base state class that implements the state interface and lets all of your other state classes inherit from that just using a variable to modify reusable code blocks as needed and overriding its base implementation of the function as needed and so for instance it can hold the exit function that way jump does not have to and that lets us clean up that code just a little bit further and that finally is all i want to talk about regarding state machines and the state pattern there's a lot more that i haven't covered but this should be enough to get you well on your way with them if you want to know more game programming patterns has an excellent chapter on state machines along with some alternative implementations of them and additional ways they can be expanded upon i'll link to that in the description in the next video we'll hop into godot and i'll show you how we can implement a state machine there see you then

Channel: The Shaggy Dev

Views: 51,146

Keywords:

Id: -ZP2Xm-mY4E

Length: 10min 54sec (654 seconds)

Published: Tue Nov 02 2021