Action Lists
Action lists are one of my favorite data structures for games. But from what I’ve found, they don’t seem to be very well known outside of the small community of students at DigiPen Institute of Technology. An action list is simply a list of actions which updates sequentially. An action can block the action behind it, preventing others to run until it’s finished, or can run concurrently. This provides a simple yet powerful interface that can be used for AI, animation, UI, and many other things.
Here is a quick demo using the Unity3D Web Player to give you an idea of what action lists can achieve:
Everything the green guy does is done using action lists; each rotation and movement is an action.
Actions
As you can see, actions can take many different forms. They could scale an object, change its color, play a sound, call a function – really they can be almost anything. So let’s start out by looking at an example action interface:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
/* base runnable action */ class action { public: // ctor / dtor action(void); virtual ~action(void); // virtual methods virtual void startup(void) {} virtual void update(float) {} virtual void shutdown(void) {} // status setters void set_paused(bool paused); void set_finished(void); void set_blocking(bool blocking); private: // private members bool _blocking; bool _started; bool _finished; bool _paused; }; // class action |
The action interface is really simple. It just provides a few virtual methods that can be overloaded and a bunch of booleans that denote the status of the action. When an action’s _finished bool is set, it will get shutdown by the action list and removed from the list. If an action is blocking, actions behind it in the sequence won’t be able to run until the blocking action is finished. And if an action is paused, it won’t update. Actions lists can be simplified without a pausing functionality but it can be nice to have.
Action List
As the name implies, the action_list is a list of actions. It maintains ownership of the actions and handles calling their startup, update, and shutdown methods.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/* runs actions in sequence, stopping at a blocking action */ class action_list : public action { public: // public methods void update(float dt); void push_back(action* back); void push_front(action* front); void clear(void); bool empty(void) const; private: // private types typedef std::list // private members action_container _actions; }; // class action_list |
Here, I’m using a std::list for the underlying container of the action_list. But this could easily be a std::vector or an array, just keep in mind that actions tend to run in a first in, first out fashion.
You may have noticed that action_list inherits from action. This is the composite design pattern, and allows an entire action_list to be added to another action_list as an action.
Most of the methods of action_list are fairly clear and are mostly dependent on the underlying choice of container. So, we’ll just look at the details of the update function:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
void action_list::update(float dt) { if (is_paused()) return; // update actions until blocked for (auto it = _actions.begin(); it != _actions.end();) { action* cur_action = *it; // skip update if paused if (!cur_action->is_paused()) { // start if hasn't started if (!cur_action->is_started()) { cur_action->_started = true; cur_action->startup(); } cur_action->update(dt); // remove if finished if (cur_action->is_finished()) { cur_action->shutdown(); delete cur_action; it = _actions.erase(it); continue; } } // remaining actions blocked if (cur_action->is_blocking()) break; ++it; } // finish if empty if (empty()) set_finished(); } |
The update iterates over the list of actions and updates them until the end of the list or until a blocking action is reached. It also handles calling the startup and shutdown methods when necessary.
Action Lanes
You’ll often want to have multiple actions operating on an object that don’t necessarily relate to each other. But doing so can sometimes be impossible when you want two sequences of blocking actions to run concurrently. You could have multiple action lists each running separate sequences, but it makes more sense to have one action list for one object. To do this, we can add the concept of lanes to action_list. A lane is essentially a self-contained action list that gets updated separately from the other lanes. This can be easily achieved by creating a new container made up of multiple action_containers from before. Here’s an action_list interface using a std::map as the container of action_containers:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
/* runs actions in order, stopping at a blocking action */ class action_list : public action { public: // typedefs typedef int lane_id; // public methods void update(float dt); void push_back(action* back, lane_id id = 0); void push_front(action* front, lane_id id = 0); void clear(void); void clear_lane(lane_id clear_id); bool empty(void) const; bool lane_empty(lane_id id) const; private: // private types typedef std::list typedef std::map typedef std::pair // private members lane_map _lanes; }; // class action_list |
This is mostly the same as before, with the added option of providing a lane_id when adding an action to the list, and of course, the lane_map. The update function is also very similar as before, but now iterating over each lane then each action within the lane.
Action lanes are of course not absolutely necessary but do provide a a bit of cleanliness when working with many actions. You could define a lane as the animation lane while having a separate lane maintain the actual behavior of the object. This provides a very clear and clean way of maintaining actions that don’t necessarily relate to each other.
Summary
As you can see, action lists are fairly simple to implement, but they provide a lot of power. They give an interface for behaviors to get updated in a given sequence or concurrently. They also allow a lot of flexibility and can be used for a wide range of different tasks.