Introduction

A demonstration of Finite State Machines (FSM) where agents inhabit an Old West style gold 
mining town called West World.

As a practical example of how to create agents that utilize finite state machines [^], we are going to look at a game environment where agents inhabit an Old West-style gold mining town named West World. Initially there will only be one inhabitant — a gold miner named Miner Bob. I have included WestWorld1, WestWorld2, and WestWorld3 in this article. I will attempt the explain the general code framework which applies to all of the projects in this article.

WestWorld1 - Basics of FSM
WestWorld2 - FSM with two agents (Miner & Wife)
WestWorld3 - Includes FSM with Messaging between Agents

WestWorld is implemented as a simple .NET Console based application. Any state changes or output from state actions will be sent as text to the console window.

Background

Finite state machines, or FSMs as they are usually referred to, have for many years been the AI coder’s instrument of choice to imbue a game agent with the illusion of intelligence. They are quick and simple to code.

They are easy to debug.
They have little computational overhead.
They are intuitive. It’s human nature to think about things as being in one state or another.
They are flexible. A game agent’s finite state machine can easily be adjusted and tweaked by the programmer to provide the behavior required by the game designer.

A finite state machine is a device, or a model of a device, which has a finite number of states. They can be in a particular state at any given time and can operate on input to either transitions from one state to another. They can also cause an output or action to take place. A FSM can only be in one state at any moment in time. The idea behind it is to decompose an object’s behavior into manageable “chunks” (i.e. states). The light switch on your wall, for example, is a very simple finite state machine. It has two states: On and Off.

Overview

There are four locations in West World: a gold mine, a bank where Bob can deposit any nuggets he finds, a saloon in which he can quench his thirst, and home-sweet-home where he can sleep the fatigue of the day
away. Exactly where he goes, and what he does when he gets there, is determined by Bob’s current state.

He will change states depending on variables like thirst, fatigue, and how much gold he has found hacking
away down in the gold mine. In the output from the program, each time you see Miner Bob change location
he is changing state. All the other events are actions that take place within a state.

Code

West World 1

Entity Class

All inhabitants of West World are derived from this base class Entity. This is a simple class with a private member for storing a UniqueID number. It also specifies a MustOverride member function, Update(), that must be implemented by all subclasses. Update is a function that gets called every update step and will be used by subclasses to update their state machine along with any other data that must be updated with each time step.
Here is the Entity class declaration:

''

''' <summary>
''' Base class for a game object
''' </summary>
Public MustInherit Class Entity

    'every entity must have a unique identifying number
    Private _UniqueID As Integer

    'this is the next valid ID. Each time a BaseGameEntity is instantiated
    'this value is updated
    Private Shared _NextID As Integer = 0

    Public Shared ReadOnly Property NextID As Integer
        Get
            Return _NextID
        End Get
    End Property


    ''' <summary>
    '''  This must be called within each constructor to make sure the ID is set
    '''  correctly. It verifies that the value passed to the method is greater
    '''   or equal to the next valid ID, before setting the ID and incrementing
    '''  the next valid ID
    ''' </summary>
    ''' <value>
    Public Property UniqueID As Integer
        Get
            Return _UniqueID
        End Get
        Set(value As Integer)
            'make sure the val is equal to or greater than the next available ID
            _UniqueID = value

            _NextID = _UniqueID + 1
        End Set
    End Property

    Protected Sub New(ByVal id As Integer)
        _UniqueID = id
    End Sub

    ''' <summary>
    ''' All entities must implement an update function
    ''' </summary>
    Public MustOverride Sub Update()

End Class

The Miner Class

The Miner class is derived from the Entity class and contains class members for the various attributes a Miner possesses, such as health, its fatigue, position, and so forth. A Miner contains an instance of a State class in addition to a method for changing its State. The Miner.Update() method is straightforward; it simply increments the _ Thirst value before calling the Execute method. It looks like this:

Public Class Miner
    Inherits Entity

    Private _CurrentState As State

    ''' <summary>
    ''' The higher the value, the thirstier the miner
    ''' 
    Private _Thirst As Integer

    ''' <summary>
    ''' The higher the value, the more tired the miner
    ''' </summary>
    Private _Fatigue As Integer

    Public Sub New(ByVal inUniqueID As Integer)
        MyBase.New(inUniqueID)

        _Location = LocationType.shack
        _GoldCarried = 0
        _Wealth = 0
        _Thirst = 0
        _Fatigue = 0
        _CurrentState = GoHomeAndSleepTilRested.Instance()
    End Sub

    ''' <summary>
    ''' Base class override
    ''' </summary>
    Public Overrides Sub Update()
        _Thirst += 1

        If _CurrentState IsNot Nothing Then
            _CurrentState.Execute(Me)
        End If
    End Sub

...
End Class

West World 2

State Machine Class

Design

The design can be made a lot cleaner by encapsulating all the state related data and methods into a State Machine class. This way an agent can own an instance of a state machine and delegate the management of current states, global states, and previous states to it.

With this in mind take a look at the following StateMachine class template. Now all an agent has to do is to own an instance of a StateMachine and implement a method to update the state machine to get full FSM functionality.

Public Class StateMachine(Of T)

    ''' <summary>
    ''' Pointer to the agent that owns this instance
    ''' </summary>
    Public Property Owner As T

    Public Property Current As State(Of T)

    ''' <summary>
    '''  Record of the last state the agent was in
    ''' </summary>
    Public Property Previous As State(Of T)

    ''' <summary>
    ''' This is called every time the FSM is updated
    ''' </summary>
    Public Property [Global] As State(Of T)

    Public Sub New(ByVal owner As T)
        _Owner = owner
        _Current = Nothing
        _Previous = Nothing
        _Global = Nothing
    End Sub

    ''' <summary>
    ''' call this to update the FSM
    ''' </summary>
    Public Sub Update()
        'if a global state exists, call its execute method, else do nothing
        If _Global IsNot Nothing Then
            _Global.Execute(_Owner)
        End If

        'same for the current state
        If _Current IsNot Nothing Then
            _Current.Execute(_Owner)
        End If
    End Sub

    ''' <summary>
    ''' Change to a new state
    ''' </summary>
    ''' <param name="pNewState"></param>
    Public Sub ChangeState(ByVal pNewState As State(Of T))

        'keep a record of the previous state
        _Previous = _Current

        'call the exit method of the existing state
        _Current.Exit(_Owner)

        'change state to the new state
        _Current = pNewState

        'call the entry method of the new state
        _Current.Enter(_Owner)
    End Sub
    ...
    End Class

West World 3

FSM Messaging Capabilities

Design

Well-designed games tend to be event driven. When an event occurs — a weapon is fired, a lever is pulled, an alarm is tripped, etc. — the event is broadcast to the relevant objects in the game so that they may respond appropriately. These events are typically sent in the form of a packet of data that contains information about the event such as what sent it, what objects should respond to it, what the actual event is, a time stamp, and so forth.

In the case of West World packets of data are sent via the Telegram class. Intelligent game agents use Telegrams to communicate with each other. Endowed with the power to send, handle, and respond to events, it’s easy to design Agent behaviors.

MessageDispatcher Class

The creation, dispatch, and management of telegrams is handled by a class named MessageDispatcher. Whenever an agent needs to send a message, it calls MessageDispatcher.DispatchMessage() with all the necessary information, such as the message type, the time the message is to be dispatched, the ID of the recipient, and so on. The MessageDispatcher uses this information to create a Telegram, which it either dispatches immediately or stores in a queue ready to be dispatched at the correct time.

Public Class MessageDispatcher

    'to make code easier to read
    Public Const SEND_MSG_IMMEDIATELY As Double = 0.0F
    Public Const NO_ADDITIONAL_INFO As Integer = 0

    'a Queue is used as the container for the delayed messages
    'because of the benefit of automatic sorting and avoidance
    'of duplicates. Messages are sorted by their dispatch time.
    Private PriorityQ As New HashSet(Of Telegram)()

    Private Shared _Instance As New MessageDispatcher

    Private Sub New()
    End Sub

    Public Shared ReadOnly Property Instance As MessageDispatcher
        Get
            Return _Instance
        End Get
    End Property
    
    ...
    End Class

EntityManager Class

Before MessageDispatcher can dispatch a message, it must get a reference to the entity specified by the sender. Therefore, there must be some sort of lookup for instantiated entities to refer to — a sort of telephone book where pointers to agents are crossreferenced by their UniqueID. The lookup table used for this demo is a singleton class called EntityManager.

Public Class EntityManager

  
    ''' <summary>
    ''' This method stores a pointer to the entity in the std::vector
    '''  m_Entities at the index position indicated by the entity's ID
    '''  (makes for faster access)
    ''' </summary>
    Public Sub RegisterEntity(ByVal e As Entity)
        _EntityMap.Add(e.UniqueID, e)
    End Sub

    ''' <summary>
    ''' Returns a pointer to the entity with the ID given as a parameter
    ''' </summary>
    ''' <param name="id"></param>
    Public Function GetEntityFromID(ByVal id As Integer) As Entity
        'find the entity
        Return _EntityMap(id)
    End Function

...

End Class

Summary

This article has shown you the skills required to create a flexible and extensible finite state machine for your own games. As you have seen, the addition of messaging can enhanced the illusion of intelligence a great deal. The output from the program is starting to look like the actions and interactions of two real people. This is only a very simple example. The complexity of behaviors is only limited by your imagination.

Additionally, you don’t have to restrict your game agents to just one finite state machine. It may be a good idea to use two FSMs working in parallel: one to control a character’s movement and one to control the weapon selection, aiming, and firing, for example. It’s possible to have a state contain a state machine. This is known as a Hierarchical State Machine [^]. For instance, your game agent may have the states Explore, Combat, and Patrol. In turn, the Combat state may own a state machine that manages the states required for combat such as Dodge, ChaseEnemy, and Shoot.

Credits

The VB.NET code displayed here owes special credit to Mat Buckland for which the original C++ code comes from in his book: Programming Game AI by Example [^] . You can find out more information here: http://www.ai-junkie.com/books/toc_pgaibe.html