[Bot Developers]A simple, but effective FSM for your bots.

[Apoc]

First things first; what is an FSM? (Finite State Machine)

Originally Posted by Wikipedia

A finite state machine (FSM) or finite state automaton (plural: automata) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an abstract model of a machine with a primitive internal memory.

Finite-state machine - Wikipedia, the free encyclopedia

In other words, it's a way to control logic flow for automated tasks. (E.g; bots)

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:

1. Determine which states there are to run.
2. Determine the priority in which the states should run. (E.g; Combat before Resting)
3. Determine if the state needs to run
4. If the state needs to run, let the state do it's predefined logic.
5. 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.

1. A priority. (We'll just use a numeric value. int.MinValue - int.MaxValue)
2. A Boolean statement determining if the state needs to be run. (I.E; execute it's logic.)
3. 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:

namespace FiniteStateMachine
{
    public abstract class State
    {
    }
}

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.)

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...)

namespace FiniteStateMachine
{
    public abstract class State
    {
        public abstract int Priority { get; }

        public abstract bool NeedToRun { get; }

        public abstract void Run();
    }
}

Yep. That's pretty much it. We just covered the 3 basic parts of a State in terms of an FSM implementation.

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.

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);
        }
    }
}

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.

And that's pretty much it for the State class.

On to the engine!

namespace FiniteStateMachine
{
    public class 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.

The following is just some quick and dirty stuff, if you don't understand it, you should go back to the basics.

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()
        {
            
        }
    }
}

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.

Don't be alarmed: This next part is really simple as well.

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;
                }
            }
        }
    }
}

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.

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.

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;
        }
    }
}

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.

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:

1. Keep a running list of states we're allowed to load, and add them via States.Add(new StateDescendant());
2. 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.

        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");
            }
        }

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.

Now that we've added some things, lets make a few simplistic states and give it a go.

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....");
        }
    }
}

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;
        }
    }
}

And finally, we'll just create a basic console app to do the rest of the work.

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();
        }
    }
}

Nothing special really. Just prints out the loaded states, and the names.

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

[ugkbunb]

thank you for the post

[Nesox]

Very nice Apoc. Might implement this

[BottMaster]

Absolutely a great post. Thank you so much.

[H4wker]

Superb. Thanks.

[SKU]

Thanks

FILLAR

[Robske]

Incredible, thanks

[dekz]

great read thanks

[SKU]

Can't believe how fluent the bot works now with this implementation of a FSM. Pulsing every endscene (yes, overkill 4tw), no lag at all, and a very easy way to add / change the bot logic. Thanks again.

[WinRawr]

Nice post Apoc, Altho i'm not using it (yet?). Thanks

[Apoc]

Originally Posted by SKU

Can't believe how fluent the bot works now with this implementation of a FSM. Pulsing every endscene (yes, overkill 4tw), no lag at all, and a very easy way to add / change the bot logic. Thanks again.

That's the whole point.

I've seen A LOT of bots implement an FSM assuming they need to use enums to represent what state they're in. There's absolutely no need to, and it really hurts extendability, and much more, maintainability.

Isn't it easier to just go to the class State<name> instead of searching through a function that can easily be 700+ lines long?

Also, if you want to have the FSM pulse only every n frames, it's a simple addition.

        public Engine(int pulseFrames):this()
        {
            PulseFrames = pulseFrames;
        }

        public ulong FrameCount { get; private set; }
        public int PulseFrames { get; set; }
        public virtual void Pulse()
        {
            FrameCount++;
            if (PulseFrames % (int) FrameCount != 0)
            {
                return;
            }
            // 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;
                }
            }
        }

[Apoc]

Some quick changes since someone requested it. Here's an example on how to run a state based on the same 'frequency' aspect as the engine. (This is useful if you only want to check states once in a blue moon; I.E: new talents to place, etc.)

// 
// Copyright © ApocDev 2009 <apoc@apocdev.com>
// 
using System;
using System.Collections.Generic;

namespace FiniteStateMachine
{
    public abstract class State : IComparable<State>, IComparer<State>
    {
        public abstract int Priority { get; }

        public abstract bool NeedToRun { get; }

        /// <summary>
        /// Determines the frequency (Frame count) between each attempt
        /// to check, and run, this state.
        /// </summary>
        public virtual int Frequency { get { return 1; } }

        #region IComparable<State> Members

        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);
        }

        #endregion

        #region IComparer<State> Members

        public int Compare(State x, State y)
        {
            return -x.Priority.CompareTo(y.Priority);
        }

        #endregion

        public abstract void Run();
    }
}

// 
// Copyright © ApocDev 2009 <apoc@apocdev.com>
// 
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Reflection;
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 Engine(int pulseFrames) : this()
        {
            PulseFrames = pulseFrames;
        }

        public List<State> States { get; private set; }
        public bool Running { get; private set; }
        public ulong FrameCount { get; private set; }
        public int PulseFrames { get; set; }

        public virtual void Pulse()
        {
            FrameCount++;
            if (PulseFrames % (int) FrameCount != 0)
            {
                return;
            }
            // This starts at the highest priority state,
            // and iterates its way to the lowest priority.
            foreach (State state in States)
            {
                if (state.Frequency % (int) FrameCount == 0)
                {
                    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;

            Running = true;

            // 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;
        }

        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.
                        var 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");
            }
        }
    }
}

Note: Frequency is VIRTUAL. That means, you don't need to override it if you want to run the state every frame. It's really only useful if you run it every 2+ frames.

[vulcanaoc]

wonderful, i am going to implement this into my libraries. +rep

[Patricker]

I was looking through your code (planning on using this beauty) and I noticed something I thought seemed wrong. You are only sorting the states on instantiation, but not on each pulse. So if the priority of a state changes it will stay in the same place instead of moving up or down the list as needed. Shouldn't it be:

 public virtual void Pulse()
        {
            States.Sort();
            // 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;
                }
            }
        }

Let me know what you think.

[Patricker]

I would normally just edit my previous post, but this seemed like it was different enough to post separately:

I added some new options to allow for more flexibility without really any added complexity. Basicaly I changed the code so that instead of just calling Run each Pulse it uses an Enter/Update/Exit type cycle. This allows you to run certain code only when the State starts and ends, though you can of course just type return; in the abstract blocks and the behaviour will be just like the original code.

Also I added code to keep track of the current state and to enter/update/exit as needed.

Updated State Code:

namespace FiniteStateMachine
{
    public abstract class State : IComparable<State>, IComparer<State>
    {
        public abstract int Priority { get; }

        public abstract bool NeedToRun { get; }

        #region IComparable<State> Members

        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);
        }

        #endregion

        #region IComparer<State> Members

        public int Compare(State x, State y)
        {
            return -x.Priority.CompareTo(y.Priority);
        }

        #endregion

        //Changed by Me to allow for more flexible state machine
        public abstract void Enter();

        public abstract void Update();

        public abstract void Exit();
    }
}

Updated Engine Pulse Code:

       public virtual void Pulse()
        {
            //ADDED: By ME (was missing from original, now re-sorts the list on each pulse)
            States.Sort();

            // This starts at the highest priority state,
            // and iterates its way to the lowest priority.
            foreach (State state in States)
            {
                if (state.NeedToRun)
                {
                    //if we are changing to a new state then exit the old one and enter the new one
                    if (state != CurrentState)
                    {
                        //Exit current state
                        CurrentState.Exit();

                        //track new state
                        CurrentState = state;
                        //enter new state
                        CurrentState.Enter();
                    }

                    //Update State
                    state.Update();

                    // 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;
                }
            }
        }

Let me know what you think.