Sunday, August 02, 2015 Eric Richards

Finite State Machines, Part 1

One of my favorite books on AI programming for games is Matt Buckland's Programming Game AI By Example. Many AI programming books lean more towards presenting topics and theories, leaving the dirty work of implementing the techniques and algorithms up to the reader. This book takes a very different tack, with each chapter featuring one or more fully implemented examples illustrating the techniques covered. Even better, it comes in a format similar to a trade-paperback, rather than a coffee table book-sized tome, so it's relatively handy to carry around and read a bit at a time, as programming books go. It is also decidedly focused on the kinds of real-world, relatively simple techniques that one would actually use in the majority of games. And, mixed in the right combinations, these simple techniques can be very powerful, as the second half of the book displays, building an increasingly sophisticated top-down, 2D shooter game.

What I particularly like about this book though, is that while it is presented as a book for programming game AI, it may be the best practical explanation of a number of fundamental AI techniques and patterns that I have seen. The lessons that I learned reading through this book have been just as applicable in my day-job as an enterprise developer as in my hobby work programming games, much more so than what I learned toiling through a semester-long AI course based on Artificial Intelligence: A Modern Approach...

The first real chapter of Mr. Buckland's book (leaving aside the obligatory math primer chapter), is devoted to finite state machines. Finite State Machines are one of the simpler ways of organizing decision making, and are probably one of the most intuitive. I'll let Mr. Buckland's definition stand by itself:

A finite state machine is a device, or a model of a device, which has a finite number of states it can be in at any given time and can operate on input to either make transitions from one state to another or to cause an output or action to take place. A finite state machine can only be in one state at any moment in time.

I've been working on porting the first example from Mr. Buckland's FSM chapter from C++ to C#, featuring a mildly alcoholic, spaghetti Western gold miner named Bob. I'm going to focus mostly on the FSM-specific code here, but you can get the full code from https://github.com/ericrrichards/ai/tree/master/trunk/WestWorld1.

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.


Bookshelf

I have way too many programming and programming-related books. Here are some of my favorites.