Chapter 5 Decision Making

5.3 STATE MACHINES：状态机

## Chapter 5 Decision Making

### 5.3 STATE MACHINES：状态机

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.

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.

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].

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.

#### 5.3.2 THE ALGORITHM ：算法

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.

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;

// 检查并执行转换，同时返回一个动作列表
Update()
{
// 假定没有转换被触发
triggeredTransition = None;

// 遍历所有状态并保存第一个被触发的状态
for transition in currentState.getTransitions()
{
if transition.isTriggered():
triggeredTransition = transition;
break;
}

// 检查是否有状态被触发？
if triggeredTransition
{
targetState = triggeredTransition.getTargetState();

// 在行为列表之中增加旧状态的退出操作、状态转移的操作以及新状态的入口操作
actions = currentState.getExitAction()
actions += triggeredTransition.getAction()
actions += targetState.getEntryAction()

// 完成状态转移并返回行为列表
currentState = targetState
return actions
}
// 否则直接返回当前状态的行为列表
else return currentState.getAction()
}
}```

#### 5.3.4 DATA STRUCTURES AND INTERFACES ：数据结构与接口

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:

```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.

#### 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.

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
{// 条件接口类
actions
def getAction(): return actions
targetState
def getTargetState(): return targetState
condition
def isTriggered(): return condition.test()
}```

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

Conditions have the following simple format:

isTriggered函数现在将测试委托给其条件成员。

```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)
{// 数值条件
minValue;
maxValue;
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)
{// 布尔条件
conditionA
conditionB
def test()
{
return conditionA.test() and conditionB.test();
}
}
class NotCondition (Condition)
{
condition
def test()
{
return not condition.test();
}
}
class OrCondition (Condition)
{
conditionA
conditionB
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.

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.

#### 5.3.6 PERFORMANCE ：开销

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.

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.

#### 5.3.7 IMPLEMENTATION NOTES ：实现的一些说明

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).

```class MyFSM
{
// 声明所有状态名
enum State
{
PATROL,
DEFEND,
SLEEP
};
// 当前状态
myState；
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.

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.

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:

```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.

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.

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.

#### 5.3.9 HIERARCHICAL STATE MACHINES：分层状态机

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).

Unfortunately, the robot can run low on power, whereupon it has to scurry off to the nearest electrical 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.

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.

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.

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.

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.

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.

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.

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.

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].

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.

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.

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.

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.

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.

#### 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.

The HSMBase has the following form:

HSMBase类如下所示：

```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:

HierarchicalStateMachine类有着如下实现：

```class HierarchicalStateMachine (HSMBase)
# List of states at this level of the hierarchy
// 本层次的状态列表
states
# The initial state for when the machine has to
# current state.
// 机器必须处于当前状态的初始状态
initialState

# The current state of the machine.
// 状态机的当前状态
currentState = initialState

# Gets the current state stack
// 获得当前状态栈
def getStates():
if currentState: return currentState.getStates()
else: return []

// 递归更新状态机
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
break

# 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
// 否则递归获得结果
else:
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

else:
# 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
// 如果我们没有（从结果中）取得转换
else:
# 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()
else:
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.

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.

#### 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.

#### 5.3.10 COMBINING DECISION TREES AND STATE MACHINES ：决策树与状态机的结合

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.

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:

#### Implementation：实现

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.