# Desire advice on implementing this animation timeline system

I have read a lot of questions on here, as well as books regarding game architecture. I have a general question about the implementation of a game's animation timeline, on which many isolated animations sit. I implemented one recently that proved rather inefficient and bug-prone, so I'm doing it again but this time seeking some advice. According to one book I've looked at, the implementation of a timeline does not have a well-known standardized technique and everyone seems to roll their own. Perhaps some of you can offer advice.

Here is the general situation, where "Time" is the game's passing time, starting at 0 when game launches:

The task: Finding the best data structures to be used such that I can throw any arbitrary value of t at the timeline entity and retrieve the active animation objects at that point in time, and finding these quickly. (Note: this is not a question about finding keyframes, but rather about finding valid animation objects on a timeline of many scheduled animations.)

I am using STL for simplicity. One idea I thought of was to have a general map of animations as my timeline, where the map's key was the start time, since maps automatically sort based on keys. Then, for any value of t I can stop iterating as soon as the key is a value higher than t since I know the animation has not started yet.

But this seems inefficient:

I would always iterate from the beginning, even for animations that have already completed. I don't want a technique that stores flags or pointers for completed animations, because I want to always be able to jump to any t and get active animations for that point in time.

Another problem, the map can only have one key, in this case the start time. To know if an animation is active, the algorithm must also peer inside the value of the map to see if its duration has been completed yet. This seems wasteful, surely there is a better way.

I think you get the path I'm going down, and I know this is an issue that everyone tackles. Any advice?

Limiting my answer to your actual question:

The task: Finding the best data structures to be used such that I can throw any arbitrary value of t at the timeline entity and retrieve the active animation objects at that point in time, and finding these quickly. (Note: this is not a question about finding keyframes, but rather about finding valid animation objects on a timeline of many scheduled animations.)

Firstly, I'd recommend doing the simplest thing that could possibly work first. The following assumes that your timeline isn't changing frequently (or at all).

Keep your animations in a vector (avoid lists or maps unless you have a good reason to use them).

To find all the animations at time T, just iterate through the list returning all the animations whose start time is less than T and whose end time is greater than T.

If you have a very large list of animations in your timeline, and the above approach is too slow, notice that your problem is similar to the geometric one of finding intersections between a line and some axis-aligned boxes. Generally, if we have too much geometry to test at once, we use spacial partitioning to avoid too many intersection tests. You could do the same here, except the problem is much easier (it's one dimensional). Adapt a quadtree solution (or just use a fixed vector of buckets) to do "temporal partitioning".

• I very much enjoyed the other answers and discussions as well, but this cut to the heart of the issue which I eventually learned on google as well. Jun 19 '13 at 17:52

A seeking is your primary concern, a skip list might be your best bet. These can be implemented as a literal linked list or a more compact and cache-friendly data structure using indices into a vector instead of list nodes.

To scrub or advance the timelines, keep a list of events (points in time at which any animation starts or ends). Keep these in a sorted sequence of some kind, e.g., a vector of something like:

struct AnimationEvent {
float time;
enum { START, END } type;
int animationID;
};


Keep a point to the "last time event" you encountered and the last time you looked for. When adding time, you can simply grab the leading time events that fall within the new period, no need for extended searching.

For example, in the graphic above, you'd have a list like

|   0 | START | 12 |
|   0 | START | 13 |
|   0 | START | 16 |
|   1 | START |  1 |
|   1 | START | 14 |
|   2 | START |  2 |


You check what happens in the first second. You see that animation nodes 12, 13, and 16 all start. You record that the last node you consumed was at index 2 and at time 1. You advanced another 0.5 seconds. The next event starts at 1s so nothing happens. You now record that the last node you consumed was still index 2 but at time 0.5s, and you advanced the active nodes (12, 13, 16) by 0.5s. You advance another 0.5s. Now your time is 1s so you consume the records indicating nodes 1 and 14 have started. You advanced your previously active nodes (still 12, 13, 16) by the additional 0.5s. You record that the last node you consumed was at index 4 at time 1.0s. Repeat. When you consume a node for animation, start it or end it as appropriate, and update nodes by the delta in time as appropriate (if an animation was due to start in 0.3s but you advanced 0.5s, then you must both start that animation and advance it by 0.2s).

I will note that this latter technique is super useful. It's used in animation, clipping, spatial partitioning, etc. Internalize it.

• I got distracted by your useful website which I am going to peer at first, then revert back to your answer here. thanks man. Jun 18 '13 at 7:33
• Ok, what's not clear here is the purpose of storing the last index you looked at, and at what time, since it appears you are still iterating from the start of this list every time? Additionally, if randomly scrubbing through time, forward or backward, does this list still serve well? Jun 18 '13 at 9:05
• You don't need to constantly reiterate from the start of the list. That's just a waste. Probably won't matter for most games, the wasted time will be nearly immeasurable. Start where you left off, though, and you can more easily tell "new" events from "old" ones. And yes, going backward the algorithm is the exact same, just reverse the direction of the list you iterate in and invert the animation times. Jun 18 '13 at 17:06
• I get it, thanks. I think what I need depends less on the direction of iteration and remembering previous iterations than it does on the ability to quickly and randomly jump between values of t. I am looking into Interval Trees, BSP, etc for this task which seem appropriate as well. Jun 18 '13 at 22:16

ok, im still not quite clear on what problem you're trying to solve. but im going to describe it as "you have some odd game mechanic that means you want to jump around randomly within a set timeline". and that the timeline itself has no logic (which you usually see with cutscene animation tools).

the difficult part here is that usually for cutscene animation tools, you'll trigger an animation at particular frames, and that animation will have been authored in a different tool, and you'd just tell your animation to play. and fix any problems with the seperate authoring tool. thats basically how cutscene playback works ;) just keyframes to start animations (or end looping ones).

the problem we appear to be solving here is one of random access. and im going to assume that this is the desired access pattern over linear playback. which would have a different solution completely. (which i'd be happy to ramble on about if you want).

right. to optimise for random access, im going to go with doing this on a per frame basis, rather than on a node-timeline basis. the general idea is that you're optimising being able to go directly to frame N, over memory footprint, or overall linear playback. to keep things to a sane memory footprint. i'd recommend having a buffer of some arbitrary number of frames that you've pre-processed in the per frame approach. while keeping the actual datastructure the more traditional node-timeline based paradigm.

so lets say that we're going to have a buffer of 1024 frames that we can jump to at any point. each "frame" would contain an array of two 32bit values per node. one an ID for the animation that's playing, and the other would contain the frame (or duration as a float) of the playback position within that animation. the thinking behind having a contiguous sized array is that it may lead to slightly more predictable memory usage and cache usage, but i'd recommend profiling that and working out whether you can get away with only storing the information for the nodes that have animations on that frame, rather than storing all nodes per frame regardless of animation state.

its then up to your animation system to be able to "jump to" a particular animation / time slice when requested by this system, which is a slightly different concern. the system we're talking about here shouldn't really be handling the animations themselves, but slaving a separate system. a similar approach, but unpacking keyframe / node data may work except it'd require a hell of a lot more memory!. it really depends on exactly what you're trying to do, which isnt really clear.

when you have more than 1024 frames, you would need to use a sliding widow approach and "decompresss" from your original space optimised data structure to your memory unfriendly optimised structure. you'll need at least two buffers, one you're reading from, and one you're decompressing too. assuming you're playing back linearly. jumping back to a frame which is no longer "decompressed" would require decompression before you could jump to it. but you could easily keep as many buffers around as you need depending on overall memory requirements.

the major downsides to this is that, linear playback suddenly becomes a hell of a lot of work for absolutely no benefit. you're doing a hell of a lot of preprocessing that you simply dont need to do. if you've got a number of these systems running at the same time, you're going to thrash the hell out of cache. its really not an approach that i'd recommend other for solving the "random access" problem.

doing linear playback is far easier achieved by just storing animation start points, and kicking off animations at particular frames, and stopping them when required. leaving the delta time to keep the animation in sync with the overall timeline. a hell of a lot less effort ;)

whew. ok hopefully that was slightly more useful? and you're kinda getting what im talking about? does this actually solve the problem you're asking?

I you're actually just asking "how do i write a cutscene system". the answer is far far far easier than the above.

• Thanks, but two points: I know how to interpolate keyframes within an animation object, that's not my question. And while I know that premature optimization is bad, this is an important design decision and warrants a thought-out technique before "getting it to work," as I discovered on my previous attempt, which did work but did so very poorly. In such a case, fixing the speed issue is not a matter of tweaking an API as much as it is in designing an efficient architecture implementation Jun 18 '13 at 6:52
• it comes down to your API design. you need to think about your data access patterns, and design around how you will be most likely using the api. for example, you're going to be spending a lot of time saying "im on frame X". and your access paradigm is going to be optimized around tweening things between keyframes at animation points. eg: i'd probably eventually just pre-process the tweening at the cost of memory (eg: every frame gets an array element for every animation with the full tween data). but at first i'd just go for a mathmatical approach. Jun 18 '13 at 6:58
• thanks for the comments, but there really is more to this question than interface; I can have an interface say "add this animation to this timeline" and another interface say "retrieve animations for time t", but its how to implement the best underlying architecture for these requests that I'm asking about. Jun 18 '13 at 6:59
• the point of the interface is that the application using this doesnt care about how its implemented. how you implement it can then be variable. which is kind of what im getting at. as for how to implement it, i'll provide a bit more info later tonight. there's a bunch of things that are curious though, such as, are you going for the hierarchical type clip system ala flash? is this a UI thing? or is this in-game animation sequencing? Jun 18 '13 at 7:04
• You are right about making APIs ignorant of implementation, but I'm passed that stage and directly interested in efficient implementation. I have never used flash, and my question is specifically about a best practice or wise idea for organizing individual animation objects (perhaps you can call them "clips") such that I can quickly retrieve all animations within the whole set of animations that are active any arbitrary value of t Jun 18 '13 at 7:09