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
No comments:
Post a Comment