Press "Enter" to skip to content

Artificial Intelligence for games 5.3 STATE MACHINES:状态机



Chapter 5 Decision Making


Chapter 5 Decision Making




Often, characters in a game will act in one of a limited set of ways. They will carry on doing the same thing until some event or influence makes them change. A covenant warrior in Halo [Bungie Software, 2001], for example, will stand at its post until it notices the player, then it will switch into attack mode, taking cover and firing.


通常来说,游戏中的角色所进行的行为将会从有限的行为集合中选取。它们将会保持这个状态,直到一些事件或者影响使得它们改变。以 光环:战斗进化 为例,敌人将会一直驻守直到它们注意到玩家,此时将会转换到攻击状态,寻求掩体以及开火。


We can support this kind of behavior using decision trees, and we’ve gone some way to doing that using random decisions. In most cases, however, it is easier to use a technique designed for this purpose: state machines.




State machines are the technique most often used for this kind of decision making and, along with scripting (see Section 5.9), make up the vast majority of decision making systems used in current games.


状态机是一种经常用于这类决策的技术,它与脚本一起使用(参见第5.9节),构成当前游戏中使用的绝大多数(vast majority)决策系统。


State machines take account of both the world around them (like decision trees) and their internal makeup (their state).




A Basic State Machine :一个基本状态机


In a state machine each character occupies one state. Normally, actions or behaviors are associated with each state. So as long as the character remains in that state, it will continue carrying out the same action.




States are connected together by transitions. Each transition leads from one state to another, the target state, and each has a set of associated conditions. If the game determines that the conditions of a transition are met, then the character changes state to the transition’s target state. When a transition’s conditions are met, it is said to trigger, and when the transition is followed to a new state, it has fired.




Figure 5.13 shows a simple state machine with three states: On Guard, Fight, and Run Away. Notice that each state has its own set of transitions.


图5.13显示了一个具有三种状态的简单状态机:On Guard,Fight和Run Away。请注意,每个状态都有自己的一组转换。


The state machine diagrams in this chapter are based on the UML state chart di- agram format, a standard notation used throughout software engineering. States are shown as curved corner boxes. Transitions are arrowed lines, labelled by the condition that triggers them. Conditions are contained in square brackets.




The solid circle in Figure 5.13 has only one transition without a trigger condition. The transition points to the initial state that will be entered when the state machine is first run.





You won’t need an in-depth understanding of UML to understand this chapter. If you want to find out more about UML, I’d recommend Pilone [2005].


您不需要深入了解UML来理解本章。如果你想了解更多关于UML的信息,我推荐 Pilone [2005]


In a decision tree the same set of decisions is always used, and any action can be reached through the tree. In a state machine only transitions from the current state are considered, so not every action can be reached.




Finite State Machines :有限状态机


In game AI any state machine with this kind of structure is usually called a finite state machine (FSM). This and the following sections will cover a range of increasingly powerful state machine implementations, all of which are often referred to as FSMs.




This causes confusion with non-games programmers, for whom the term FSM is more commonly used for a particular type of simple state machine. An FSM in computer science normally refers to an algorithm used for parsing text. Compilers use an FSM to tokenize the input code into symbols that can be interpreted by the compiler.




The Game FSM :游戏中的有限状态机


The basic state machine structure is very general and admits any number of imple- mentations. I have seen tens of different ways to implement a game FSM, and it is rare to find any two developers using exactly the same technique. That makes it difficult to put forward a single algorithm as being the “state machine” algorithm.




Later in this section, I’ll look at a range of different implementation styles for the FSM, but the main algorithm I work through is just one. I chose it for its flexibility and the cleanness of its implementation.




5.3.1 THE PROBLEM :问题


We would like a general system that supports arbitrary state machines with any kind of transition condition. The state machine will conform to the structure given above and will occupy only one state at a time.






We will use a generic state interface which can be implemented to include any spe- cific code. The state machine keeps track of the set of possible states and records the current state it is in. Alongside each state, a series of transitions are maintained. Each transition is again a generic interface that can be implemented with the appropriate conditions. It simply reports to the state machine whether it is triggered or not.


我们将使用通用状态接口,可以实现包含任何特定代码。 状态机跟踪可能状态的集合并记录它所处的当前状态。在每个状态下,保持一系列转换。 每次转换都是一个通用接口,可以使用适当的条件实现。 它只是向状态机报告它是否被触发。


At each iteration (normally each frame), the state machine’s update function is called. This checks to see if any transition from the current state is triggered. The first transition that is triggered is scheduled to fire. The method then compiles a list of actions to perform from the currently active state. If a transition has been triggered, then the transition is fired.


在每次迭代(通常是每个帧),调用状态机的更新函数。 这将检查是否触发了当前状态的任何转换。 触发的第一个转换将会被执行。 然后,该方法维护一个要从当前活动状态执行的动作列表(actions)。 如果已触发某个转换,则会执行这个转换。


This separation of the triggering and firing of transitions allows the transitions to also have their own actions. Often, transitioning from one state to another also involves carrying out some action. In this case a fired transition can add the action it needs to those returned by the state.


这种转换的触发和触发的分离允许转换也具有它们自己的动作。 通常,从一个状态转换到另一个状态也涉及执行某些行动。 //在这种情况下,触发转换可以将所需的操作添加到状态返回的操作。


5.3.3 PSEUDO-CODE :伪代码实现


The state machine holds a list of states, with an indication of which one is the current state. It has an update function for triggering and firing transitions and a function that returns a set of actions to carry out.


状态机保存状态列表,指示哪一个是当前状态。 //它具有用于执行和触发转换的更新功能以及返回要执行的一组操作的功能。


class machine
    // 维护一个状态机的状态列表
    list<State> states;
    // 初始状态
    State initialState;
    // 当前状态
    currentState = initialState;
    // 检查并执行转换,同时返回一个动作列表
        // 假定没有转换被触发
        triggeredTransition = None;
        // 遍历所有状态并保存第一个被触发的状态
        for transition in currentState.getTransitions()
            if transition.isTriggered():
            triggeredTransition = transition;
        // 检查是否有状态被触发?
        if triggeredTransition
            targetState = triggeredTransition.getTargetState();
            // 在行为列表之中增加旧状态的退出操作、状态转移的操作以及新状态的入口操作
            actions = currentState.getExitAction()
            actions += triggeredTransition.getAction()
            actions += targetState.getEntryAction()
            // 完成状态转移并返回行为列表
            currentState = targetState
            return actions
        // 否则直接返回当前状态的行为列表
        else return currentState.getAction()




The state machine relies on having states and transitions with a particular interface.


The state interface has the following form:






class State
    def getAction();
    def getEntryAction();
    def getExitAction();
    def getTransitions();


Each of the getAction methods should return a list of actions to carry out. As we will see below, the getEntryAction is only called when the state is entered from a transition, and the getExitAction is only called when the state is exited. The rest of the time that the state is active, getAction is called. The getTransitions method should return a list of transitions that are outgoing from this state.


The transition interface has the following form:


每个getAction方法都应返回要执行的操作列表。 正如我们将在下面看到的,只有在从转换进入状态时才调用getEntryAction,并且仅在退出状态时调用getExitAction。 其余时间状态为活动状态,调用getAction。 getTransitions方法应返回从此状态传出的转换列表。




class Transition
  def isTriggered();
  def getTargetState();
  def getAction();


The isTriggered method returns true if the transition can fire; the getTarget-State method reports which state to transition to; and the getAction method returns a list of actions to carry out when the transition fires.


如果转换可以触发,则isTriggered方法返回true; getTarget-State方法报告要转换到的状态; 并且getAction方法返回转换触发时要执行的操作列表。


Transition Implementation :实现转换


Only one implementation of the state class should be required: it can simply hold the three lists of actions and the list of transitions as data members, returning them in the corresponding get methods.




In the same way, we can store the target state and a list of actions in the transition class and have its methods return the stored values. The isTriggered method is more difficult to generalize. Each transition will have its own set of conditions, and much of the power in this method is allowing the transition to implement any kind of tests it likes.


以同样的方式,我们可以在转换类中存储目标状态和操作列表,并使其方法返回存储的值。 isTriggered方法更难以概括。 每个转换都有自己的一组条件,这种方法的大部分功能是允许转换实现它喜欢的任何类型的条件测试。


Because state machines are often defined in a data file and read into the game at run time, it is a common requirement to have a set of generic transitions. The state machine can then be set up from the data file by using the appropriate transitions for each state.


由于状态机通常在数据文件中定义并在运行时读入游戏,因此通常需要具有一组通用转换。 然后,可以通过使用每个状态的适当转换从数据文件中设置状态机。


In the previous section on decision trees, we saw generic testing decisions that operated on basic data types. The same principle can be used with state machine transitions: we have generic transitions that trigger when data they are looking at is in a given range.


在上一节关于决策树的部分中,我们看到了对基本数据类型进行操作的通用测试决策。 相同的原理可以与状态机转换一起使用:我们具有通用转换,当它们正在查看的数据处于给定范围内时触发。


Unlike decision trees, state machines don’t provide a simple way of combining these tests together to make more complex queries. If we need to transition based on the condition that the enemy is far away AND health is low, then we need some way of combining triggers together.


与决策树不同,状态机不提供将这些测试组合在一起以进行更复杂查询的简单方法。// 如果我们需要根据敌人在远处且健康状况低的条件进行过渡,那幺我们需要一些将触发器组合在一起的方法。


In keeping with our polymorphic design for the state machine, we can accom- plish this with the addition of another interface: the condition interface. We can use a general transition class of the following form:


为了与状态机的多态设计保持一致,我们可以通过添加另一个接口来实现这一点:条件接口。 我们可以使用以下形式的一般转换类:


class Transition
{// 条件接口类
    def getAction(): return actions
    def getTargetState(): return targetState
    def isTriggered(): return condition.test()


The isTriggered function now delegates the testing to its condition member.


Conditions have the following simple format:






class Condition
   def test();


We can then make a set of sub-classes of condition for particular tests, just like we did for decision trees:




class FloatCondition (Condition)
{// 数值条件
    testValue; // 我们想关注的游戏数据
    def test()
        return minValue <= testValue <= maxValue


We can combine conditions together using Boolean sub-classes, such as AND, NOT, and OR:




class AndCondition (Condition)
{// 布尔条件
    def test()
        return conditionA.test() and conditionB.test();
class NotCondition (Condition)
    def test()
        return not condition.test();
class OrCondition (Condition)
    def test()
        return conditionA.test() or conditionB.test() 


and so on, for any level of sophistication we need.




Weaknesses :缺点


This approach to transitions gives a lot of flexibility, but at the price of lots of method calls. In C++ these method calls have to be polymorphic, which can slow down the call and confuse the processor. All this adds time, which may make it unsuitable for use in every frame on lots of characters.


这种转换方法提供了很大的灵活性,但代价是大量的方法调用。 在C ++中,这些方法调用必须是多态的,这会降低调用速度并使处理器混淆。 所有这些都增加了时间,这可能使其不适合在许多角色的每个帧中使用。


Several developers I have come across use a homegrown scripting language to ex- press conditions for transitions. This still allows designers to create the state machine rules, but can be slightly more efficient. In practice, however, the speed up over this approach is quite small, unless the scripting language includes some kind of compila- tion into machine code (i.e., Just In Time Compiling). For all but the simplest code, interpreting a script is at least as time-consuming as calling polymorphic functions.


我遇到的几个开发人员使用自己开发的脚本语言来表达转换条件。 这仍然允许设计人员创建状态机规则,但可以稍微提高效率。 然而,在实践中,除非脚本语言包括对机器代码的某种编译(即,及时编译),否则这种方法的速度非常快。 对于除最简单代码之外的所有代码,解释脚本至少与调用多态函数一样耗时。




The state machine algorithm only requires memory to hold a triggered transition and the current state. It is O(1) in memory, and O(m) in time, where m is the number of transitions per state.


状态机算法仅需要存储器来保持触发转换和当前状态。 它在存储器中是O(1),在时间上是O(m),其中m是每个状态的转换数。


The algorithm calls other functions in both the state and the transition classes, and in most cases the execution time of these functions accounts for most of the time spent in the algorithm.






As I mentioned earlier, there are any number of ways to implement a state machine. The state machine described in this section is as flexible as possible. I’ve tried to aim for an implementation that allows you to experiment with any kind of state machine and add interesting features. In many cases it may be too flexible. If you’re only planning to use a small subset of its flexibility, then it is very likely to be unnecessarily inefficient.


正如我之前提到的,有许多方法可以实现状态机。 本节中描述的状态机尽可能灵活。 我试图实现一个允许您尝试任何类型的状态机并添加有趣功能的实现。 在许多情况下,它可能过于灵活。 如果您只计划使用其灵活性的一小部分,则很可能会产生不必要的低效率。


5.3.8 HARD-CODED FSM :FSM的硬编码问题


A few years back, almost all state machines were hard-coded. The rules for transitions and the execution of actions were part of the game code. It has become less common as level designers get more control over building the state machine logic, but it is still an important approach.


几年前,几乎所有的状态机都是硬编码的。 转换规则和动作的执行是游戏代码的一部分。 随着关卡设计师对构建状态机逻辑的更多控制,它变得不那幺常见,但它仍然是一种重要的方法。


Pseudo-Code :伪代码


In a hard-coded FSM, the state machine consists of an enumerated value, indicating which state is currently occupied, and a function that checks if a transition should be followed. Here I’ve combined the two into a class definition (although I personally tend to associate hard-coded FSMs with developers still working in C).


在硬编码的FSM中,状态机由枚举值组成,指示当前占用的状态,以及检查是否应遵循转换的函数。 在这里,我将两者合并为一个类定义(尽管我个人倾向于将硬编码的FSM与仍在C中工作的开发人员联系起来)。


class MyFSM
    // 声明所有状态名
    enum State
    // 当前状态
    def update()
        // 寻找当前状态
        if myState == PATROL
            if canSeePlayer()
                myState = DEFEND
            if tired()
                myState = SLEEP
        else if myState == DEFEND
            if not canSeePlayer()
                myState = PATROL 
        else if myState == SLEEP
            if not tired()
                myState = PATROL
        def notifyNoiseHeard(volume)
            if myState == SLEEP and volume > 10:
            myState = DEFEND


Notice that this is pseudo-code for a particular state machine rather than a type of state machine. In the update function there is a block of code for each state. In that block of code the conditions for each transition are checked in turn, and the state is updated if required. The transitions in this example all call functions (tired and canSeePlayer), which I am assuming have access to the current game state.


请注意,这是特定状态机的伪代码,而不是一种状态机。 在更新功能中,每个状态都有一个代码块。 在该代码块中,依次检查每个转换的条件,并在需要时更新状态。 这个例子中的转换都是调用函数(tired()和canSeePlayer()),我假设它们可以访问当前的游戏状态。


In addition, I’ve added a state transition in a separate function, notifyNoiseHeard. I am assuming that the game code will call this function whenever the character hears a loud noise. This illustrates the difference between a polling (asking for informa- tion explicitly) and an event-based (waiting to be told information) approach to state transitions. Chapter 10 on world interfacing contains more details on this distinction.


另外,我在一个单独的函数notifyNoiseHeard中添加了一个状态转换。 我假设只要角色听到很大的噪音,游戏代码就会调用此函数。 这说明了轮询(明确要求信息)和基于事件(等待被告知信息)的状态转换方法之间的区别。 关于世界接口的第10章包含有关这种区别的更多细节。


The update function is called in each frame, as before, and the current state is used to generate an output action. To do this, the FSM might have a method containing conditional blocks of the following form:


更新函数像以前一样在每个帧中调用,当前状态用于生成输出动作。 为此,FSM可能有一个包含以下形式的条件块的方法:


def getAction()
    if myState == PATROL: return PatrolAction
    elif myState == DEFEND: return DefendAction
    elif myState == SLEEP: return SleepAction


Often, the state machine simply carries out the actions directly, rather than returning details of the action for another piece of code to execute.




Performance :开销


This approach requires no memory and is O(n + m), where n is the number of states, and m is the number of transitions per state.


这种方法不需要存储器,并且是O(n + m),其中n是状态数,m是每个状态的转换数。


Although this appears to perform worse than the flexible implementation, it is usually faster in practice for all but huge state machines (i.e., thousands of states).




Weaknesses :缺点


Although hard-coded state machines are easy to write, they are notoriously difficult to maintain. State machines in games can often get fairly large, and this can appear as ugly and unclear code.


虽然硬编码的状态机很容易编写,但它们很难维护。 游戏中的状态机通常会变得相当大,这可能看起来像丑陋和不清楚的代码。


Most developers, however, find that the main drawback is the need for program- mers to write the AI behaviors for each character. This implies a need to recompile the game each time the behavior changes. While it may not be a problem for a hobby game writer, it can become critical in a large game project that takes many minutes or hours to rebuild.


然而,大多数开发人员发现主要缺点是程序员需要为每个角色编写AI行为。 这意味着每次行为改变时都需要重新编译游戏。 虽然它可能不是一个业余爱好游戏开发者的问题,但它可能在一个大型游戏项目中变得至关重要,需要花费很多分钟或几小时来重建。


More complex structures, such as hierarchical state machines (see below), are also difficult to coordinate using hard-coded FSMs. With a more flexible implementation, debugging output can easily be added to all state machines, making it easier to track down problems in the AI.


更复杂的结构,例如分层状态机(见下文),也很难使用硬编码的FSM进行协调。 通过更灵活的实现,可以轻松地将调试输出添加到所有状态机,从而更容易跟踪AI中的问题。




On its own, one state machine is a powerful tool, but it can be difficult to express some behaviors. One common source of difficulty is “alarm behaviors.”




Imagine a service robot that moves around a facility cleaning the floors. It has a state machine allowing it to do this. It might search around for objects that have been dropped, pick one up when it finds it, and carry it off to the trash compactor. This can be simply implemented using a normal state machine (see Figure 5.14).


想象一下一个机器人在清洁地板的设施周围移动。 它有一个状态机允许它这样做。 它可能会搜索掉落的物体,找到它时拾取一个物体,然后将它带到垃圾压缩机。 这可以使用普通状态机简单地实现(参见图5.14)。



Unfortunately, the robot can run low on power, whereupon it has to scurry off to the nearest electrical point and get recharged. Regardless of what it is doing at the time, it needs to stop, and when it is fully charged again, it needs to pick up where it left off. The recharging periods could allow the player to sneak by unnoticed, for example, or allow the player to disable all electricity to the area and thereby disable the robot.


不幸的是,机器人的能源不是无限的,因此它必须赶到最近的电气点并进行充电。 不管它当时在做什幺,它需要停止。当它再次充满电时,它需要从它停止的地方开始。 例如,充电时段可允许玩家不加注意地潜行,或允许玩家禁用该区域的所有电力,从而禁用机器人。(注:游戏场景模拟)


This is an alarm mechanism: something that interrupts normal behavior to respond to something important. Representing this in a state machine leads to a dou- bling in the number of states.


这是一种警报机制:可以中断正常行为以回应重要事件。 在状态机中表示这一点会导致状态数量的增加。


With one level of alarm this isn’t a problem, but what would happen if we wanted the robot to hide when fighting breaks out in the corridor. If its hiding instinct is more important than its refuelling instinct, then it will have to interrupt refuelling to go hide. After the battle it will need to pick up refuelling where it left off, after which it will pick up whatever it was doing before that. For just 2 levels of alarm, we would have 16 states.


通过一层警报,这不是问题,但如果我们希望机器人在走廊中发生战斗时隐藏会发生什幺。 如果它的隐藏决策比加油决策优先级更高,那幺就不得不中断加油才能隐藏起来。 在战斗结束后,它需要在停止的地方接受加油,之后它将重拾它之前做的事情。 对于仅2层警报,我们将有16个状态。(?)


Rather than combining all the logic into a single state machine, we can separate it into several. Each alarm mechanism has its own state machine, along with the original behavior. They are arranged in a hierarchy, so the next state machine down is only considered when the higher level state machine is not responding to its alarm.


我们可以将它分成几个,而不是将所有逻辑组合到一个状态机中。 每个报警机制都有自己的状态机以及原始行为。 它们按层次结构排列,因此仅当较高级别的状态机未响应其警报时才考虑下一个状态机。


Figure 5.15 shows one alarm mechanism and corresponds exactly to the diagram above.





We will nest one state machine inside another to indicate a hierarchical state ma- chine (Figure 5.16). The solid circle again represents the start state of the machine. When a composite state is first entered, the circle with H* inside it indicates which sub-state should be entered.


我们将一个状态机嵌套在另一个状态机中以指示分层状态机(图5.16)。 实心圆圈再次表示机器的启动状态。 首次输入复合状态时,其中带有H *的圆圈表示应输入哪个子状态。



If the composite state has already been entered, then the previous sub-state is returned to. The H* node is called the “history state” for this reason.


如果已经输入复合状态,则返回先前的子状态。 由于这个原因,H *节点被称为“历史状态”。


The details of why there’s an asterisk after the H, and some of the other vagaries of the UML state chart diagram, are beyond the scope of this chapter. Refer back to Pilone [2005] for more details.


H之后有一个星号的原因以及UML状态图表中的一些其他变幻莫测的细节超出了本章的范围。 有关更多详细信息,请参阅Pilone [2005]。


Rather than having separate states to keep track of the non-alarm state, we intro- duce nested states. We still keep track of the state of the cleaning state machine, even if we are in the process of refuelling. When the refuelling is over, the cleaning state machine will pick up where it left off.


我们引入嵌套状态,而不是使用单独的状态来跟踪非警报状态。 即使我们正在加油,我们仍然会跟踪清洁状态机的状态。 当加油结束时,清洁状态机将从停止的地方开始。


In effect, we are in more than one state at once: we might be in the “Refuel” state in the alarm mechanism, while at the same time be in the “Pick Up Object” state in the cleaning machine. Because there is a strict hierarchy, there is never any confusion about which state wins out: the highest state in the hierarchy is always in control.


实际上,我们同时处于多个状态:我们可能处于报警机制中的“加油”,同时处于清洗机制中的“拾取对象”状态。 因为存在严格的层次结构,所以对于执行哪个状态并不存在任何混淆:层次结构中的最高状态始终处于控制之中。


To implement this, we could simply arrange the state machines in our program so that one state machine calls another if it needs to. So if the refuelling state ma- chine is in its “Clean Up” state, it calls the cleaning state machine and asks it for the action to take. When it is in the “Refuel” state, it returns the refuelling action directly.


为了实现这一点,我们可以简单地在我们的程序中安排状态机,以便一个状态机在需要时调用另一个状态机。 因此,如果加油状态机处于“清理”状态,它会调用清洁状态机并要求其采取措施。 当它处于“加油”状态时,它直接返回加油动作。


While this would lead to slightly ugly code, it would implement our scenario. Most hierarchical state machines, however, support transitions between levels of the hierarchy, and for that we’ll need more complex algorithms.


虽然这会导致稍微丑陋的代码,但它会实现我们的场景。 但是,大多数分层状态机支持层次结构级别之间的转换,为此我们需要更复杂的算法。


For example, let’s expand our robot so that it can do something useful if there are no objects to collect. It makes sense that it will use the opportunity to go and recharge, rather than standing around waiting for its battery to go flat. The new state machine is shown in Figure 5.17.


例如,让我们扩展我们的机器人,以便在没有要收集的对象时它可以做一些有用的事情。 这是有意义的,它会利用这个机会去充电,而不是站在那里等待电池电量消失。 新的状态机如图5.17所示。



Notice that we’ve added one more transition: from the “Search” state right out into the “Refuel” state. This transition is triggered when there are no objects to collect. Because we transitioned directly out of this state, the inner state machine no longer has any state. When the robot has refuelled and the alarm system transitions back to cleaning, the robot will not have a record of where to pick up from, so it must start the state machine again from its initial node (“Search”).


请注意,我们又添加了一个转换:从“搜索”状态直接进入“加油”状态。 没有要收集的对象时会触发此转换。 因为我们直接从这个状态转换,内部状态机不再具有任何状态。 当机器人加满了油并且报警系统转换回清洁时,机器人将无法记录从哪里取货,因此它必须从其初始节点(“搜索”)再次启动状态机。


The Problem :问题


We’d like an implementation of a state machine system that supports hierarchical state machines. We’d also like transitions that pass between different layers of the machine.


我们想要一个支持分层状态机的状态机系统的实现。 我们也喜欢在机器的不同层之间传递的过渡。


The Algorithm :算法


In a hierarchical state machine each state can be a complete state machine in its own right. We therefore rely on recursive algorithms to process the whole hierarchy. As with most recursive algorithms, this can be pretty tricky to follow. The simplest im- plementation covered here is doubly tricky because it recurses up and down the hier- archy at different points. I’d encourage you to use the informal discussion and exam- ples in this section alongside the pseudo-code in the next section and play with the Hierarchical State Machine program on the CD to get a feel for how it is all working.


在分层状态机中,每个状态本身可以是完整的状态机。 因此,我们依靠递归算法来处理整个层次结构。 与大多数递归算法一样,这可能非常棘手。 这里涉及的最简单的实现是双重棘手的,因为它在不同的点上上下起伏。 我鼓励您使用本节中的非正式讨论和示例以及下一节中的伪代码,并使用CD上的Hierarchical State Machine程序来了解它是如何工作的。


The first part of the system returns the current state. The result is a list of states, from highest to lowest in the hierarchy. The state machine asks its current state to return its hierarchy. If the state is a terminal state, it returns itself; otherwise, it returns itself and adds to it the hierarchy of state from its own current state.


系统的第一部分返回当前状态。 结果是状态列表,从层次结构的最高到最低。 状态机要求其当前状态返回其层次结构。 如果状态是终端状态,则返回自身; 否则,它返回自身并从其当前状态向其添加状态层次结构。


In Figure 5.18 the current state is [State L, State A].





The second part of the hierarchical state machine is its update. In the original state machine we assumed that each state machine started off in its initial state. Because the state machine always transitioned from one state to another, there was never any need to check if there was no state. State machines in a hierarchy can be in no state; they may have a cross hierarchy transition. The first stage of the update, then, is to check if the state machine has a state. If not, it should enter its initial state.


分层状态机的第二部分是它的更新。 在原始状态机中,我们假设每个状态机在其初始状态下启动。 因为状态机总是从一个状态转换到另一个状态,所以从来没有必要检查是否没有状态。 层次结构中的状态机可以处于无状态; 他们可能有一个跨层次的过渡。 然后,更新的第一阶段是检查状态机是否具有状态。 如果没有,它应该进入其初始状态。


Next, we check if the current state has a transition it wants to execute. Transitions at higher levels in the hierarchy always take priority, and the transitions of sub-states will not be considered if the super-state has one that triggers.


接下来,我们检查当前状态是否有要执行的转换。 层次结构中较高级别的转换始终具有优先级,如果父状态已经被触发,则不会考虑子状态的转换。


A triggered transition may be one of three types: it might be a transition to an- other state at the current level of the hierarchy; it might be a transition to a state higher up in the hierarchy; or it might be a transition to a state lower in the hierarchy. Clearly, the transition needs to provide more data than just a target state. We allow it to return a relative level: how many steps up or down the hierarchy the target state is.


触发转换可以是以下三种类型之一:它可能是在层次结构的当前级别转换到另一种状态; 它可能是向层次结构中更高级别的状态过渡; 或者它可能是转换到层次结构中较低的状态。 显然,转换需要提供的数据多于目标状态。 我们允许它返回一个相对级别:目标状态在层次结构中向上或向下的步数。


We could simply search the hierarchy for the target state and not require an ex- plicit level. While this would be more flexible (we wouldn’t have to worry about the level values being wrong), it would be considerably more time-consuming. A hybrid, but fully automatic, extension could search the hierarchy once offline and store all appropriate level values.


我们可以简单地在层次结构中搜索目标状态,而不需要一个明确的级别。 虽然这会更灵活(我们不必担心水平值是错误的),但它会更加耗时。 混合但全自动的扩展可以在离线时搜索层次结构并存储所有适当的级别值。


So the triggered transition has a level of zero (state is at the same level), a level greater than zero (state is higher in the hierarchy), or a level less than zero (state is lower in the hierarchy). It acts differently depending on which category the level falls into.


因此,触发转换拥有三种情况:级别为零(状态处于同一级别),级别大于零(层次结构中的状态较高),或小于零的级别(状态在层次结构中较低)。 它的行为取决于级别所属的类别。


If the level is zero, then the transition is a normal state machine transition and can be performed at the current level, using the same algorithm used in the finite state machine.




If the level is greater than zero, then the current state needs to be exited and noth- ing else needs to be done at this level. The exit action is returned, along with an indication to whoever called the update function that the transition hasn’t been com- pleted. We will return the exit action, the transition outstanding, and the number of levels higher to pass the transition. This level value is decreased by one as it is returned. As we will see, the update function will be returning to the next highest state machine in the hierarchy.


如果级别大于零,则需要退出当前状态,而不需要在此级别完成其他操作。 返回退出操作,同时向任何调用Update()的位置指示转换尚未完成。 我们将返回退出时执行的行为、未完成的转换以及更高级别的数量以通过转换。 该级别值在返回时减少一。 正如我们将看到的,更新功能将返回到层次结构中的下一个最高状态机。


If the level is less than zero, then the current state needs to transition to the ancestor of the target state on the current level in the hierarchy. In addition, each of the children of that state also needs to do the same, down to the level of the final desti- nation state. To achieve this we use a separate function, updateDown, that recursively performs this transition from the level of the target state back up to the current level and returns any exit and entry actions along the way. The transition is then complete and doesn’t need to be passed on up. All the accumulated actions can be returned.


// 如果级别小于零,则当前状态需要转换到层次结构中当前级别上的目标状态的父状态。 此外,该状态的每个孩子也需要做同样的事情,直到最终目标状态的水平。 为了实现这一点,我们使用一个单独的函数updateDown,它递归地执行从目标状态级别到当前级别的转换,并返回任何退出和进入操作。 然后转换完成,不需要向上传递。 可以返回所有累积的动作。


So we’ve covered all possibilities if the current state has a transition that triggers. If it does not have a transition that triggers, then its action depends on whether the current state is a state machine itself. If not, and if the current state is a plain state, then we can return the actions associated with being in that state, just as before.


因此,如果当前状态具有触发的转换,我们已经涵盖了所有可能性。 如果它没有触发的转换,那幺它的动作取决于当前状态是否是状态机本身。 如果不是,并且如果当前状态是普通状态,那幺我们可以像以前一样返回与处于该状态相关联的动作。


If the current state is a state machine, then we need to give it the opportunity to trigger any transitions. We can do this by calling its update function. The update func- tion will handle any triggers and transitions automatically. As we saw above, a lower level transition that fires may have its target state at a higher level. The update func- tion will return a list of actions, but it may also return a transition that it is passing up the hierarchy and that hasn’t yet been fired.


如果当前状态是状态机,那幺我们需要给它机会来触发任何转换。 我们可以通过调用它的更新函数来实现。 更新功能将自动处理任何触发和转换。 如上所述,触发的较低级别转换可能使其目标状态处于较高级别。 更新功能将返回一个操作列表,但它也可能返回一个它正在向层次结构传递但尚未触发的转换。


If such a transition is received, its level is checked. If the level is zero, then the transition should be acted on at this level. The transition is honored, just as if it were a regular transition for the current state. If the level is still greater than zero (it should never be less than zero, because we are passing up the hierarchy at this point), then the state machine should keep passing it up. It does this, as before, by exiting the current state and returning the following pieces of information: the exit action; any actions provided by the current state’s update function; the transition that is still pending; and the transition’s level, less one.


如果收到这样的转换,则检查其级别。 如果级别为零,则应在此级别上执行转换。转换已经执行,就像它是当前状态的常规过渡一样。 如果级别仍然大于零(它应该永远不会小于零,因为我们此时正在调整层次结构),那幺状态机应该继续传递它。 它像以前一样通过退出当前状态并返回以下信息来执行此操作:退出操作; 当前状态更新功能提供的任何行动; 仍未决的状态转换; 和转换的层级//,少一个。


If no transition is returned from the current state’s update function, then we can simply return its list of actions. If we are at the top level of the hierarchy, the list alone is fine. If we are lower down, then we are also within a state, so we need to add the action for the state we’re in to the list we return.


如果没有从当前状态的更新函数返回转换,那幺我们可以简单地返回其动作列表。 如果我们处于层次结构的顶层,那幺单独列表就可以了。 如果我们处于较低的层级,那幺我们也处于一个状态,所以我们需要为我们返回的列表中的状态添加动作。


Fortunately, this algorithm is at least as difficult to explain as it is to implement. To see how and why it works, let’s work through an example.


幸运的是,这种算法至少与实现一样难以解释。 为了了解它的工作原理和原因,让我们来看一个例子。


Examples :例子


Figure 5.19 shows a hierarchical state machine that we will use as an example.





To clarify the actions returned for each example, we will say S-entry is the set of entry actions for state S, similarly S-active and S-exit for active and exit actions. In transitions we use the same format 1-actions for the actions associated with transi- tion 1.


为了阐明每个示例返回的操作,我们将说S-entry是状态S的入口操作集,类似于活动和退出操作的S-active和S-exit。 在转换中,我们对与转换1相关的操作使用相同的格式1动作。


These examples can appear confusing if you skim them through. If you’re having trouble with the algorithm, I urge you to follow through step by step with both the diagram above and the pseudo-code from the next section.


如果您浏览它们,这些示例可能会让您感到困惑。 如果您在使用算法时遇到问题,我建议您按照上图和下一部分的伪代码一步一步地进行操作。


Suppose we start just in State L, and no transition triggers. We will transition into State [L, A], because L’s initial state is A. The update function will return: L-active and A-entry, because we are staying in L and just entering A.


假设我们只是在状态L开始,没有转换触发器。 我们将转换到状态[L,A],因为L’的初始状态是A.更新函数将返回:L-active和A-entry,因为我们留在L并且只是进入A.


Now suppose transition 1 is the only one that triggers. The top-level state ma- chine will detect no valid transitions, so will call state machine L to see if it has any. L finds that its current state (A) has a triggered transition. Transition 1 is a transition at the current level, so it is handled within L and not passed anywhere. A transitions to A, and L’s update function returns: A-exit, 1-actions, B-entry. The top-level state machine accepts these actions and adds its own active action. Because we have stayed in State L throughout, the final set of actions is A-exit, 1-actions, B-entry, L-active. The current state is [L, B].


现在假设转换1是唯一触发的转换。 顶层状态机将检测到无有效转换,因此将调用状态机L以查看它是否有任何转换。 L发现其当前状态(A)具有触发转换。 1是当前级别的转换,因此它在L内处理,不会在任何地方传递。 转换到A,并且L的更新函数返回:A-exit,1–actions,B-entry。 顶层状态机接受这些操作并添加其自己的活动操作。 因为我们始终处于状态L,所以最后一组动作是A-exit,1-actions,B-entry,L-active。 当前状态是[L,B]。


From this state, transition 4 triggers. The top-level state machine sees that transi- tion 4 triggers, and because it is a top-level transition, it can be honored immediately. The transition leads to State M, and the corresponding actions are L-exit, 4-actions, M-entry. The current state is [M]. Note that L is still keeping a record of being in State B, but because the top-level state machine is in State M, this record isn’t used at the moment.


从这个状态,转换4。 顶级状态机看到转换4触发,并且因为它是顶级转换,所以它可以立即兑现。 转换导致状态M,并且相应的动作是L-exit,4-actions,M-entry。 当前状态是[M]。 请注意,L仍然保留在状态B中的记录,但由于顶级状态机处于状态M,因此此记录不会被使用。


We’ll go from State M to State N in the normal way through transition 5. The pro- cedure is exactly the same as for the previous example and the non-hierarchical state machine. Now transition 6 triggers. Because it is a level zero transition, the top-level state machine can honor it immediately. It transitions into State L and returns the ac- tions N-exit, 6-actions, L-entry. But now, L’s record of being in State B is important: we end up in State [L, B] again. In our implementation we don’t return the B-entry action, because we didn’t return the B-exit action when we left State L previously. This is a personal preference on my part and isn’t fixed in stone. If you want to exit and re-enter State B, then you can modify your algorithm to return these extra actions at the appropriate time.


我们将通过转换5以正常方式从状态M转到状态N.该过程与前一个示例和非分层状态机完全相同。 现在转换6个触发器。 因为它是一个零级转换,所以顶级状态机可以立即兑现它。 它转换到状态L并返回N-exit,6-actions,L-entry的动作。 但是现在,L在状态B的记录很重要:我们再次进入状态[L,B]。 在我们的实现中,我们不返回B-entry动作,因为我们之前离开状态L时没有返回B-exit动作。 这是我个人的偏好,并不是固定的。 如果要退出并重新输入状态B,则可以修改算法以在适当的时间返回这些额外的操作。


Now suppose from State [L, B] transition 3 triggers. The top-level state machine finds no triggers, so it will call state machine L to see if it has any. L finds that State B has a triggered transition. This transition has a level of one: its target is one level higher in the hierarchy. This means that State B is being exited, and it means that we can’t honor the transition at this level. We return B-exit, along with the uncompleted transition, and the level minus one (i.e., zero, indicating that the next level up needs to handle the transition). So control returns to the top-level update function. It sees that L returned an outstanding transition, with zero level, so it honors it, transitioning in the normal way to State N. It combines the actions that L returned (namely,B-exit) with the normal transition actions to give a final set of actions: B-exit, L-exit,3-actions, N-entry. Note that, unlike in our third example, L is no longer keeping track of the fact that it is in State B, because we transitioned out of that state. If we fire transition 6 to return to State L, then State L’s initial state, A, would be entered, just like in the first example.


现在假设从状态[L,B]过渡3触发。顶级状态机找不到触发器,因此它将调用状态机L以查看它是否有任何触发器。 L发现状态B已经触发转换。此转换的级别为1:其目标在层次结构中高一级。这意味着状态B正在退出,并且我们无法履行这一级别的过渡。我们返回B-exit,以及未完成的转换,以及级别减1(即,零,表示下一级需要处理转换)。因此控制移交回上层的Update函数。Update函数得到了一个未完成的状态转换,零级别,所以Update函数将执行这个转换:以正常方式转换到状态N。它将L返回的动作(即B-exit)与正常的过渡动作结合起来给出一组最终动作集:B-exit,L-exit,3-actions,N-entry。请注意,与我们的第三个示例不同,L不再跟踪它在状态B中执行的事,因为我们已经转换出该状态。如果我们触发转换6返回到状态L,则将输入State L’的初始状态A,就像在第一个示例中一样。


Our final example covers transitions with level less than zero. Suppose we moved from State N to State M via transition 7. Now we make transition 2 trigger. The top- level state machine looks at its current state (M) and finds transition 2 triggered. It has a level of minus one, because it is descending one level in the hierarchy. Because it has a level of minus one, the state machine calls the updateDown function to perform the recursive transition. The updateDown function starts at the state machine (L) that contains the final target state (C), asking it to perform the transition at its level. State machine L, in turn, asks the top-level state machine to perform the transition at its level. The top-level state machine changes from State M to State L, returning M-exit, L-entry as the appropriate actions. Control returns to state machine L’s updateDown function. State machine L checks if it is currently in any state (it isn’t, since we left State B in the last example). It adds its action, C-entry, to those returned by the top- level machine. Control then returns to the top-level state machine’s update function: the descending transition has been honored, it adds the transition’s actions to the result, and returns M-exit, C-entry, L-entry, 2-actions.


我们的最后一个示例涵盖了级别小于零的转换。假设我们通过转换7从状态N移动到状态M,现在我们通过触发器2执行转换。顶级状态机查看其当前状态(M)并找到触发的转换2。它的级别为-1,因为它在层次结构中下降一级。因为它的级别为-1,所以状态机调用updateDown函数来执行递归转换。 updateDown函数从包含最终目标状态(C)的状态机(L)开始,要求它在其级别执行转换。状态机L反过来要求顶级状态机在其级别执行转换。顶级状态机从状态M变为状态L,返回M-exit,L-entry作为适当的动作。控制返回状态机L的updateDown函数。状态机L检查它当前是否处于任何状态(它不是,因为我们在最后一个例子中离开了状态B)。它将其操作C-entry添加到顶级计算机返回的操作中。然后,Control返回到顶级状态机的Update函数:已经执行过降序转换,它将转换的动作添加到结果中,并返回M-exit,C-entry,L-entry,2-actions。


If state machine L had still been in State B, then when L’s updateDown function was called, it would transition out of B and into C. It would add B-exit and C-entry to the actions that it received from the top-level state machine.


如果状态机L仍处于状态B,那幺当调用L的 updateDown函数时,它将从B转换为C。它会将B-exit和C-entry添加到它从顶层状态机接收的操作集中。


Pseudo-Code :伪代码


The hierarchical state machine implementation is made up of five classes and forms one of the longest algorithms in this book. The State and Transition classes are similar to those in the regular finite state machine. The HierarchicalStateMachine class runs state transitions, and SubMachineState combines the functionality of the state machine and a state. It is used for state machines that aren’t at the top level of the hierarchy. All classes but the Transition inherit from a HSMBase class, which simpli- fies the algorithm by allowing functions to treat anything in the hierarchy in the same way.


分层状态机实现由五个类组成,并形成本书中最长的算法之一。 State和Transition类与常规有限状态机中的类相似。 HierarchicalStateMachine类运行状态转换,SubMachineState结合状态机和状态的功能。 它用于不在层次结构顶层的状态机。 除了Transition之外的所有类都继承自HSMBase类,它通过允许函数以相同的方式处理层次结构中的任何内容来简化算法。


The HSMBase has the following form:




class HSMBase
    # The structure returned by update
    // Update函数返回结果的结构体
    struct UpdateResult
      actions   // 行为
      transition// 转换路径
      level     // 层级
    def getAction(): return []
    def update()
        UpdateResult result
        result.actions = getAction()
        result.transition = None
        result.level = 0
        return result        
    // 未实现的功能?
    def getStates() # unimplemented function


The HierarchicalStateMachine class has the following implementation:




class HierarchicalStateMachine (HSMBase)
    # List of states at this level of the hierarchy
    // 本层次的状态列表
    # The initial state for when the machine has to
    # current state.
    // 机器必须处于当前状态的初始状态
    # The current state of the machine.
    // 状态机的当前状态
    currentState = initialState
    # Gets the current state stack
    // 获得当前状态栈
    def getStates():
      if currentState: return currentState.getStates()
      else: return []
    # Recursively updates the machine.
    // 递归更新状态机
    def update():
        # If we’re in no state, use the initial state
        // 如果没有处于任何状态,使用初始状态
        if not currentState:
            currentState = initialState
            return currentState.getEntryAction()
        # Try to find a transition in the current state
        // 从当前状态尝试找到一个转换
        triggeredTransition = None
        for transition in currentState.getTransitions():
            if transition.isTriggered():
            triggeredTransition = transition
        # If we’ve found one, make a result structure for it
        // 如果我们找到了一个转换,为其生成一个结果结构体
        if triggeredTransition:
            result = UpdateResult()
            result.actions = []
            result.transition = triggeredTransition
            result.level = triggeredTransition.getLevel()
        # Otherwise recurse down for a result
        // 否则递归获得结果
            result = currentState.update()
        # Check if the result contains a transition
        // 检查结果中是否包含转换
        if result.transition:
            # Act based on its level
            // 基于本层执行
            if result.level == 0:
                # Its on our level: honor it
                // 结果行为在本层:执行
                targetState = result.transition.getTargetState()
                result.actions += currentState.getExitAction()
                result.actions += result.transition.getAction()
                result.actions += targetState.getEntryAction()
                # Set our current state
                // 设置当前状态
                currentState = targetState
                # Add our normal action (we may be a state)
                // 添加基本操作
                result.actions += getAction()
                # Clear the transition, so nobody else does it
                // 清除转换,因此没有其他(?)执行它
                result.transition = None
            else if result.level > 0:
                # Its destined for a higher level
                // 这表示一个更高的层级
                # Exit our current state
                // 退出当前状态
                result.actions += currentState.getExitAction()
                currentState = None
                # Decrease the number of levels to go
                // 当相对于目标层级为降低时
                result.level -= 1
                 # It needs to be passed down
                // 它需要向下迁移
                targetState = result.transition.getTargetState()
                targetMachine = targetState.parent
                result.actions += result.transition.getAction()
                result.actions += targetMachine.updateDown(targetState, -result.level)
                # Clear the transition, so nobody else does it
                // 清除转换,因此没有其他(?)执行它
                result.transition = None
        # If we didn’t get a transition
        // 如果我们没有(从结果中)取得转换
        # We can simply do our normal action
        // 我们可以简单的执行我们的基本行为
            result.action += getAction()
        # Return the accumulated result
        // 返回积累的结果
            return result
# Recurses up the parent hierarchy, transitioning into
# each state in turn for the given number of levels
// 递归父层次结构,依次转换到指定层级号的每个状态
def updateDown(state, level):
    # If we’re not at top level, continue recursing
    // 如果不在顶层,继续递归
    if level > 0:
    # Pass ourself as the transition state to our parent
    // 将自己作为转换状态传递给父状态
        actions = parent.updateDown(this, level-1)
    # Otherwise we have no actions to add to
    // 否则我们将没有要添加的行为
    else: actions = []
    # If we have a current state, exit it
    // 如果当前状态存在,退出
    if currentState:
        actions += currentState.getExitAction()
    # Move to the new state, and return all the actions
    // 转移到新的状态,并且返回所有行为
    currentState = state
    actions += state.getEntryAction()
    return actions


The state class is substantially the same as before, but adds an implementation for getStates:




class State (HSMBase):
    def getStates():
        # If we’re just a state, then the stack is just us
        // 如果是一个状态,那幺要返回的状态栈仅有这个状态自身
        return [this]
    # As before...
    def getAction()
    def getEntryAction()
    def getExitAction()
    def getTransitions()


Similarly, the Transition class is the same, but adds a method to retrieve the level of the transition.




class Transition:   
    # Returns the different in levels of the hierarchy from
    # the source to the target of the transition.
    def getLevel()
    # As before...
    def isTriggered()
    def getTargetState()
    def getAction()


Finally, the SubMachineState class merges the functionality of a state and a state machine.




class SubMachineState (State, HierarchicalStateMachine):
    # Route get action to the state
    // 转换
    def getAction(): return State::getAction()
    # Route update to the state machine
    // 转换   
    def update(): return HierarchicalStateMachine::update()
    # We get states by adding ourself to our active children
    // 通过将自身加入活跃子节点集中获取当前状态
    def getStates():
        if currentState:
            return [this] + currentState.getStates()
            return [this]


Implementation Notes:实现说明


I’ve used multiple inheritance to implement SubMachineState. For languages (or programmers) that don’t support multiple inheritance, there are two options. The Sub- MachineState could encapsulate HierarchicalStateMachine, or the Hierarchical- StateMachine can be converted so that it is a sub-class of State. The downside with the latter approach is that the top-level state machine will always return its active action from the update function, and getStates will always have it as the head of the list.


我已经使用多重继承来实现SubMachineState类。对于不支持多重继承的语言(或程序员),有两种选择。 Sub-MachineState可以封装HierarchicalStateMachine,或者Hierarchical-StateMachine可以被转换,使其成为State的子类。后一种方法的缺点是顶级状态机将始终从更新函数返回其活动操作,并且getStates将始终将其作为列表的头部。


I’ve elected to use a polymorphic structure for the state machine again. It is possible to implement the same algorithm without any polymorphic method calls. Given that it is complex enough already, however, I’ll leave that as an exercise. My experience deploying a hierarchical state machine involved an implementation using poly- morphic method calls (provided on the CD). In-game profiling on both PC and PS2 showed that the method call overhead was not a bottleneck in the algorithm. In a system with hundreds or thousands of states, it may well be, as cache efficiency issues come into play.


Some implementations of hierarchical state machines are significantly simpler than this by making it a requirement that transitions can only occur between states at the same level. With this requirement, all the recursion code can be eliminated. If you don’t need cross hierarchy transitions, then the simpler version will be easier to implement. It is unlikely to be any faster, however. Because the recursion isn’t used when the transition is at the same level, the code above will run about as fast if all the transitions have a zero level.


我已经选择再次使用状态机的多态结构。没有任何多态方法调用就可以实现相同的算法。鉴于它已经足够复杂了,我将把它留作练习。我部署分层状态机的经验涉及使用多态方法调用的实现(在CD上提供)。 PC和PS2上的游戏内分析表明,方法调用开销不是算法中的瓶颈。在具有数百或数千个状态的系统中,很可能会出现缓存效率问题。




Performance :开销


The algorithm is O(n) in memory, where n is the number of layers in the hierarchy. It requires temporary storage for actions when it recurses down and up the hierarchy.




Similarly, it is O(nt) in time, where t is the number of transitions per state. To find the correct transition to fire, it potentially needs to search each transition at each level of the hierarchy and O(nt) process. The recursion, both for a transition level <0 and for a level >0 is O(n), so it does not affect the O(nt) for the whole algorithm.


类似地,它是时间上的O(nt),其中t是每个状态的转换数。要找到正确的触发转换,可能需要在层次结构的每个级别和O(nt)进程中搜索每个转换。对于转换级别<0和级别> 0的递归都是O(n),因此它不会影响整个算法的O(nt)。




The implementation of transitions bears more than a passing resemblance to the implementation of decision trees. This is no coincidence, but we can take it even further. Decision trees are an efficient way of matching a series of conditions, and this has application in state machines for matching transitions.


We can combine the two approaches by replacing transitions from a state with a decision tree. The leaves of the tree, rather than being actions as before, are transitions to new states.






A simple state machine might look like Figure 5.20.





The diamond symbol is also part of the UML state chart diagram format, repre- senting a decision. In UML there is no differentiation between decisions and transi- tions, and the decisions themselves are usually not labelled.


In this book I’ve labelled the decisions with the test that they perform, which is clearer for our needs.






When in the “Alert” state, a sentry has only one possible transition: via the de- cision tree. It quickly ascertains whether the sentry can see the player. If the sentry is not able to see the player, then the transition ends and no new state is reached. If the sentry is able to see the player, then the decision tree makes a choice based on the distance of the player. Depending on the result of this choice, two different states may be reached: “Raise Alarm” or “Defend.” The latter can only be reached if a further test (distance to the player) passes.




To implement the same state machine without the decision nodes, the state ma- chine in Figure 5.21 would be required. Note that now we have two very complex con- ditions and both have to evaluate the same information (distance to the player and distance to the alarm point). If the condition involved a time-consuming algorithm (such as the line of sight test in our example), then the decision tree implementation


would be significantly faster.





Pseudo-Code :伪代码


We can incorporate a decision tree into the state machine framework we’ve developed so far.




The decision tree, as before, consists of DecisionTreeNodes. These may be decisions (using the same Decision class as before) or TargetStates (which replace the Action class in the basic decision tree). TargetStates hold the state to transition to and can contain actions. As before, if a branch of the decision tree should lead to no result, then we can have some null value at the leaf of the tree.


与以前一样,决策树由DecisionTreeNodes组成。这些可能是决策(使用与之前相同的Decision类)或TargetStates(它们替换基本决策树中的Action类)。 TargetStates保持状态转换并可以包含操作。和以前一样,如果决策树的一个分支应该导致没有结果,那幺我们可以在树的叶子上有一些空值。


The decision making algorithm needs to change. Rather than testing for Actions to return, it now tests for TargetState instances:




We can then build an implementation of the Transition interface which supports these decision trees. It has the following algorithm:






As before, this implementation relies heavily on polymorphic methods in an object- oriented framework. The corresponding performance overhead may be unacceptable in some cases where lots of transitions or decisions are being considered.



Be First to Comment


电子邮件地址不会被公开。 必填项已用*标注