作者：Randy Gaul

动作列表是用于游戏引擎内的各种任务的简单数据结构。可以说，动作列表总是可以替代某些状态机。

最普遍的（和最简单的）一种行为组织结构是有限状态机。状态机通常用C或C++的交换或数组、或者其他语言的if和else语句来执行，所以比较死板和不灵活。动作列表更强大，因为它以清楚的方式模拟事物在现实中的发生情况。为此，动作列表比有限状态机更直观和灵活。

快速回顾

动作列表只是一个用于即时动作的概念的组织方案。动作是按FIFO（先入先出）顺序储存的。这意味着先进入的动作列表的动作先完成并引退，跟着才执行第二个动作。动作列表并不明确地遵守FIFO格式，但核心是一样的。

在所有游戏循环中，动作列表和各个在表中的动作都是按顺序更新的。一旦一个动作完成，它就从列表中移除。

动作是指楞以执行某些活动的功能。比如，动作可以在以下不同的区域中执行活动：

UI：播放短事件如“成就”、播放动画、弹出窗口、显示动态内容：移动、旋转、弹跳、淡入淡出、一般的渐变。

AI：队列行为：移动、等待、巡逻、逃跑、攻击。

关卡逻辑或行为：移动的平台、障碍物移动、切换关卡。

动画/声音：播放、暂停。

使用动作列表不能有效地表示低级事件如寻径或集合。战斗和其他高度专门化的游戏玩法也不适合通过动作列表来执行。

动作列表的种类

以下是动作列表数据结构中应该包含的内容。请注意，后文将谈到更多细节。

class ActionList
{
public:
void Update( float dt );

void PushFront( Action *action );
void PushBack( Action *action );
void InsertBefore( Action *action );
void InsertAfter( Action *action );
Action *Remove( Action *action );

Action *Begin( void );
Action *End( void );

bool IsEmpty( void ) const;
float TimeLeft( void ) const;
bool IsBlocking( void ) const;

private:
float duration;
float timeElapsed;
float percentDone;
bool blocking;
unsigned lanes;
Action **actions; // can be a vector or linked list
};

值得注意的是，各个动作的实际储存不一定是真正的链接表——像C++ std::vector也是可以的。我自己的偏好是把所有动作聚集在一个配置器里，用干扰链接表把列表连接起来。通常来说，动作列表适用于对性能不敏感的地方，所以当制作动作列表数据结构时，高度数据导向型的优化措施可能是不必要的。

动作

这整个工作的关键在于动作本身。各个动作都应该是完全独立的，因此动作列表对动作的内部是一无所知的。这使动作列表成为极其灵活的工具。动作列表不关心它运行的UI动作还是管理3D模型角色的移动。

执行动作的好办法是通过一个抽象的界面。在动作对象的动作列表上可以看到一些特殊的功能。以下是基本动作的例子：

class Action
{
public:
virtual Update( float dt );
virtual OnStart( void );
virtual OnEnd( void );
bool isFinished;
bool isBlocking;
unsigned lanes;
float elapsed;
float duration;

private:
ActionList *ownerList;
};

OnStart()和OnEnd()功能是不可缺少的。这两个功能无论动作何时插入列表和结束，都要分别执行。这些功能使动作完全独立。

阻塞动作和非阻塞动作

对动作列表的拓展是，把动作表示为阻塞动作和非阻塞动作。二者的区别很明显：阻塞动作结束动作列表的更新程序，禁止动作进一步更新；非阻塞动作允许后随的动作更新。

简单的布尔值可以用于确定动作是阻塞的还是非阻塞的。以下是表现动作列表的更新程序的伪代码：

void ActionList::Update( float dt )
{
int i = 0;
while(i != numActions)
{
Action *action = actions + i;

action->Update( dt );
if(action->isBlocking)
break;

if(action->isFinished)
{
action->OnEnd( );
action = this->Remove( action );
}

++i;
}
}

使用非阻塞动作的一个好处是，允许某些行为同时运行。例如，如果我们有一队列动作要执行，那么角色应该能够同时执行。如果一个敌人从玩家身边逃走时，如果它必须跑一段，停下挥挥手，再跑一段再停下来挥手，那就太怪异了。

阻塞和非阻塞动作的概念直观地匹配了游戏需要执行的大部分类型的简单行为。

案例

我们来举一个能体现动作列表的真实执行情况的例子，以便了解如何使用动作列表以及为什么它是实用的。

问题

在简单的2D游戏中，敌人要来回巡逻。当敌人发现玩家时，它就会向玩家投炸弹并停止巡逻。投完炸弹后应该有一段短暂的冷却时间，这时的敌人是完全静止不动的。如果玩家仍然在敌人的视野内，冷却之后敌人将继续投炸弹。如果玩家离开视野，则敌人继续巡逻。

每一颗炸弹要飞过2D世界，且要遵守游戏所执行的贴图物理法则。炸弹要等导火线时间结束后才能爆炸。爆炸效果由动画、声音和炸弹的碰撞盒的移除及视觉效果组成。

给这个行为构造一个状态机是可能的，且并不困难，只是需要一些时间。各个状态的过渡需要手动写代码，保存之前的状态到后面，可能带来麻烦。

动作列表的解决方案

幸运的是，使用动作列表可以很好地解决这个问题。首先，我们想象一个空白的动作列表。这个空白的动作列表将表示一系列敌人“要做”的动作；敌人的动作列表如果是空白的，则说明它是不活动的。

必须思考一下如何把理想的行为区分为小部分。首先要写下巡逻行为。我们假设敌人是先向左边走一段距离，再返回向右边走相同的一段距离，再返回，如此反复。

以下是向左巡逻的动作列表：

class PatrolLeft : public Action
{
virtual Update( float dt )
{
// Move the enemy left
enemy->position.MoveLeft( );

// Timer until action completion
elapsed += dt;
if(elapsed >= duration)
isFinished = true;
}

virtual OnStart( void ); // do nothing

virtual OnEnd( void )
{
// Insert a new action into the list
list->Insert( new PatrolRight( ) );
}

bool isFinished = false;
bool isBlocking = true;
Enemy *enemy;
float duration = 10; // seconds till finish
float elapsed = 0; // seconds
};

PatrolRight的代码与上述一样，除了方向改了。当这些动作之一被放入敌人的动作列表中时，敌人会无休止地向左向右巡逻。

以下图解是巡逻的动作列表的流程，有四个当前动作列表的状态快照。

接下来的动作应该是检测玩家是否在附近。这可以用永远不能结束的非阻塞动作来完成。这个动作会检测玩家是否在敌人周围，如果是则触发新动作“ThrowBomb”，这个投弹行为后还紧接着一个“Delay”动作。

非阻塞动作将一直存在并被更新，但动作列表会继续更新所有除了它以外的后续动作。阻塞动作（如巡逻）将被更新，并且动作列表会停止更新所有后续动作。记住，这里的这个动作是为了看玩家是否在敌人视野内，永远不会离开动作列表！

以下是发现玩家的动作代码：

class DetectPlayer : public Action
{
virtual Update( float dt )
{
// Throw a bomb and pause if player is nearby
if(PlayerNearby( ))
{
this->InsertInFrontOfMe( new ThrowBomb( ) );

// Pause for 2 seconds
this->InsertInFrontOfMe( new Pause( 2.0 ) );
}
}

virtual OnStart( void ); // do nothing
virtual OnEnd( void ) // do nothing

bool isFinished = false;
bool isBlocking = false;
};

ThrowBomb动作是一个向玩家投炸弹的阻塞动作。它后面跟着ThrowBombAnimation（播放敌人动画），但我为了简洁，我把它省略了。投弹后的中止发生在动画后，会持续一小段时间。

我们来看看这个动作列表的图解流程：

(蓝圈是阻塞动作，白圈是非阻塞动作。)

炸弹本身就是一个全新的游戏对象，它自己的动作列表中也有三个左右的动作。第一个动作是阻塞动作“中止”；后面跟着播放爆炸动画。爆炸动画本身与碰撞盒一起，必须移除。最后，还要播放爆炸声音效果。

总之，应该有6到10种不同的动作类型将用于的制作这个行为。这些动作的最精华之处在于，它们可以重复利用于任意类型的敌人的行为，而不只是上述敌人。

动作线路

每一个动作列表在它的当前形式都有一条动作可以存在的线路。一条线路是一系列要被更新的动作。线路可以是阻塞的，可非阻塞的。

线路的完美执行法是使用位掩码。使用一个32bit的整数就可以构造32条不同的线路。

动作应该有一个代表它所具有的所有线路的整数。32条不同的线路足以表示不同的动作类型。在列表本身的更新程序之中，各条线路可以是阻塞的，也可以是非阻塞的。

以下是使用位掩码更新动作列表的例子：

void ActionList::Update( float dt )
{
int i = 0;
unsigned lanes = 0;
while(i != numActions)
{
Action *action = actions + i;

if(lanes & action->lanes)
continue;

action->Update( dt );
if(action->isBlocking)
lanes |= action->lanes;

if(action->isFinished)
{
action->OnEnd( );
action = this->Remove( action );
}

++i;
}
}

这大大增加了列表的灵活性，现在一个动作列表可以运行32个不同类型的动作，而在些之前，要使用32个不同的动作列表才能达到相同的效果。

延迟动作

一个什么也不做，但延期其他所有动作一段时间的动作是非常有用的。这个动作的原理是阻止后续动作发生直到计时器结束。

延迟动作的执行非常简单：

class Delay : public Action
{
public:
void Update( float dt )
{
elapsed += dt;
if(elapsed > duration)
isFinished = true;
}
};

同步动作

另一个实用的动作是阻塞直到它自己成为列表上的第一个动作。当一些不同的非阻塞动作正在运行时，但你又不确定它们的结束顺序时，就可以使用这种同步动作。同步动作保证没有之前的非阻塞动作正在运行。

同步动作的执行也非常简单：

class Sync : public Action
{
public:
void Update( float dt )
{
if(ownerList->Begin( ) == this)
isFinished = true;
}
};

高级特征

到目前为止，我所描述的动作列表已经显得非常强大了。但是，还有一些额外的特征能让它更加耀眼。这些特征比较先进，但我并不推荐，除非你可以不太麻烦地执行它们。

发送信息

向一个动作直接发送信息的能力，或允许动作向另一个动作和游戏对象发送信息，是非常有用的。这使得动作变得非常灵活。具有这个功能的动作列表通常可以充当“一个可怜人的脚本语言”。

动作可以发送的非常实用的信息包括：开始、结束、中止、重新开始、完成、取消、阻止等。阻止这一项是非常有意思的——无论何时一个新动作被放入列表，它就会阻止其他动作。这些其他动作会希望知道它，可能也让其他后续动作知道这个事件。

执行发送信息的具体办法比较麻烦。因此，执行细节就不在这里说了，毕竟发送信息不是本文的重点。

分级动作

表示动作的层级有不同的方式。其中之一是允许动作列表自身成为另一个动作列表的一个动作。这使多个动作列表可以打包成一个大的动作，置于同一个标识之下。这也使得复杂的动作列表具有更高的易用性，更容易开发和纠错。

另一个方法是让具有单一目标的动作在自己的动作列表中比自身更早刷出其他动作。与前一种方法相比，我自己倾向于这种方法，因为它更容易执行。

总结

把它作为死板的专门状态机的替代品，我已经详细地讨论了动作列表的概念和它的执行办法。动作列表提供了快速开发大量动态行为的简单又灵活的方法。一般来说，动作列表是一种游戏编程的理想数据结构。（本文为游戏邦/gamerboom.com编译，拒绝任何不保留版权的转载，如需转载请联系：游戏邦）

The Action List Data Structure: Good for UI, AI, Animations, and More

by Randy Gaul

The action list is a simple data structure useful for many various tasks within a game engine. One could argue that the action list should always be used in lieu of some form of state machine.

The most common form (and simplest form) of behavior organization is a finite state machine. Usually implemented with switches or arrays in C or C++, or slews of if and else statements in other languages, state machines are rigid and inflexible. The action list is a stronger organization scheme in that it models in a clear manner how things usually happen in reality. For this reason, the action list is more intuitive and flexible than a finite state machine.

Quick Overview

The action list is just an organization scheme for the concept of a timed action. Actions are stored in a first in first out (FIFO) ordering. This means that when an action is inserted into an action list, the last action inserted into the front will be the first to be removed. The action list doesn’t follow the FIFO format explicitly, but at its core they remain the same.

Every game loop, the action list is updated and each action in the list is updated in order. Once an action is finished, it is removed from the list.

An action is some sort of function to call which does some sort of work somehow. Here are a few different types of areas and the work that actions could perform within them:

User Interface: Displaying short sequences such as “achievements”, playing sequences of animations, flipping through windows, displaying dynamic content: move; rotate; flip; fade; general tweening.

Artificial Intelligence: Queued behavior: move; wait; patrol; flee; attack.

Level logic or behavior: Moving platforms; obstacle movements; shifting levels.

Animation/Audio: Play; stop.

Low level things like path finding or flocking are not effectively represented with an action list. Combat and other highly specialized game-specific gameplay areas are also things that one probably should not implement via an action list.

Action List Class

Here’s a quick look at what should lay inside the action list data structure. Please note that more specific details will follow later in the article.

class ActionList
{
public:
void Update( float dt );

void PushFront( Action *action );
void PushBack( Action *action );
void InsertBefore( Action *action );
void InsertAfter( Action *action );
Action *Remove( Action *action );

Action *Begin( void );
Action *End( void );

bool IsEmpty( void ) const;
float TimeLeft( void ) const;
bool IsBlocking( void ) const;

private:
float duration;
float timeElapsed;
float percentDone;
bool blocking;
unsigned lanes;
Action **actions; // can be a vector or linked list
};

It is important to note that the actual storage of each action does not have to be an actual linked list – something like the C++ std::vector would work perfectly fine. My own preference is to pool all the actions inside of an allocator and link lists together with intrusively linked lists. Usually action lists are used in less performance-sensitive areas, so heavy data-oriented optimization will likely be unnecessary when developing an action list data structure.

The Action

The crux of this whole shebang is the actions themselves. Each action should be entirely self-contained such that the action list itself knows nothing about the internals of the action. This makes the action list an extremely flexible tool. An action list will not care whether it is running user interface actions or managing the movements of a 3D modeled character.

A good way to implement actions is through a single abstract interface. A few specific functions are exposed from the action object to the action list. Here is an example what a base action may look like:

class Action
{
public:
virtual Update( float dt );
virtual OnStart( void );
virtual OnEnd( void );
bool isFinished;
bool isBlocking;
unsigned lanes;
float elapsed;
float duration;

private:
ActionList *ownerList;
};

The OnStart() and OnEnd() functions are integral here. These two functions are to be executed whenever an action is inserted into a list, and when the action finishes, respectively. These functions allow actions to be entirely self-contained.

Blocking and Non-Blocking Actions

An important extension to the action list is the ability to denote actions as either blocking and non-blocking. The distinction is simple: a blocking action ends the action list’s update routine and no further actions are updated; a non-blocking action allows the subsequent action to be updated.

A single Boolean value can be used to determine whether an action is blocking or non-blocking. Here is some psuedocode demonstrating an action list’s update routine:

void ActionList::Update( float dt )
{
int i = 0;
while(i != numActions)
{
Action *action = actions + i;

action->Update( dt );
if(action->isBlocking)
break;

if(action->isFinished)
{
action->OnEnd( );
action = this->Remove( action );
}

++i;
}
}

A good example of the use of non-blocking actions would be to allow some behaviors to all run at the same time. For example, if we have a queue of actions for running and waving hands, the character performing these actions ought to be able to do both at once. If an enemy is running from the character it would be very goofy if it had to run, then stop and wave its hands frantically, then keep running.

As it turns out, the concept of blocking and non-blocking actions intuitively matches most types of simple behaviors required to be implemented within a game.

Case Example

Lets cover an example of what running an action list would look like in a real-world scenario. This will help develop intuition about how to use an action list, and why action lists are useful.

Problem

An enemy within a simple top-down 2D game needs to patrol back and forth. Whenever this enemy is within range of the player it needs to toss a bomb towards the player, and pause its patrol. There should be a small cooldown after a bomb is thrown where the enemy stands completely still. If the player is still in range another bomb followed by a cooldown should be thrown. If the player is out of range, the patrol should continue exactly where it left off.

Each bomb should float through the 2D world and abide by the laws of the tile-based physics implemented within the game. The bomb just waits until its fuse timer finishes, and then blows up. The explosion should consist of an animation, a sound, and a removal of the bomb’s collision box and visual sprite.

Constructing a state machine for this behavior will be possible and not too hard, but it will take some time. Transitions from each state must be coded by hand, and saving previous states to continue later might cause a headache.

Action List Solution

Luckily this is an ideal problem to solve with action lists. First, let us envision an empty action list. This empty action list will represent a list of “to do” items for the enemy to complete; an empty list indicates an inactive enemy.

It is important to think about how to “compartmentalize” the desired behavior into little nuggets. The first thing to do would be to get down patrol behaviors. Let’s assume the enemy should patrol left by a distance, then patrol right by the same distance, and repeat.

Here’s what the patrol left action might look like:

class PatrolLeft : public Action
{
virtual Update( float dt )
{
// Move the enemy left
enemy->position.MoveLeft( );

// Timer until action completion
elapsed += dt;
if(elapsed >= duration)
isFinished = true;
}

virtual OnStart( void ); // do nothing

virtual OnEnd( void )
{
// Insert a new action into the list
list->Insert( new PatrolRight( ) );
}

bool isFinished = false;
bool isBlocking = true;
Enemy *enemy;
float duration = 10; // seconds till finish
float elapsed = 0; // seconds
};

PatrolRight will look nearly identical, with the directions flipped. When one of these actions is placed into the action list of the enemy, the enemy will indeed patrol left and right infinitely.

Here is a short diagram showing the flow of an action list, with four snapshots of the state of the current action list for patrolling:

The next addition should be the detection of when the player is nearby. This could be done with a non-blocking action that does not ever complete. This action would check to see whether the player is near the enemy, and if so will create a new action called ThrowBomb directly in front of itself in the action list. It will also place a Delay action right after the ThrowBomb action.

The non-blocking action will sit there and be updated, but the action list will continue updating all subsequent actions beyond it. Blocking actions (such as Patrol) will be updated and the action list will cease to update any subsequent actions. Remember, this action is here just to see whether the player is in range, and will never leave the action list!

Here is what this action might look like:

class DetectPlayer : public Action
{
virtual Update( float dt )
{
// Throw a bomb and pause if player is nearby
if(PlayerNearby( ))
{
this->InsertInFrontOfMe( new ThrowBomb( ) );

// Pause for 2 seconds
this->InsertInFrontOfMe( new Pause( 2.0 ) );
}
}

virtual OnStart( void ); // do nothing
virtual OnEnd( void ) // do nothing

bool isFinished = false;
bool isBlocking = false;
};

The ThrowBomb action will be a blocking action that tosses a bomb towards the player. It should probably be followed by a ThrowBombAnimation, which is blocking and plays an enemy animation, but I’ve left this out for conciseness. The pause behind the bomb will take place of the animation, and wait a little while before finishing.
Let’s take a look at a diagram of what this action list might look like while updating:

Blue circles are blocking actions. White circles are non-blocking actions.

The bomb itself should be an entirely new game object, and have three or so actions in its own action list. The first action is a blocking Pause action. Following this should be an action to play an animation for an explosion. The bomb sprite itself, along with the collision box, will need to be removed. Lastly, an explosion sound effect should be played.

In all there should be around six to ten different types of actions that are all used together in order to construct the needed behavior. The best part about these actions is that they can be reused in the behavior of any enemy type, not just the one demonstrated here.

More on Actions

Action Lanes

Each action list in its current form has a single lane in which actions can exist. A lane is a sequence of actions to be updated. A lane can either be blocked or not blocked.

The perfect implementation of lanes makes use of bitmasks. (For details on what a bitmask is, please see A Quick Bitmask How-To for Programmers and the Wikipedia page for a quick introduction.) Using a single 32-bit integer, 32 different lanes can be constructed.

An action should have an integer to represent all the various lanes that it resides upon. This allows for 32 different lanes to represent different categories of actions. Each lane can either be blocked or not blocked during the update routine of the list itself.

Here is a quick example of the Update method of an action list with bitmask lanes:

void ActionList::Update( float dt )
{
int i = 0;
unsigned lanes = 0;
while(i != numActions)
{
Action *action = actions + i;

if(lanes & action->lanes)
continue;

action->Update( dt );
if(action->isBlocking)
lanes |= action->lanes;

if(action->isFinished)
{
action->OnEnd( );
action = this->Remove( action );
}

++i;
}
}

This provides a heightened level of flexibility, as now an action list can run 32 different types of actions, where beforehand 32 different action lists would be required to achieve the same thing.

Delay Action

An action that does nothing but delay all actions for a specified amount of time is a very useful thing to have. The idea is to delay all subsequent actions from taking place until a timer has elapsed.

The implementation of the delay action is very simple:

class Delay : public Action
{
public:
void Update( float dt )
{
elapsed += dt;
if(elapsed > duration)
isFinished = true;
}
};

Synchronize Action

A useful type of action is one that blocks until it is the first action in the list. This is useful when a few different non-blocking actions are being run, but you aren’t sure what order they will finish in. The synchronize action ensures that no previous non-blocking actions are currently running before continuing.

The implementation of the sync action is as simple as one might imagine:

class Sync : public Action
{
public:
void Update( float dt )
{
if(ownerList->Begin( ) == this)
isFinished = true;
}
};

Advanced Features

The action list described thus far is a rather powerful tool. However there are a couple additions that can be made to really let the action list shine. These are a bit of advanced and I don’t recommend implementing them unless you can do so without too much trouble.

Messaging

The ability to send a message directly to an action, or allow an action to send messages to other actions and game objects, is extremely useful. This allows actions to be extraordinarily flexible. Often an action list of this quality can act as a “poor man’s scripting language”.

Some very useful messages to post from an action can include the following: started; ended; paused; resumed; completed; canceled; blocked. The blocked one is quite interesting – whenever a new action is put into a list, it may block other actions. These other actions will want to know about it, and possibly let other subscribers know about the event as well.

The implementation details of messaging is language-specific and rather non-trivial. As such, the details of implementation will not be discussed here, as messaging is not the focus of this article.

Hierarchical Actions

There are a few different ways to represent hierarchies of actions. One way is to allow an action list itself to be an action within another action list. This allows the construction of action lists to package together big groups of actions under a single identifier. This heightens usability and makes more complex action list easier to develop and debug.

Another method is to have actions whose sole purpose is to spawn other actions just before itself within the owning action list. I myself prefer this method to the aforementioned, though it may be a bit more difficult to implement.

Conclusion

The concept of an action list and its implementation have been discussed in detail in order to provide an alternative to rigid ad-hoc state machines. The action list provides a simple and flexible means to rapidly develop a wide range of dynamic behaviors. The action list is an ideal data structure for game programming in general.(source:gamedev.tutsplus)