Taking a closer look at the power provided in stack based finite-state machines.
Abstract:
I've blogged before on the various types of finite-state machines you could possibly use in the Terrarium, but I didn't really go into any depth on how you might take advantage of them. So I'm going to take this opportunity to talk about stack based finite-state machines, how your engine can quickly and easily interact with them, and propose an extension that allows for nested finite-state machines.
Requirements for a stack based FSM:
Well, the largest requirement is a stack where you can store state information. You can either have the engine store this stack for you, or allow the FSM to store the stack. I'm going to assume that the FSM is going to hold onto the stack for now, but we'll have to add some new rules later for nested state machines to operate properly. Since this is the .NET world I am going to take full advantage of delegates to implement our state machine. Each state will consist of a method callback and an optional data pointer to store extra data. We'll use an object for this, but you could strongly type these if you wanted to.
We'll encapsulate all of this data into an abstract base class that we'll expect each FSM to inherit from. This allows us to create a strong contract with the engine, so it won't be left wondering what to do once the FSM is added to it's queue. Our base class will provide access to the stack, provide a default idle implementation, and in the future could perform other important operations.
using System;
using System.Collections;
public delegate void StackFSMStateCallback(object extraData);
public class StackFSMState {
public StackFSMStateCallback callback = null;
public object extraData = null;
public StackFSMState(StackFSMStateCallback callback, object extraData) {
this.callback = callback;
this.extraData = extraData;
}
}
public abstract class StackFSM {
private Stack stateStack = new Stack();
public StackFSMState GetNextState() {
if ( stateStack.Count > 0 ) {
return (StackFSMState) stateStack.Pop();
} else {
return new StackFSMState(new StackFSMStateCallback(this.Idle), null);
}
}
protected void SetNextState(StackFSMState state) {
stateStack.Push(state);
}
public virtual void Idle(object extraData) {
SetNextState(new StackFSMState(new StackFSMStateCallback(this.Idle), null));
}
}
Creating our first FSM based on the stack:
Creating a new FSM based on the stack implementation is pretty easy. We just need to override the Idle state method and provide our own implementation. What would happen if we just wanted to randomly pop a new state onto the stack to execute 10% of the time. This would actually be pretty easy. BasicFSM does just that. We are adding Console.WriteLine calls so we can understand which states are actually executing. If we are in Idle we'll print that we are in that state, else we'll print we are in the Basic state. Notice that I'm calling base.Idle whenever I'm not doing any processing. This isn't required, but since base.Idle simply pops a new Idle state onto the stack, I might as well use it. I could just as easily pop the state onto the stack myself, or simply not pop anything at all, since the GetNextState method makes sure we always return a valid state event.
public class BasicFSM : StackFSM {
Random rand = new Random();
public override void Idle(object extraData) {
Console.WriteLine("Running an Idle state");
if ( rand.Next(0, 10) == 5 ) {
SetNextState(new StackFSMState(new StackFSMStateCallback(this.BasicState), null));
} else {
base.Idle(extraData);
}
}
public virtual void BasicState(object extraData) {
Console.WriteLine("Running a basic state");
}
}
To demonstrate the rest of the code, let's change BasicFSM.Idle so that we randomly select which method we use to pop state back onto the stack. We'll call this one UnsureFSM since we might run into this situation if a developer was unsure as to what they needed to do. Or a tester might throw this code in to try and whack our state machine implementation.
public class UnsureFSM : StackFSM {
Random rand = new Random();
public override void Idle(object extraData) {
Console.WriteLine("Running an Idle state");
if ( rand.Next(0, 10) == 5 ) {
SetNextState(new StackFSMState(new StackFSMStateCallback(this.BasicState), null));
} else {
switch(rand.Next(0, 3)) {
case 0:
base.Idle(extraData);
break;
case 1:
break;
case 2:
SetNextState(new StackFSMState(new StackFSMStateCallback(this.Idle), null));
break;
}
}
}
public virtual void BasicState(object extraData) {
Console.WriteLine("Running a basic state");
}
}
Implementing a basic engine:
If you take all of the code up to now, you'll get a basic FSM implementation, but no engine to run it. Since I want you to be able to test the process I am going to add a basic engine that calls into our FSM based on whatever the current state might be. This'll be a basic queue for now where we add each of our FSM implementations, but you'll probably want a full on game scheduler running this at a later time. I'll definitely be talking about game schedulers in the future so stay tuned.
public class FSMEngine {
private static void Main(string[] args) {
Queue fsmQueue = new Queue();
fsmQueue.Enqueue(new BasicFSM());
fsmQueue.Enqueue(new UnsureFSM());
while(true) {
StackFSM fsm = (StackFSM) fsmQueue.Dequeue();
StackFSMState state = fsm.GetNextState();
state.Callback(state.ExtraData);
fsmQueue.Enqueue(fsm);
Thread.Sleep(500);
}
}
}
Compile all this code into an executable and run it. You should get some pretty interesting results and you'll be able to play with the concepts involved.
Exercising the stack:
So far we aren't exercising the stack. What would it take to really exercise a stack based FSM? Well, states that push multiple states onto the stack of course. We basically need to break out of the push a new state on, pop it off next turn, rinse, repeat. The one thing that is really good at defining multiple states is a movement algorithm. These types of algorithms generally define multiple waypoints to be tackled along your path to the destination. We can also exercise the code-path where we push a state back onto the stack because it isn't complete yet.
So the MovementFSM starts in the Idle event and decides that 50 percent of the time it'll pick a target. If no target it selected it pops on a new idle state, however, if we grab a target to move towards, then we have to extrapolate the points along the path that we'll be moving towards. The ExtrapolateWayPoints handles this task for us by computing a random number of intermediate points and then popping these onto the stack. We compute the points from closest to farthest away, and then push the on the stack in reverse order so the closest point is at the top of the stack.
Once the movement points are on the stack, we fall out and see what happens. Each point is moved towards in the Move state method. We are now using the extraData to store the point we are moving towards, so we can print this out and see exactly where the FSM is moving. At some point (10 percent of the time), we don't actually reach our destination waypoint, so we pop the waypoint back onto the stack. This is an important refinement since it shows how easy it is to continue on our previous state with the same data. If we didn't reach out location because it is unreachable, then we could even pop on additional waypoints to refine the path.
One of the most powerful features of the stack based FSM is made apparent in the Move state method. When the current state is complete, no work has to be done in order to transition to the next state. Nothing new has to be done. You can do new things, but you don't have to. Removing this transition logic from certain algorithms makes them much easier to implement. Here is the code:
public class MovementFSM : StackFSM {
Random rand = new Random();
public override void Idle(object extraData) {
Console.WriteLine("Running in Idle State: " + name);
Point target = PickTarget();
if ( target != Point.Empty ) {
ExtrapolateWayPoints(target);
} else {
base.Idle(extraData);
}
}
public virtual void Move(object extraData) {
if ( extraData != null ) {
Point wayPoint = (Point) extraData;
Console.WriteLine("Moving towards " + wayPoint.ToString());
if ( rand.Next(0, 10) == 1 ) {
// Move not completed
SetNextState(new StackFSMState(new StackFSMStateCallback(this.Move), extraData));
} else {
// We are done, assume the next state is on the stack.
// Bonus! No transition required!
}
}
}
private void ExtrapolateWayPoints(Point target) {
Point[] wayPoints = new Point[rand.Next(1, 20)];
Point start = new Point(rand.Next(0, 100), rand.Next(0, 100));
int distanceX = target.X - start.X;
int distanceY = target.Y - start.Y;
for(int i = 0; i < wayPoints.Length - 1; i++) {
wayPoints[i] = new Point(
distanceX / wayPoints.Length * i + start.X,
distanceY / wayPoints.Length * i + start.Y
);
}
wayPoints[wayPoints.Length-1] = target;
// Pop the way-points on in reverse order so the closest is on the top
// of the stack.
for(int i = wayPoints.Length - 1; i > -1; i--) {
SetNextState(new StackFSMState(new StackFSMStateCallback(this.Move), wayPoints[i]));
}
}
private Point PickTarget() {
if ( rand.Next(0, 2) == 1 ) {
return new Point(rand.Next(0, 100), rand.Next(0, 100));
}
return Point.Empty;
}
}
Additional Features:
After a good deal of thought, I'm going to save the nested FSM implementation for an additional article. There are many ways to implement nested FSMs with respect to where their stack state is stored and I'd like to thoroughly explain these. I might also talk about stack control methods in the future and add that to the StackFSM implementation. I think some worthy things to note would be stack compression (always a big subject), using fixed sized stacks, replacing stacks entirely and using your own strongly typed implementations, as well as some methods for better taking advantage of the extraData object.