Finite State Machines, Part 1

Getting Started

BaseGameEntity

The first thing we need to do is to define a base class to represent different entities in a game which can have an FSM applied to them. For the purposes of this simple example, all that the base entity class really requires is a unique identifier, Id, by which we can refer to the entity. For convenience, we are also going to add some additional properties and a message to reduce the amount of duplication when we are logging out the entity's actions to the output window: Name, the name of the entity, Color, the color that the text output by the entity should be, and LogAction(), which writes a message to the console for the entity.

For thread-safety, we're going to implement some locking around the incrementing of the unique identifier seed that the BaseGameEntity class uses. It is a bit of overkill for such a simple example, but it is good practice to think about thread-safety with any writable global variables.

Aside from the previously mentioned properties and methods, we will define an abstract Update() method, which will be called each frame in order to update the FSM machine for the entity.

The ConsoleUtilities class referenced by LogAction() is a simple utility class which provides a wrapper around actions which interact with the .NET System.Console class.

public abstract class BaseGameEntity {
    private static int nextValidId;
    private static readonly object SyncRoot = new object();

    private int _id;
    public int Id { 
        get { return _id; }
        private set {
            Debug.Assert(value >= nextValidId, "Invalid id");
            _id = value;
            lock (SyncRoot) {
                nextValidId = value + 1;
            }
        } 
    }
    public string Name { get; set; }
    public ConsoleColor Color { get; set; }

    protected BaseGameEntity(string name) {
        Id = nextValidId;
        Name = name;
        Color = ConsoleColor.White;
    }

    public abstract void Update();

    public void LogAction( string message) {
        ConsoleUtilities.SetTextColor(Color);
        Console.WriteLine("{0}: {1}", Name, message);
    }
}

IState

With the BaseGameEntity class defined, we can move on to define an interface to represent the different states which our entity may be in, in the finite-state machine. This interface consists of three methods:

• Enter(TEntity entity): This method will be called when the entity transitions from another state into this state.
• Execute(TEntity entity): This method will be called each frame that the entity is in this state, to update the entity according to the logic of this state.
• Exit(TEntity entity): This method will be called when the entity transitions from this state into another state.

To understand how this works, let us take for example a simple scenario where we have two states, A and B. We will start with our entity in state A. Let us assume that the Execute method of state A contains logic to transfer the entity into state B. In this case, the control flow for a frame would be:

1. A.Execute()
2. A.Exit()
3. The current state changes from A to B
4. B.Enter()

public interface IState<in TEntity> where TEntity: BaseGameEntity {
    void Enter(TEntity entity);
    void Execute(TEntity entity);
    void Exit(TEntity entity);
}

Miner Bob

With that groundwork out of the way, we can move on and define the protagonist of this little example, Miner Bob. Miner Bob is a pretty stereotypical old-timey Western prospector. He lives alone in his shack, and spends his time sleeping and mining for gold. When he's filled his pockets with gold dust, he tramps off to town to deposit it in the bank, and when he gets thirsty, he also heads into town to spend his hard-earned geld on rotgut whiskey. When he gets tired from all his mining, banking and drinking, he heads back to the shack and takes a nap. It's a simple life, but it works for Bob.

Let's get started defining a class to represent Miner Bob.

public class Miner : BaseGameEntity {
    public const int ComfortLevel = 5;
    private const int MaxNuggets = 3;
    private const int ThirstLevel = 5;
    private const int TirednessThreshold = 5;

    private IState<Miner> _currentState;

    private int _goldCarried;
    private int _thirst;
    private int _fatigue;

    public Location Location { get; set; }

    public int GoldCarried {
        get { return _goldCarried; }
        set {
            _goldCarried = value;
            if (_goldCarried < 0) _goldCarried = 0;
        }
    }
    public bool PocketsFull { get { return _goldCarried >= MaxNuggets; } }

    public bool Fatigued{ get { return _fatigue > TirednessThreshold; }}
    public void DecreaseFatigue() {
        _fatigue--;
    }

    public void IncreaseFatigue() {
        _fatigue++;
    }

    public int Wealth { get; set; }

    public void AddToWealth(int val) {
        Wealth += val;
    }

    public bool Thirsty { get { return _thirst >= ThirstLevel; } }

    public void BuyAndDrinkAWhiskey() {
        _thirst = 0;
        Wealth -= 2;
    }
    // continued...
}

First off, we've got some constants that control Bob's behavior.

• ComfortLevel: This represents the amount of money Bob wants to have in the bank. He's not greedy, he just wants to be relatively comfortable, so when he's mined this much gold, he's happy to go home and hang out, rather than continuing to toil on his claim.
• MaxNuggets: This is the number of gold nuggets that Bob can stuff in his pockets before they are full, and he needs to go to the bank and make a deposit. Unfortunately, Bob doesn't have a backpack or a mule he can load up...
• ThirstLevel: This is how thirsty Bob can get, before he feels the urge to hit the bar and have a drink.
• TirednessThreshold: Mining is hard work, so when Bob hits this level of tiredness, he needs to go home and take a nap.

Next, we've got some member variables to track Bob's state.

• _currentState: The FSM state that Bob is currently in.
• _goldCarried: The number of gold nuggets Bob currently has in his pockets.
• _thirst: How thirsty Bob is at the moment.
• _fatigue: How tired Bob is at the moment.
• Location: Bob's current location. For this example, we're representing Bob's location as one of a handful of enumerated places that make up our little world:

  public enum Location {
      Shack,
      Goldmine,
      Bank,
      Saloon
  }

• Wealth: The amount of money Bob has on deposit in the bank in town.

Last, we've got some convenience functions to check the miner's state and perform some updates, respecting the various constraints that we have defined.

We still need to override the BaseGameEntity Update() method, as well as provide a mechanism for the miner to change between states. We'll do that next:

// Miner continued...
public override void Update() {
    _thirst++;
    if (_currentState != null) {
        _currentState.Execute(this);
    }
}

public void ChangeState(IState<Miner> newState) {
    Debug.Assert(_currentState != null);
    Debug.Assert(newState != null);
    _currentState.Exit(this);

    _currentState = newState;
    _currentState.Enter(this);
}

FInally, we'll provide a constructor to initialize the miner, place him in his initial state, and set him at home in his shack:

public Miner(string name)
    : base(name) {
    Location = Location.Shack;
    GoldCarried = 0;
    Wealth = 0;
    _thirst = 0;
    _fatigue = 0;
    _currentState = GoHomeAndSleepTilRested.Instance;
}

Miner States

Now that we've defined our Miner entity, we need to define the various states that control his behavior. For this example, we'll define four, mutually-exclusive states:

• GoHomeAndSleepTilRested: This is the miner's initial state. When entering this state, the miner will leave whatever location he currently is, and walk home to his shack. While the miner is in this state, he will nap, until he is no longer tired, then he'll go back to mining.
• EnterMineAndDigForNugget: When entering this state, the miner will leave his current location, and walk to his claim. Within this state, the miner will mine gold nuggets, until he fills up his pockets and needs to go to the bank, or he gets thirsty and feels the need for some booze.
• VisitBankAndDepositGold:On entering this state, the miner leaves his present location and heads to the bank. In this state, the miner puts whatever gold he's got in the bank, and then either goes home to rest, if his bank account is flush, or heads back to the mine to get more gold.
• QuenchThirst:When the miner enters this state, he walks to the bar from wherever he is. At the bar, he buys whiskey until he isn't thirsty anymore, then he staggers back to the mine.

You may notice that these states are implemented as singletons, following the pattern illustrated by Jon Skeet. This means that the states can only define behavior - any state that needs to be maintained needs to be contained by the entity, rather than within the state itself. This is fairly efficient, as we then only need to instantiate a single instance of the state object, but may not be ideal for all usages.

GoHomeAndSleepTilRested

public class GoHomeAndSleepTilRested : IState<Miner>{
    private static readonly Lazy<GoHomeAndSleepTilRested> Lazy = new Lazy<GoHomeAndSleepTilRested>(()=>new GoHomeAndSleepTilRested());
    private GoHomeAndSleepTilRested() { }
    public static GoHomeAndSleepTilRested Instance {get {return Lazy.Value;}}
        


    public void Enter(Miner entity) {
        if (entity.Location != Location.Shack) {
            entity.LogAction("Walkin' home");
            entity.Location = Location.Shack;
        }
    }

    public void Execute(Miner entity) {
        if (!entity.Fatigued) {
            entity.LogAction("What a God-darn fantastic nap! Time to find more gold");
            entity.ChangeState(EnterMineAndDigForNugget.Instance);
        } else {
            entity.DecreaseFatigue();
            entity.LogAction("ZZZZZ...");
        }
    }

    public void Exit(Miner entity) {
        entity.LogAction("Leaving the house");
    }
}

EnterMineAndDigForNugget

public class EnterMineAndDigForNugget : IState<Miner> {
    private static readonly Lazy<EnterMineAndDigForNugget> Lazy = new Lazy<EnterMineAndDigForNugget>(()=>new EnterMineAndDigForNugget()); 
    private EnterMineAndDigForNugget() { }

    public static EnterMineAndDigForNugget Instance {get {return Lazy.Value;}}


    public void Enter(Miner entity) {
        if (entity.Location != Location.Goldmine) {
            entity.LogAction("Walkin' to the goldmine");
            
            entity.Location = Location.Goldmine;
        }
    }

    public void Execute(Miner entity) {
        entity.GoldCarried++;
        entity.IncreaseFatigue();

        entity.LogAction("Pickin' up a nugget");
        if (entity.PocketsFull) {
            entity.ChangeState(VisitBankAndDepositGold.Instance);
        }
        if (entity.Thirsty) {
            entity.ChangeState(QuenchThirst.Instance);
        }
    }

    public void Exit(Miner entity) {
        entity.LogAction("Ah'm leavin' the goldmine with mah pockets full o' sweet gold");
    }
}

VisitBankAndDepositGold

public class VisitBankAndDepositGold : IState<Miner> {
    private static readonly Lazy<VisitBankAndDepositGold> Lazy = new Lazy<VisitBankAndDepositGold>(()=>new VisitBankAndDepositGold());
    private VisitBankAndDepositGold() { }
    public static VisitBankAndDepositGold Instance { get { return Lazy.Value; }}



    public void Enter(Miner entity) {
        if (entity.Location != Location.Bank) {
            entity.LogAction("Goin' to the bank. Yes siree");

            entity.Location = Location.Bank;
        }
    }

    public void Execute(Miner entity) {
        entity.AddToWealth(entity.GoldCarried);
        entity.GoldCarried = 0;
        entity.LogAction(string.Format("Depositing gold. Total saving now: {0}", entity.Wealth));
            

        if (entity.Wealth >= Miner.ComfortLevel) {
            entity.LogAction("Woohoo! Rich enough for now. Back home to my li'lle lady");

            entity.ChangeState(GoHomeAndSleepTilRested.Instance);
        }
        else {
            entity.ChangeState(EnterMineAndDigForNugget.Instance);
        }
    }

    public void Exit(Miner entity) {
        entity.LogAction("Leavin' the bank");
    }
}

QuenchThirst

public class QuenchThirst : IState<Miner> {
    private static readonly Lazy<QuenchThirst> Lazy = new Lazy<QuenchThirst>(()=>new QuenchThirst());
    private QuenchThirst() { }
    public static QuenchThirst Instance {get {return Lazy.Value;}}

    public void Enter(Miner entity) {
        if (entity.Location != Location.Saloon) {
            entity.Location = Location.Saloon;
            entity.LogAction("Boy, ah sure is thusty! Walking to the saloon");
        }
    }

    public void Execute(Miner entity) {
        if (entity.Thirsty) {
            entity.BuyAndDrinkAWhiskey();
            entity.LogAction("That's mighty fine sippin liquer");
            entity.ChangeState(EnterMineAndDigForNugget.Instance);
        }
        else {
            entity.LogAction("ERROR!\tERROR!\tERROR!");
        }
    }

    public void Exit(Miner entity) {
        entity.LogAction("Leaving the saloon, feelin' good");
    }
}

Driver Program

To wrap things up, the last step is to write a simple Main() function to create a Miner and run him through the simulation:

class Program {
    static void Main(string[] args) {
        int numCycles;
        if (args.Length == 0 || !int.TryParse(args.First(), out numCycles)) {
            numCycles = 20;
        }
        var miner = new Miner("Miner Bob") {Color = ConsoleColor.Red};
        for (var i = 0; i < numCycles; i++) {
            miner.Update();
            Thread.Sleep(800);
        }
        ConsoleUtilities.PressAnyKeyToContinue();
    }
}

Next Time...

In the next installment, we'll look at refining the FSM developed here, in order to make it more reusable. We'll also look at adding a second entity to our simulation, and implement some simple messaging between entities.