First things first; what is an FSM? (Finite State Machine)
In other words, it's a way to control logic flow for automated tasks. (E.g; bots)Originally Posted by Wikipedia
I'm writing this post for two reasons;
1) People tend to have a hard time implementing an FSM in their bots, or other programs, due to 'complexity', even though it's actually a very simple concept once seen.
2) Hopefully, this will progress current bot writers usage of logic, into something more fluid, and reliable.
An FSM consists of two main parts; The engine, and the states. (All source code will be posted at the bottom)
The Engine
An FSM engine is actually something incredibly simple, but most people make it far too complex, and hard to maintain due to either lack of knowledge on how to properly implement one, or the thought that 'it has to be this way to work properly'. The engine I'm showing you is, by no means, not the only implementation of an FSM. It is however, the most simplistic, and easiest to maintain out of all the ones I've seen. (There may be simpler ones, but I have not come across them.)
In essence, all the engine needs to do is the following:
- Determine which states there are to run.
- Determine the priority in which the states should run. (E.g; Combat before Resting)
- Determine if the state needs to run
- If the state needs to run, let the state do it's predefined logic.
- Otherwise, move on to the next state.
It's not nearly as complicated as it looks.
The State(s)
A state is just what the name implies. 'The state of the world (or logic system) that we are currently in, and where we would like it to be.'
Ok, so maybe the name isn't quite as 'literal' as it seems.
In short terms, a state really consists of 3 things.
- A priority. (We'll just use a numeric value. int.MinValue - int.MaxValue)
- A Boolean statement determining if the state needs to be run. (I.E; execute it's logic.)
- Execute the logic that is predefined for that state.
In our example, we'll implement a very simple FSM, including 2-3 states, to give an example of how it will work.
First things first, we need to create the main State class, that all other states will inherit from. (I'll explain why we do this first, rather than the engine, later)
We'll start off with the usual declarations:
This is an abstract class for 1 reason: We don't want developers/users creating an instance of the base 'State' class itself, as it will never hold any logic whatsoever. (Also note: We can easily create 'State's as an interface, but I choose not to. You'll see why below.)Code:namespace FiniteStateMachine { public abstract class State { } }
Now, we'll 'create' the 3 main pieces of the State class that make it useful for an FSM. (Get ready, this part is really difficult...)
Yep. That's pretty much it. We just covered the 3 basic parts of a State in terms of an FSM implementation.Code:namespace FiniteStateMachine { public abstract class State { public abstract int Priority { get; } public abstract bool NeedToRun { get; } public abstract void Run(); } }
Priority is self explanatory. (You can change it to a uint if you want the lowest priority to be 0, however, it really doesn't matter, unless you like 'high priority' to be low numbers.)
NeedToRun again is self explanatory. Do we need to run this state? If so, return true, if not, return false.
Run() is... well... you get the idea.
The way it is right now, is perfectly viable. However, I'm a lazy programmer, so I tend to avoid doing any messy sorting logic. .NET provides an interface called 'IComparable<T>' and 'IComparer<T>'. It allows us to implement a 'sorting' function in our classes, to make sorting easier. (E.g; List<T>().Sort(); ) We need both interfaces implemented due to how different collections use the comparing methods. (Some use CompareTo, others use Compare.)
Since we only really want to 'sort' based on priority (explained in the engine code section), we'll just compare the Priority properties of the states.
It really is that simple. Whenever we put a collection of states into a List<T> (as we will later), if we use the .Sort() method, it will sort the states by priority. Highest to lowest.Code:namespace FiniteStateMachine { public abstract class State : IComparable<State>, IComparer<State> { public abstract int Priority { get; } public abstract bool NeedToRun { get; } public abstract void Run(); public int CompareTo(State other) { // We want the highest first. // int, by default, chooses the lowest to be sorted // at the bottom of the list. We want the opposite. return -Priority.CompareTo(other.Priority); } public int Compare(State x, State y) { return -x.Priority.CompareTo(y.Priority); } } }
And that's pretty much it for the State class.
On to the engine!
Nothing special here, just a normal class. It's not abstract for one main reason: We ARE going to allow developers to override the Pulse() method we'll be creating, however, we also want to be able to use this class itself, as an FSM. This leaves quite a bit of customization.Code:namespace FiniteStateMachine { public class Engine { } }
The following is just some quick and dirty stuff, if you don't understand it, you should go back to the basics.
Fairly simple. We just created a List to hold all of our states, and a simple 'Pulse' method that will actually be carrying out our logic system.Code:using System.Collections.Generic; namespace FiniteStateMachine { public class Engine { public List<State> States { get; private set; } public Engine() { States = new List<State>(); } public virtual void Pulse() { } } }
Don't be alarmed: This next part is really simple as well.
That's it. Your whole logic system in a single method. Of course, we're leaving out some basic things, (and some more advanced stuff that I'll show you in a minute) like how to actually 'pulse' the engine, or how to load in the states we want.Code:namespace FiniteStateMachine { public class Engine { public List<State> States { get; private set; } public Engine() { States = new List<State>(); // Remember: We implemented the IComparer, and IComparable // interfaces on the State class! States.Sort(); } public virtual void Pulse() { // This starts at the highest priority state, // and iterates its way to the lowest priority. foreach (State state in States) { if (state.NeedToRun) { state.Run(); // Break out of the iteration, // as we found a state that has run. // We don't want to run any more states // this time around. break; } } } } }
Now, lets add a simple method to create a thread, that runs our FSM engine. For shits and giggles, lets base it off of FPS.
You'll notice; I create a new property 'Running' which is just a flag to let everyone (and ourselves) know if the FSM is actually running or not. I've also created the StartEngine, StopEngine, and Run methods. All of them are self explanatory, and the comments speak for themselves.Code:using System.Collections.Generic; using System.Threading; namespace FiniteStateMachine { public class Engine { private Thread _workerThread; public Engine() { States = new List<State>(); // Remember: We implemented the IComparer, and IComparable // interfaces on the State class! States.Sort(); } public List<State> States { get; private set; } public bool Running { get; private set; } public virtual void Pulse() { // This starts at the highest priority state, // and iterates its way to the lowest priority. foreach (State state in States) { if (state.NeedToRun) { state.Run(); // Break out of the iteration, // as we found a state that has run. // We don't want to run any more states // this time around. break; } } } public void StartEngine(byte framesPerSecond) { // We want to round a bit here. int sleepTime = 1000 / framesPerSecond; // Leave it as a background thread. This CAN trail off // as the program exits, without any issues really. _workerThread = new Thread(Run) {IsBackground = true}; _workerThread.Start(sleepTime); } private void Run(object sleepTime) { try { // This will immitate a games FPS // and attempt to 'pulse' each frame while (Running) { Pulse(); // Sleep for a 'frame' Thread.Sleep((int) sleepTime); } } finally { // If we exit due to some exception, // that isn't caught elsewhere, // we need to make sure we set the Running // property to false, to avoid confusion, // and other bugs. Running = false; } } public void StopEngine() { if (!Running) { // Nothing to do. return; } if (_workerThread.IsAlive) { _workerThread.Abort(); } // Clear out the thread object. _workerThread = null; // Make sure we let everyone know, we're not running anymore! Running = false; } } }
Ok, so now we've got a fully working FSM. Our only problem is, how to load the states into our list?
We have two options:
- Keep a running list of states we're allowed to load, and add them via States.Add(new StateDescendant());
- Load the via reflection, which gives us the ability to load multiple different DLLs, and not have to worry about maintaining a list of states to load.
Obviously we're going with #2.
Now, the following method is far from 'basic' stuff. It actually requires an understand of how late binding works, etc. Which is outside the scope of this tutorial.
Basically, you pass it a path to a DLL (or exe) and it will attempt to load any States that are defined in it. Keep in mind; it will NOT load any classes that are not public. This is how .NET is, and no, you cannot get around it.Code:public void LoadStates(string assemblyPath) { // Make sure we actually have a path to work with. if (string.IsNullOrEmpty(assemblyPath)) { return; } // Make sure the file exists. if (!File.Exists(assemblyPath)) { return; } try { // Load the assembly, and get the types contained // within it. Assembly asm = Assembly.LoadFrom(assemblyPath); Type[] types = asm.GetTypes(); foreach (Type type in types) { // Here's some fairly simple stuff. if (type.IsClass && type.IsSubclassOf(typeof(State))) { // Create the State using the Activator class. State tempState = (State) Activator.CreateInstance(type); // Make sure we're not using two of the same state. // (That would be bad!) if (!States.Contains(tempState)) { States.Add(tempState); } } } } catch (Exception ex) { // Feel free to change this to some other logging method. Debug.WriteLine(ex.Message, "Exceptions"); } }
Now that we've added some things, lets make a few simplistic states and give it a go.
Code:using System; namespace FiniteStateMachine { public class StateIdle : State { public override int Priority { // Idle obviously has the lowest value, // it just means we have nothing to do! get { return int.MinValue; } } public override bool NeedToRun { // Always run this one. get { return true; } } public override void Run() { Console.WriteLine("Idling...."); } } }And finally, we'll just create a basic console app to do the rest of the work.Code:using System; namespace FiniteStateMachine { public class StateNumberToHigh : State { private int number = 0; public override int Priority { get { return 5; } } public override bool NeedToRun { get { return number++ >= 10; } } public override void Run() { Console.WriteLine("Lowering the number by 20!"); number -= 20; } } }
Nothing special really. Just prints out the loaded states, and the names.Code:using System; using FiniteStateMachine; namespace FSM_Tester { class Program { static void Main(string[] args) { Engine engine = new Engine(); // Just load the actual DLL for now. engine.LoadStates("FiniteStateMachine.dll"); engine.States.Sort(); Console.WriteLine("Total states: " + engine.States.Count); foreach (State state in engine.States) { Console.WriteLine("State loaded: " + state.GetType().Name); } // Run the engine! (The very slow engine for now...) engine.StartEngine(3); Console.ReadLine(); } } }
And there you have it, an incredibly extensible FSM implementation you can use for your bots, or other automated tasks.
Source code download:
Filebeam - Free Fast File Hosting