Desire advice on implementing this animation timeline system

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

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.