Intro

I would like to start by saying, I am not a computer scientist. The only degree I have is an Associates in visual communications. I am a self taught developer and have no formal training in any kind of programming. What follows is my understanding and implementation of a Finite State Machine (FSM). That being said, I am open to corrections and suggestions. Also a lot of this is based around cocos2d, since that is what I am using for the AAS (Awesome Adventure System).

What is an FSM?

An FSM is basically a way to simplify and organize complicated logic associated with an object. Well, what does that mean? Say you have a robot, and you want it to perform various tasks. Tasks might include walk, talk, and kill. So, how would we program our robot to do all these things? Well, we could create some complex conditional logic based on if/switch. This is less than ideal especially when we want to change who we want our robot to kill. An FSM in its simplest form is a machine (robot) and its states (kill, walk, talk etc.). States are swapped in and out of our machine in order to make it do different things.

That’s great, but how does it work?

If you look at the code below, you will see the header for the FSM that I am using in the AAS. I have created an Actor class that is a subclass of CCSprite. Each Actor has its own FSM and is the owner of the FSM. You can think of the Actor as the car and the FSM as the engine.

#import "FSMState.h"

@interface FSM : NSObject
{
	id _owner;
	FSMState *_currentState;
	FSMState *_globalState;
	FSMState *_previousState;
}

- (id) initWithEntity:(id) entity;
- (BOOL) inState:(Class) state;
- (void) update;
- (void) changeState:(FSMState *) newState;
- (void) changeGlobalState:(FSMState *) newState;
- (void) revertToPreviousState;

@end

The initWithEntity method is simply a way for an Actor to create its FSM and pass itself in as the owner. We need the FSM to know what object to control so whatever state is active will also have a reference to that object.

- (id) initWithEntity:(id) entity
{
	if((self = [super init]))
	{
		_owner = [entity retain];
	}
	
	return self;
}

Ok, now we want to add a state to our machine so it can do something. In our changeState method we will set the previous state to our current state first. This is so that we can easily revert to the previous state. Next, we will exit the current state and set our new state as the current state.

- (void) changeState:(FSMState *) newState
{
	[newState retain];
	
	if(_previousState) [_previousState release];
	_previousState = _currentState;
	
	if(_currentState) [_currentState exit];
        
	_currentState = newState;
	
	[_currentState setEntity:_owner];
	[_currentState enter];
}

Here is the revertToPreviousState method which is pretty much self explanatory. All it does it call the changeState method with the previous state.

- (void) revertToPreviousState
{
	[self changeState:_previousState];
}

Next we have the concept of a global state. A global state is a state that executes without exiting the current state. Here is our changeGlobalState method, which is very similar to the changeState method.

- (void) changeGlobalState:(FSMState *) newState
{
	if(_globalState) [_globalState exit];  
	_globalState = newState;
	
	[_globalState setEntity:_owner];
	[_globalState enter];
}

The last method in our FSM is the update method. This is the method that will get called in your main game loop. This will just call the execute method on our current and global states so they can update as well.

- (void) update
{
	if(_globalState) [_globalState execute];
	if(_currentState) [_currentState execute];
}

Creating the states

Below is the header for the base class for the states that will be loaded into the FSM. It contains a class method for getting an instance of our state. This will make it easy to create and load our states in the FSM. We have an entity property that is a reference to our Actor which the state will manipulate. The enter method is called when the state is loaded, the execute method is called in our game loop, and the exit method is called when we unload our state.

@interface FSMState : NSObject
{
	id _entity;
}

+ (id) state;

- (void) setEntity:(id) ent;
- (id) getEntity;

- (void) enter;
- (void) execute;
- (void) exit;

@end

The walk state

How you build your states is dependent on what type of game you are building, what the object needs to do, and many other variables. Here is a sample of a simple walk state. I create a new class method to get an instance of the state. I don’t want to use the default one in my base class in this instance because I want to pass a path to the state. The path is simply an array of tile coordinates that are found using an A* path finding algorithm.

+ (id) stateWithPath:(NSMutableArray *) path
{
	WalkState *state = [[WalkState alloc] init];
	state.path = [path retain];
	return [state autorelease];
}

In the enter method I call a walk next method which will walk my sprite to the next tile in the path. I am getting the tile size for my map to translate the tile coordinates into an actual position in the map. I then grab the next tile I have to move to from the path array and use some cocos2d magic to move my sprite to the new tile location.

- (void) enter
{
	[self walkNext];
}

- (void) walkNext
{
	int tileSize = [AASGameManager tileSize];
	Actor *ent = (Actor *) _entity;
	
	PathFindNode *currNode = (PathFindNode *)[path 
		objectAtIndex:path.count-1];

	float nodeX = currNode->nodeX * tileSize;
	float nodeY = currNode->nodeY * tileSize;
	
	id walkMove = [CCMoveTo 
			actionWithDuration:.25 position:ccp(nodeX, nodeY)];

	id endWalkFunc = [CCCallFuncN actionWithTarget:self 
			selector:@selector(endWalkNext)];

	id walkSequence = [CCSequence actions:walkMove, endWalkFunc, nil];
	
	[ent runAction:walkSequence];
}

When the move is complete I call the endWalkNext method. This removes the node that I just moved to from our path array, checks for the end of the path, and walks to the next node or loads a stand state via the stand method.

- (void) endWalkNext
{
	Actor *ent = (Actor *) _entity;
	
	[path removeLastObject];
	
	if(path.count == 0)
	{
		[path release];
		[ent stand];
		return;
	}
	
	[self walkNext];
}

In this example state I didn’t use the execute state. The reason being cocos2d handles all the animation nicely without having to worry about movement in the game loop.

Loading the states

Here are the methods in my Actor class that will trigger a state change. The stand method will simply load an instance of the StandState class in the state machine. The walk to class will take a point in the map (found via a tap in my case) and use an A* algorithm to find a path. Once the path is found I can load a new WalkState into the state machine and pass it the path I just found.

- (void) stand
{
	[stateMachine changeState:[StandState state]];
}

- (void) walkTo:(CGPoint) point
{
	if([self spaceIsBlocked:point.x :point.y]) return;
	
	if([stateMachine inState:[WalkState class]]) [self stand];
	
	int tileSize = [AASGameManager tileSize];
	
	int startX = floor(self.position.x/tileSize);
	int startY = floor(self.position.y/tileSize);
	
	NSMutableArray *path = [[astar 
			findPath:startX :startY :point.x :point.y] retain];

	[stateMachine changeState:[WalkState stateWithPath:path]];
	[path release];
}

The End?

This is just part one of my postings on the use of an FSM. The next part will have a sample application with it as well. At the moment I am having computer problems at home so I couldn’t get a demo in time for my #iDevBlogADay post. As always I am open to comments and suggestion.