WestWorld
4.64/5 (8 votes)
A demonstration of Finite State Machines (FSM) where agents inhabit an Old West style gold mining town called West World.
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