WestWorld

• 下载 WestWorld-noexe.zip - 306.1 KB
• 下载 WestWorld.zip - 306.1 KB

引言

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

作为一个关于如何创建利用有限状态机的代理人的实际示例 [^]，我们将要看一个游戏环境，在这个环境中代理人居住在一个旧西部风格的金矿小镇，名为 West World。最初只有一个居民——一个名叫 Miner Bob 的矿工。我在本文中包含了 WestWorld1、WestWorld2 和 WestWorld3。我将尝试解释适用于本文所有项目的通用代码框架。

• WestWorld1 - FSM 基础
• WestWorld2 - 包含两个代理人（矿工和妻子）的 FSM
• WestWorld3 - 包含代理人之间消息传递的 FSM

WestWorld 实现为一个简单的 .NET 控制台应用程序。任何状态更改或状态操作的输出都将作为文本发送到控制台窗口。

背景

有限状态机，或通常称为 FSM，多年来一直是 AI 程序员赋予游戏代理人智能幻觉的首选工具。它们代码编写快速简单。

• 它们易于调试。
• 它们的计算开销很小。
• 它们很直观。人类天生就会将事物视为处于一种状态或另一种状态。
• 它们很灵活。游戏代理人的有限状态机可以由程序员轻松调整和修改，以提供游戏设计者所需行为。

有限状态机是一种设备，或一种设备的模型，它有有限数量的状态。它们可以在任何给定时间处于特定状态，并通过输入在不同状态之间进行转换。它们还可以导致输出或动作的发生。FSM 在任何时刻只能处于一种状态。其理念是将对象的行为分解为可管理的“块”（即状态）。例如，您墙上的电灯开关就是一个非常简单的有限状态机。它有两个状态：开和关。

概述

West World 有四个地点：一个金矿，一个 Bob 可以存放他找到的任何金块的银行，一个他可以解渴的酒馆，以及一个他可以在那里安睡一天的家。
他具体去哪里，以及在那里做什么，取决于 Bob 当前的状态。

他会根据口渴、疲劳以及他在金矿里挖了多少金子等变量来改变状态。
在程序的输出中，每次您看到 Miner Bob 改变地点
时，他都在改变状态。所有其他事件都是在状态内发生的动作。

代码

West World 1

实体类

West World 的所有居民都派生自这个基类 Entity。这是一个简单的类，有一个私有成员用于存储一个 UniqueID 数字。它还指定了一个 MustOverride 成员函数 Update()，所有子类都必须实现它。Update 是一个在每个更新步骤中调用的函数，子类将使用它来更新它们的状态机以及必须随每个时间步更新的任何其他数据。
这是 Entity 类声明

''

''' <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

Miner 类

Miner 类派生自 Entity 类，并包含各种 Miner 属性的类成员，例如健康、疲劳、位置等。Miner 除了包含一个用于更改其状态的方法外，还有一个 State 类的实例。Miner.Update() 方法很简单；它只需增加 _ Thirst 值，然后调用 Execute 方法。它看起来是这样的

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

状态机类

设计

通过将所有与状态相关的数据和方法封装到状态机类中，可以使设计更加清晰。这样，代理人就可以拥有一个状态机的实例，并将当前状态、全局状态和先前状态的管理委托给它。

考虑到这一点，请看下面的 StateMachine 类模板。现在，代理人只需拥有一个 StateMachine 实例并实现一个方法来更新状态机即可获得完整的 FSM 功能。

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 消息传递功能

设计

设计良好的游戏通常是事件驱动的。当事件发生时——武器被射击、杠杆被拉动、警报被触发等——事件会被广播给游戏中的相关对象，以便它们可以做出适当的响应。这些事件通常以数据包的形式发送，数据包包含关于事件的信息，例如是谁发送的、哪些对象应该响应它、实际事件是什么、时间戳等等。

在 West World 的情况下，数据包通过 Telegram 类发送。智能游戏代理人使用 Telegrams 进行相互通信。通过拥有发送、处理和响应事件的能力，设计 Agent 行为变得很容易。

MessageDispatcher 类

Telegram 的创建、分发和管理由一个名为 MessageDispatcher 的类处理。每当代理人需要发送消息时，它都会调用 MessageDispatcher.DispatchMessage() 并提供所有必要的信息，例如消息类型、消息发送时间、接收者 ID 等。MessageDispatcher 使用此信息创建一个 Telegram，然后立即将其分发或存储在队列中，准备在正确的时间分发。

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 类

在 MessageDispatcher 能够分发消息之前，它必须获取发送者指定的实体引用。因此，必须存在某种已实例化实体的查找机制——一种电话簿，代理人的指针通过它们的 UniqueID 进行交叉引用。用于此演示的查找表是一个名为 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

摘要

本文向您展示了为自己的游戏创建灵活且可扩展的有限状态机所需的技能。正如您所见，消息传递的添加可以极大地增强智能的幻觉。程序的输出开始看起来像是两个真实人物的行为和互动。这只是一个非常简单的例子。行为的复杂性仅受您的想象力限制。

此外，您不必将游戏代理人限制为一个有限状态机。使用两个 FSM 并行工作可能是一个好主意：一个用于控制角色的移动，另一个用于控制武器选择、瞄准和射击，例如。状态可以包含一个状态机。这被称为层次状态机 [^]。例如，您的游戏代理人可能具有探索、战斗和巡逻状态。反过来，战斗状态可能拥有一个管理战斗所需状态的状态机，例如闪避、追逐敌人和射击。

致谢

此处显示的 VB.NET 代码特别感谢 Mat Buckland，他的原始 C++ 代码来自他的书：《Programming Game AI by Example》[^]。您可以在此处找到更多信息：http://www.ai-junkie.com/books/toc_pgaibe.html