Hello,
In this post I'd like to talk about a basic programming concept, the state machine. State machine's are used all over the place in various areas of programming. In games, they are heavily used by AI (and other things, however this post will deal mostly with AI). So let's get right down to it.
What is a state machine? It can essentially be boiled down into a giant list of if/else statements of potential tasks. For instance, I might have a boolean for isTired, isReadyToFight, or isFighting associated with a warrior. So my state machine might look something like this
class Warrior : GameObject
{
bool isTired = true;
bool isReadyToFight = false;
bool isFighting = false;
void Update()
{
if(isTired)
{
isReadyToFight = isFighting = false;
isTired = true;
Rest();
}
else if(isReadyToFight)
{
isFighting = true;
Fight();
}
}
//Rest of implementation omitted
}
Phew. That took a while to type. Let's look at this. So we can see we have two real states here. Resting and Fighting. We start off with isTired = true, so Resting is our Initial State or Starting Point in our state machine. We rest till we're ready to fight, then we fight till we need to rest. Pretty simple. Let's assume we needed another state, such as retreat. Then we would need another bool, and more if/else statements. Then we add states like MoveIntoRange, Heal, DefendTarget...oh my. This code is turning into a disaster! But you probably already know the solution..
We could use enumerators to traverse our state machine. Let's take a minute and see what this might look like:
class Warrior : GameObject
{
enum State {Resting, Fighting}
State currState = State.Resting;
void Update()
{
switch(currState)
{
case State.Resting:
Rest();
if(canFight)
SetCurrentState(State.Fighting);
break;
case State.Fighting:
Fight();
if(!canFight)
SetCurrentState(State.Resting);
break;
default:
break;
}
}
void SetCurrentState(State newState)
{
switch(currState)
{
case State.Resting:
//Do some exit resting stuff: make the bed, get dressed, etc.
break;
case State.Fighting:
//Do some exit fighting stuff: Put away sword, Report to commander, etc.
break;
default:
break; }
switch(newState)
{
case State.Resting:
//Do some enter resting stuff, put on pajamas, drink warm milk etc.
break;
case State.Fighting:
//Do some exit fighting stuff: Take out weapons, say goodbye to your mom, etc.
break;
default:
break; }
currState = newState;
}
//Rest is omitted
}
Phew. Lots of code again. Well, we've cleaned up alot from last time. We even added some enter/exit state functionality, which is great! States could even have their own sub-states like this. But, our code is still very challenging to add states to. Every time we want to add a state, we'll need to extend the switch state in Update, and most likely both witch statements in SetCurrentState. Also, there's something else we need to worry about. In the Resting state, we check to see if we can fight. But what if we need to check for more things, such as go to work, or do chores? The resting state will continue to grow as we add more states that can be reached from the resting state. True, we could modulate this and put the Resting state in its own function ExecuteResting(), but the warrior class itself is now becoming huge and messy with lots of complicated functions and confusing state connections. Plus we have to watch out for things like going into states we shouldn't be. For instance, if we're in a Retreat state, it doesn't make alot of sense to be able to go into the Rest state just cause its time to rest. So, onto the actual solution used today.
First off, we make an actual State abstract state class that looks something like this.
template <class T>
abstract class State
{
public virtual void Execute(T owner) {}
public virtual void Enter(T owner) {}
public virtual void Exit(T owner) {}
//You can easily add more like this if you need to
}
Then we can make a state machine as such
template <class T>
class StateMachine
{
State<T> currState;
T m_owner;
StateMachine(T owner) {m_owner = owner;}
//Hiding the default constructor
private StateMachine() {}
public void Update()
{
if(currState != NULL)
currState.Execute(m_owner);
}
public void SetNewState(State<T> newState)
{
if(currState != NULL)
currState.Exit(owner);
currState = newState;
currState.Enter(owner);
}
}
At this point, we can make our warrior class look like this
class Warrior : GameObject
{
StateMachine<Warrior> m_stateMachine;
Warrior() {m_StateMachine.SetNewState(new WarriorResting(); }
void Update() {m_stateMachine.Update(); }
void Rest() {/*Rest omitted*/}
void Fight() {/*Fight omitted*/}
}
Then we can make our Rest state
class WarriorRest : State<Warrior>
{
public virtual void Enter(Warrior owner) {/*Put on pajamas, drink milk, etc*/}
public virtual void Exit(Warrior owner) {/*Make bed, get dressed, etc*/}
public virtual void Execute(Warrior owner)
{
owner.Rest();
if(owner.isReadyToFight)
owner.m_stateMachine.SetNewState(new WarriorFight());
}
}
The WarriorFight class would be of similar nature. Let's look at some of the many advantages of doing this.
1. Very easy to maintain and add new states. If we want to add say, a retreat class, its very easy to do that. We just make a new WarriorWhatever class. Then wherever we should be able to enter that class from we can make the appropriate checks to do so. We still have to go to each of our states and put the checks in, however we don't have to search through nasty switch statements to do it. We know right where ALL of our Rest logic is contained and can easy add it there.
2. Separation of AI Logic and function. So, what if we wanted to make the player a warrior as well? With this functionality we notice that a player could easy control the warrior class. All the functionality is there-Rest, Fight, Retreat, etc- its just a matter of how its called. With the previous solutions, it would be much more challenging to separate the two to re-use Warrior for any other purpose.
3. Easy to modify. What if we want some global check going on? Such as, at any given point in time, we want to be able to Retreat. We could easily modify the StateMachine class to support this.
State<T> globalState;
public void Update(){
if(currState != NULL)
currState.Execute(m_owner);
if(globalState != NULL)
globalState.Execute(m_owner);
}
Now we have two states running simultaneously. Our global state could be something like
class CheckRetreat : State<Warrior>
{
public virtual Execute(Warrior owner)
{
if(!owner.isRetreating && BattleManager.shouldRetreat)
{
owner.m_stateMachine.SetNewState(new WarriorRetreat());
}
}
}
In fact, you could even modify your state machine to maintain a list of states to update all at once! (Careful if you actually do that though, not as good as an idea as it sounds). Some common state machine modifications include keeping track of the previous state to revert to at any time, having a static state shared by all people who would use it, making the state machine itself static for many Warriors to use. The possibilities are pretty endless.
4. Easy on memory.
If you look at it, you pretty much see that all the states work with any owner. So, is there any real reason for each state machine have its own instance of every state? Not really, no. All of your states could be made into singletons. Then instead of doing
m_stateMachine.SetNewState(new WarriorRest());
We could do
m_stateMachine.SetNewState( WarriorRest.Instance());
You could even make a StateManager to keep track of states and delete ones least recently used and keep the frequent ones in memory as much as possible.
There are many other advantages to this approach, but since this is getting pretty long as it is, I'm going to cut it short here. I hope this opened some doors or at least served as a useful refresher. Oh, and as for the mashed up C#/C++ code I was using in my examples, I was just trying to use what seemed most readable for the given instance. Sorry if you were looking for really specific coding examples.
PS, all AI in this game was made using the state machine algorithms above, just to show you that this stuff can work and be pretty useful.
http://class.cas.msu.edu/tc455/project2/group1/index.html
If you wanna talk more states or more game AI in general, shoot me an email at warddav16@gmail.com or leave a comment below!
--daviD Ward
Sunday, May 12, 2013
Saturday, March 2, 2013
Object Orient All The Things
Hello again,
This post is going to be slightly different. Its about porting what you learn in your object oriented design class to the real world: where it works and where it doesn't. Lets get started.
My latest game I'm working on is a retro 2D style game, mostly inspired by Legend Of Zelda : Link to the Past. Since its a 5 week project, we're not doing any dungeon crawling, but what we are doing are boss fights. And since I have another programmer, I get to do all the boss AI! Dream come true. Now, I sought out to make some simple, re-usable code from my favorite AI book (and one of my favorite game programming books in general), Programming Game AI by Example, by Mat Buckland.
http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782
Its a great intro to AI book, go read it! Really, its way better than this post. Go read it!
...You read it? Awesome! Lets continue.
So after watching some LOZ Link to the Past boss videos on youtube, I noticed all bosses are pretty state driven. 1st chapter of that awesome book I know you just read is about state driven AI, so that's pretty fantastic. I made a StateMachine class and an abstract State class and was all set to go! I made an EnemyBase class who owned its own StateMachine and I was pumped to start making state based behaviors, everything was so awesome and cool there, and I started on the first boss. Here's where my super object oriented world crashed.
Spoiler alert, first boss is going to be a wizard who shoots fireballs in random directions. Also, before the fight, there are going to be archers who shoot arrows. Awesome! I'll just make a shoot arrow state and...oh wait. Let's look at our abstract state class in C#
public abstract class State<T>
{
public virtual Enter(T owner){}
public virtual Execute(T owner){}
public virtual Exit(T owner){}
}
So what if I made a State called ShootArrow?
public class ShootArrow : State<EnemyBase>
{
public override Enter(EnemyBase owner)
{
owner.ShootArrow();
}
}
There's a huge issue with this approach, and that is EnemyBase doesn't have a ranged attack! Sure, I could've made one, but not every enemy needs a ranged attack, so that's not very object oriented to put one there...they could have a virtual ranged attack that's only implemented in classes that need to have a ranged attack, but what if two classes need to implement it that exact same way (like Archer and Boss1)? Then both classes would have duplicate code...no no no. Never think copied code. Always wrong. Not object oriented. You will get and F on the project. Bad bad bad.
But even here I had already jumped ahead of myself. Without putting all functionality for every enemy I ever want to have in my base class, I can't have any state inherit from State<EnemyBase> as it won't be able to call any functions it doesn't have. So, each thing inherited from EnemyBase will need to have its own state machine, so states can call the functions they'll need. I'll need things like
public class ShootBolt : State<Boss1>
{
public override Enter(Boss1 owner)
{
owner.ShootBolt();
}
}
instead. Then Boss1 can have a function that shoots bolts! Hooray! Oh wait....have you seen the problem yet? Archer needs to shoot arrows too...but I can't give the archer a state made for Boss1, the compiler would never allow it. So what if I made a class inbetween EnemyBase and Boss1 and archer called EnemyCanShoot : EnemyBase and then do Boss1 : EnemyCanShoot and Archer : EnemyCanShoot? Then my state could be public class ShootBolt : State<EnemyCanShoot> instead? That could work....if shooting a bolt was the only thing I ever needed to share between classes. What happens if Boss1 and BasicWizard need to teleport as well? Boss1 can't inherit from EnemyCanShoot AND EnemyCanTeleport, this is C# (oh yeah, this projects being made in C# and Unity3D), multiple inheritance isn't allowed. Even if it were C++ and we could do MI, that could start to really lead to some super sloppy code.
class Boss1 : public EnemyCanShoot, public EnemyCanTeleport, public EnemyCanSlash, public EnemyCanDie, public EnemyCanBreatheFire, public EnemyCanSwim, public EnemyDropsPickup
etc...yikes. So this doesn't seem like a good idea, especially when all those EnemyCan's all inherit from from the same EnemyBase and would be overriding different functions at the same time and trying to figure out which fricking Move function you actually wanna call like the one that swims or flies or teleports or asdfbgrwhrtw. Messy. More like EnemyCant. Ha. Jokes.
But really, maybe we could do something like an interface? Yeah, that could work, public class Boss1 : ICanShoot and public class Archer : ICanShoot that just have some sort of functionality to shoot. Problem is, interfaces can't have anything really in them, like variables or function definitions. So if Boss1 and Archer need to shoot the exact same way, you end up with redundant code. Insert Luke Skywalker "Nooooo" here.
Is there any hope out there? Is this super StateMachine not as awesome as I originally thought? Can I not have re-usable states everywhere? What to do? Ultimately, I had to face some kinda rough truths (at least for me). Sometimes, its okay to not object orient all the things. This idea of an abstract state machine presented in the book wasn't meant for what I was trying to use it for. That's not to say its not still awesome, it takes code away from your Boss1 code and breaks it down and makes it much more manageable and readable without alot of nasty switch statements. Which is wonderful. But I had to accept it, without a major code re-structure (which I really didn't want to do), I was going to have either some duplicate code or some enemies that had (potentially alot of) un-needed functionality. If I were to start this project over, I probably would've done things a bit differently. I might not have used this StateMachine approach as such a godlike over any other AI approach and make it so every enemy HAS to use it.
And you might be wondering "why didn't he just do this" or "why didn't he just do that" or some super thing that I didn't think of that magically does everything I was just trying to do. First, let me say I tried alot of things that I didn't even really mention in this article to get this approach of re-usable states to work that failed, so I may have attempted it. Secondly, this is a 5 week project where I have quite alot of other things to do, both in this project and outside of it too, so spending a week trying to get this perfect for all cases just wasn't in the cards. That being said, if someone has some way or technique that does let this work the way I was trying to, please share!!!! I'm very curious, and I'm sure there's a solution out there I didn't have time to try that works great and is magical and awesome and lovely. But that being said, here's how my story ends now:
There are 5 lines of duplicate code copied and pasted in my project now. It happened. And you know, I'm pretty okay with that. I made alot of object oriented code in this that I'm quite proud of (next post maybe) and some AI that's working nicely. And if the alternative is spending hours and hours getting an approach to do something its probably not truly meant for, only 5 line is great to me. Spending the time to completely object orient (assuming you are doing an object oriented approach, not something like data oriented) is usually worth it, but if you don't do it to its fullest because the game needs to get done, or because the approach you took is awesome and perfect except for one or two little instances, trust me: its not the end of the world, and your teacher isn't going to give you an F if your game is awesome.
--daviD Ward
This post is going to be slightly different. Its about porting what you learn in your object oriented design class to the real world: where it works and where it doesn't. Lets get started.
My latest game I'm working on is a retro 2D style game, mostly inspired by Legend Of Zelda : Link to the Past. Since its a 5 week project, we're not doing any dungeon crawling, but what we are doing are boss fights. And since I have another programmer, I get to do all the boss AI! Dream come true. Now, I sought out to make some simple, re-usable code from my favorite AI book (and one of my favorite game programming books in general), Programming Game AI by Example, by Mat Buckland.
http://www.amazon.com/Programming-Game-Example-Mat-Buckland/dp/1556220782
Its a great intro to AI book, go read it! Really, its way better than this post. Go read it!
...You read it? Awesome! Lets continue.
So after watching some LOZ Link to the Past boss videos on youtube, I noticed all bosses are pretty state driven. 1st chapter of that awesome book I know you just read is about state driven AI, so that's pretty fantastic. I made a StateMachine class and an abstract State class and was all set to go! I made an EnemyBase class who owned its own StateMachine and I was pumped to start making state based behaviors, everything was so awesome and cool there, and I started on the first boss. Here's where my super object oriented world crashed.
Spoiler alert, first boss is going to be a wizard who shoots fireballs in random directions. Also, before the fight, there are going to be archers who shoot arrows. Awesome! I'll just make a shoot arrow state and...oh wait. Let's look at our abstract state class in C#
public abstract class State<T>
{
public virtual Enter(T owner){}
public virtual Execute(T owner){}
public virtual Exit(T owner){}
}
So what if I made a State called ShootArrow?
public class ShootArrow : State<EnemyBase>
{
public override Enter(EnemyBase owner)
{
owner.ShootArrow();
}
}
There's a huge issue with this approach, and that is EnemyBase doesn't have a ranged attack! Sure, I could've made one, but not every enemy needs a ranged attack, so that's not very object oriented to put one there...they could have a virtual ranged attack that's only implemented in classes that need to have a ranged attack, but what if two classes need to implement it that exact same way (like Archer and Boss1)? Then both classes would have duplicate code...no no no. Never think copied code. Always wrong. Not object oriented. You will get and F on the project. Bad bad bad.
But even here I had already jumped ahead of myself. Without putting all functionality for every enemy I ever want to have in my base class, I can't have any state inherit from State<EnemyBase> as it won't be able to call any functions it doesn't have. So, each thing inherited from EnemyBase will need to have its own state machine, so states can call the functions they'll need. I'll need things like
public class ShootBolt : State<Boss1>
{
public override Enter(Boss1 owner)
{
owner.ShootBolt();
}
}
instead. Then Boss1 can have a function that shoots bolts! Hooray! Oh wait....have you seen the problem yet? Archer needs to shoot arrows too...but I can't give the archer a state made for Boss1, the compiler would never allow it. So what if I made a class inbetween EnemyBase and Boss1 and archer called EnemyCanShoot : EnemyBase and then do Boss1 : EnemyCanShoot and Archer : EnemyCanShoot? Then my state could be public class ShootBolt : State<EnemyCanShoot> instead? That could work....if shooting a bolt was the only thing I ever needed to share between classes. What happens if Boss1 and BasicWizard need to teleport as well? Boss1 can't inherit from EnemyCanShoot AND EnemyCanTeleport, this is C# (oh yeah, this projects being made in C# and Unity3D), multiple inheritance isn't allowed. Even if it were C++ and we could do MI, that could start to really lead to some super sloppy code.
class Boss1 : public EnemyCanShoot, public EnemyCanTeleport, public EnemyCanSlash, public EnemyCanDie, public EnemyCanBreatheFire, public EnemyCanSwim, public EnemyDropsPickup
etc...yikes. So this doesn't seem like a good idea, especially when all those EnemyCan's all inherit from from the same EnemyBase and would be overriding different functions at the same time and trying to figure out which fricking Move function you actually wanna call like the one that swims or flies or teleports or asdfbgrwhrtw. Messy. More like EnemyCant. Ha. Jokes.
But really, maybe we could do something like an interface? Yeah, that could work, public class Boss1 : ICanShoot and public class Archer : ICanShoot that just have some sort of functionality to shoot. Problem is, interfaces can't have anything really in them, like variables or function definitions. So if Boss1 and Archer need to shoot the exact same way, you end up with redundant code. Insert Luke Skywalker "Nooooo" here.
Is there any hope out there? Is this super StateMachine not as awesome as I originally thought? Can I not have re-usable states everywhere? What to do? Ultimately, I had to face some kinda rough truths (at least for me). Sometimes, its okay to not object orient all the things. This idea of an abstract state machine presented in the book wasn't meant for what I was trying to use it for. That's not to say its not still awesome, it takes code away from your Boss1 code and breaks it down and makes it much more manageable and readable without alot of nasty switch statements. Which is wonderful. But I had to accept it, without a major code re-structure (which I really didn't want to do), I was going to have either some duplicate code or some enemies that had (potentially alot of) un-needed functionality. If I were to start this project over, I probably would've done things a bit differently. I might not have used this StateMachine approach as such a godlike over any other AI approach and make it so every enemy HAS to use it.
And you might be wondering "why didn't he just do this" or "why didn't he just do that" or some super thing that I didn't think of that magically does everything I was just trying to do. First, let me say I tried alot of things that I didn't even really mention in this article to get this approach of re-usable states to work that failed, so I may have attempted it. Secondly, this is a 5 week project where I have quite alot of other things to do, both in this project and outside of it too, so spending a week trying to get this perfect for all cases just wasn't in the cards. That being said, if someone has some way or technique that does let this work the way I was trying to, please share!!!! I'm very curious, and I'm sure there's a solution out there I didn't have time to try that works great and is magical and awesome and lovely. But that being said, here's how my story ends now:
There are 5 lines of duplicate code copied and pasted in my project now. It happened. And you know, I'm pretty okay with that. I made alot of object oriented code in this that I'm quite proud of (next post maybe) and some AI that's working nicely. And if the alternative is spending hours and hours getting an approach to do something its probably not truly meant for, only 5 line is great to me. Spending the time to completely object orient (assuming you are doing an object oriented approach, not something like data oriented) is usually worth it, but if you don't do it to its fullest because the game needs to get done, or because the approach you took is awesome and perfect except for one or two little instances, trust me: its not the end of the world, and your teacher isn't going to give you an F if your game is awesome.
--daviD Ward
Subscribe to:
Comments (Atom)