Finite State Machines
So after a long hiatus I have decided to jump back into the Flash scene. I am going to kick off my return with a continuation of the Building a Game Stucture series. Today we look into FSM ( Finite State Machines ). FSMs are used as the basic AI for most games, especially RPG / Platformer / RTS type games.
What is an FSM / What is it used for?
An FSM can be used to determine the behavior of an entity based on specific conditions. Essentially they imbue an entity with the illusion of intelligence. Coding a state machine is a simple matter. There are in fact numerous ways to implement an FSM and there isn’t necessarily one “right” way to do it.
First We will look at a simple, although potentially problematic approach.
public function update() : void { if( health < 0 ) { changeState( DIE_STATE ); } switch( currentState ) { case IDLE_STATE: patrol(); if( isEnemySighted ) { changeState( CHASE_STATE ); } break; case CHASE_STATE: chaseEnemy(); if( isEnemyInRange ) { if( health < 30 && mana > 20 ) { castHeal(); } else { attackEnemy(); } } break; case DIE_STATE: if( isDeathAnimationComplete ) { removeEntity(); } else { playDeathAnimation(); } break; } }
As you can see setting up a switch and several if statements can accomplish basic AI behavior. The problem with this approach begins to surface as more states, conditions, and transitions are introduced. Imagine how big of a monster it would be to edit this structure of code on an entity that had over a dozen different states and transitions. Also it would be hard to switch out the behaviors of entity. For example, what if you wanted the player to be able to control this unit? You would have to create a separate class altogether. More on that later.
The State Design Pattern
The best way that I have found to implement an extensible FSM is with what is called the State Design Pattern. With this approach we will be embedding the rules for the state transitions within the states themselves.
Actionscript doesn’t allow for any type of function templates unfortunately. So we will have to work around that in order to allow for varying types of entities to be used in our FSM. The user will be forced to do his/her own error checking, so only a small annoyance. With states, generally you will want to have transitions when the states are being changed, so our pattern will allow for an enter, execute, and exit function.
Here is the Interface for the states:
public interface IState extends IEventDispatcher { function setEntity( a_entity:* ) : void; function getEntity() : *; function enter():void; function execute():void; function exit():void; }
As you can see the structure is actually quite simple. The states will contain a reference to the entity they are operating upon. Here is an example of a somewhat fleshed out state:
public class PatrolState extends EventDispatcher implements IState { public function setEntity( a_entity:* ) : void { if( !(a_entity is Unit) ) { throw new Error( "<PatrolState> a_entity must be of type Unit!" ); } m_entity = a_entity; } public function getEntity() : * { return m_entity; } public function enter():void { // set up patrol path and steering behaviors } public function execute():void { // if enemy is close, set state to chase state // else continue patrolling } public function exit():void { // clean up patrol paths // remove steering behaviors } private var m_mine:Mine; private var m_base:Building; private var m_entity:Harvester; }
So now that we have a state set up, we can improve this system a lot by creating a reusable state machine that handles the switching / updating of the states. Here is the interface:
public class StateMachine { public function StateMachine( a_owner:Entity, a_currentState:IState = null, a_globalState:IState = null ) public function update() : void public function dispose() : void public function changeState( newState:IState ):void public function changeGlobalState( newState:IState ):void public function revertToPreviousState() : void }
In my implementation I allow for a “global” function as well, which will be called every tick in addition to the actual states. This may or may not be used depending on the behavior you are looking for. Also, a reference is being held to the “previous state” so that temporary behavior can be given and then the entity can switch back to what it was doing before. For instance, if a unit was on a patrol path and spots an enemy…it can switch to an attack state, and then once the enemy is dead it can revert to it’s patrol path.
Here is a quick example I created in order to display the FSM in action. ( might be a bit shitty, but I was in a hurry 
)
So as you can, FSM’s can be used to create fairly complex and intelligent behavior. Not only that, but imagine creating an RTS style game where units are given commands by the player and the units all follow those orders. Rather than creating dozens of different classes with built in behaviors based on if they are on the players team or being controlled by the AI, you could toss in the correct states to the FSM controller. Then let’s say you decided to give one of those units top down shooter style controls if you clicked on them…that could be done as well, again by just changing the state. So the possibilities are limitless.
With that, I would like to also give some reference to another useful method which works well in some less complex scenarios, instead of this full blown approach. For instance, I actually used this method to manage the 3 states of a “ball” which can be grabbed, aimed, and then launched on another project of mine.
Be sure to add me to your RSS reader if you haven’t already. I plan to slowly get back to more consistent posting very soon. Sorry about the long wait guys! So until next time…be sure to download the new code and examples at my google project page, and here a list of the updates to the game structure code:
Code Changes
- GameFactory:
- If no parent is specified for getEntity function, it will default to the instance of the gameworld ( if it exists )
- No longer need to specify entity t ype on getEntity…IE: var myBoid:Boid = m_factory.getEntity( “boid” ) as Boid. You can now take off the “as Boid”
- GameWorld
- Fixed error with the Gameworld’s bounds setup.
- Moving Entity
- Added BOUNDS_STOP behavior
- Fixed the bounds behaviors for entities inside of other entities in different locations than 0,0
- Entity
- Entity now implements IEntity which will improve use with other classes etc such as the game factory.
- Fixed the bounds size calculation
- Root
- Made a change to the stageWidth/Height thing that makes it lookup what the dimensions are.
- Follow Path
- Fixed so that if it is set to “not” patrol, it will not create an error.
(7 votes, average: 5.00 out of 5)
Loading ...
mitomane said
am August 13 2009 @ 11:31 am
welcome back
and thanks for this great post.
Tariq said
am August 13 2009 @ 12:03 pm
Nice job on this article. Good to see your back posting blogs again.
Meedoc said
am August 13 2009 @ 12:42 pm
The demo doesn’t work if you press a key after the restart and before the robot reaches the mine. The robot doesn’t collect gold and just stop to move when he arrives at the center of the mine.
Besides, nice post!
Colby Cheeze said
am August 13 2009 @ 12:46 pm
Odd…well I did say it was pretty shitty! Hopefully it just gives you an idea of how to implement the code etc.
8bitjeff said
am August 13 2009 @ 9:56 pm
Hey Colby! Nice work. This is something I looked into a while back after reading the Head First Design Patterns book, but I never fully implemented it. I have a version that is a little deeper than the GYW version, but not nearly as complete in an OOP sense as yours. That framework of yours is really coming around!
Orlando said
am August 14 2009 @ 8:00 am
Welcome back!
I was so excited to see a new update in my RSS feed, I hope to see a lot more!
nicoChico said
am August 14 2009 @ 8:19 am
Awesome.. keep writing.
Dan said
am August 18 2009 @ 12:10 am
WOW, so I’ve been looking for a good gaming blog to follow for awhile now… and I just came across yours… AMAZING STUFF! This is exactly what I’ve been looking for. I’ve been reading your blog for about 2 hours now and can stop. Thank you soo much, and keep up the great work!
Porter said
am August 19 2009 @ 7:47 pm
Awesome post, this is a great example of code. I love looking at how other people code things and this is a great example of what I look for. I actually used this in my last link dump, good stuff.
Brett said
am August 25 2009 @ 12:07 pm
Had downloaded your code since I came across it while pretty much starting to write my own version of the same thing. Took me a while to follow through all your code which I wish you had commented but really impressively written. You did alot of the work for me and really well laid out. I actually have written my own FSM with pretty much the same style as yours but will be taking a look at yours as I plan to update my code with your newest. By the way, I am using your code quite heavily for my own steering game I am writing and I did find a bug in one of your Vector methods, upon fixing it broke some of your steering which I didn’t pursue.
Basically, the issue I found was the following, in the code if you get a rounding error due to something directly facing something when you ask for the angle you get a NAN when pointing at something or point directly away.
public function angleTo( vector:Vector2D ):Number
{
return Math.acos( dotOf( vector ) / ( length * vector.length ) );
}
Need to check the return and see if it is out of range of acos and if is return 0 or pi depending on which direction.
I would post my corrected code but I am at work and don’t have it. Also, it is under a different method because it does screw up some of the steering behavior once corrected.
Really happy to see you reposting and really like the infastructure you have created.
Brett said
am September 18 2009 @ 1:52 pm
Hey, just imported this version into my project. I will research why but right now when I remove a Entity from the factory it draws the Sprite on the camera in the spot of removal forever. This is something that happened after the update and once I find out what is causing I will get back to you. Just thought you should know. Also, seems to get real slow after a bit after this happens.
Brett said
am September 18 2009 @ 2:32 pm
Wish I had researched before posting nonetheless found the problem…
public function removeChild( a_id:String ):void
{
if( Entity( _entityMap[ a_id ] ) == null )
{
throw new Error( ” There was no entity with a matching id.” );
return;
}
//_entityMap[ a_id ].dispose();
delete _entityMap[ a_id ];
}
This block of code from Entity.as has the line _entityMap[ a_id ].dispose(); commented out. I am not sure if this was because it was planned for later or what nor did I research what this map did but needless to say uncommenting it fixed the removal issue.
So after change looks like this and works as expected again along with the super slowness/freezing goes away. I assume this non removal is hogging up all the memory. Anyway, hope this was helpful.
public function removeChild( a_id:String ):void
{
if( Entity( _entityMap[ a_id ] ) == null )
{
throw new Error( ” There was no entity with a matching id.” );
return;
}
_entityMap[ a_id ].dispose();
delete _entityMap[ a_id ];
}
Colby Cheeze said
am September 19 2009 @ 11:17 am
Thank you Brett. This was an accident of mine. I believe that I was testing something out and forgot to uncomment the code before releasing it.
Why you should use Flex and Flash Together | Internet Superstars said
am September 30 2009 @ 8:35 pm
[...] what happens when you switch between different states. (8-bit rocket has a good tutorial, so does Cheezeworld) This will cost you some time now, but you’ll have a state machine ready to go for the [...]