Events as Entities

[alanjfs]

Problem

Currently, events are designed to fit with pre-existing entities in your game or application. For example, if your game character is an entity with Position and Renderable components, then you could attach a Sequentity::Track that carry events related to changes to those components.

registry.view<Sequentity::Track>().each([](const auto& track, auto& position) {

    // Iterate over all events for this track, at the current time
    Sequentity::Intersect(track, current_time, [](const auto& event) {
        if (event.type == TranslateEvent) {
            auto& data = static_cast<TranslateEventData*>(event.data);

            // Do something with it
            event.time
            event.length
        }
    });
});

So far so good.

The consequence however is that each Track becomes a "mini-ECS" in that they themselves form a registry of additional entities, each one carrying a Sequentity::Channel component, which in turn form yet another registry of the Sequentity::Event. Except they don't carry the advantage of an ECS, in that they are limited to this one component each, and you can't operate on them like you would other entities in your application.

Solution

What if each of these were entities of the same registry, associated to your application entity indirectly?

bob = registry.create();

registry.assign<Name>(bob, "Bob");
registry.assign<Position>(bob);
registry.assign<Renderable>(bob, "BobMesh.obj");

Just your everyday ECS. Now let's get Sequentity in there.

track1 = registry.create();
channel1 = registry.create();
event1 = registry.create();

registry.assign<Name>(track1, "Track 1");
registry.assign<Sequentity::Track>(track1, bob); // With reference to another entity

registry.assign<Name>(channel1, "Channel 1");
registry.assign<Sequentity::Channel>(channel1, track);  // With reference to its "parent" track

registry.assign<Sequentity::Event>(event1, channel1); // With reference to its "parent" channel
registry.assign<SomeData>(event1);  // Your data here

Benefits

1. The immediate benefit is that we avoid the need to store a void* inside the Event struct itself, and instead rely on EnTT to take ownership and delete any memory alongside removal of the entity.
2. Another is that we're now able to iterate over events independently.
3. And another is that moving events from one track to another is now a matter of retargeting that .parent value, rather than physically moving a member of the channel.events vector like we must currently.

registry.view<Sequentity::Event>().each([](const auto& event) {
  // Do something with all events
});

We could also iterate over tracks and channels individually in the same way, if we needed just them and not the events (to draw the outliner, for example). And if we wanted, we could still reach out and fetch the associated channel and track from an event by traversing what is effectively a hierarchy.

registry.view<Sequentity::Event>().each([](const auto& event) {
  const auto& channel = registry.get<Sequentity::Channel>(event.parent);
  const auto& track = registry.get<Sequentity::Track>(channel.parent);
});

Cost

The primary (and poor) reason for not going this route immediately was the percieved performance cost of introducing this hierarchy of enities and traversing between levels.

One of the (hypothetical) advantage of the current data layout is that it is tightly packed.

struct Track {
  std::vector<Channel> channels {
    struct Channel {
      std::vector<Event> events {
        struct Event { ... };
      };
    };
  };
};

Each track can be drawn as a whole, with its channels tightly laid out in memory, and its inner events tightly laid out in memory too. Hypotethically, this should be the absolute most optimal way of storing and iterating over the data, and it just so happens to also make for a suitable editing format; e.g. moving a track takes all data with it, moving events in time along a single channel doesn't really make a difference, as the data is all the same and doesn't need to physically move (just need a change to the .time integer value).

If each event is an entity, then in order to read from its channel we need to perform a separate lookup for its channel. That channel may reside elsewhere in memory, as may its track.

We could potentially sort these three pools such that tracks, its channels and its events reside next to each other, in which case accessing these should be almost as fast (?), except we still need to perform a lookup by entity as opposed to just moving the pointer in a vector.

Aside from this (hypothetical) performance cost however, is there any cost to API or UX? Worth exploring.

[alanjfs]

Took a crack at this, but ran into a few issues. Overall, it technically works. But it got a little more complex.

• Browse repository at this point

Background

Data in Sequentity is organised into a hierarchy with three levels.

• Track
  • Channel
    • Event
    • Event
    • Event
    • Event

1. Where each Event is owned by a single Channel
2. Each Channel is owned by a single Track
3. Track and Channel hold attributes that affect the behavior of a related Event.

Problem 1 - Too much Searching

In the previous implementation, the Track was assigned to the entity it affects, like a character, and physically contained each Channel, which in turn physically contained each Event.

struct Event {
   entt::entity owner;
};

struct Channel {
   entt::entity owner;
   std::vector<Event> events;
};

struct Track {
   entt::entity owner;
   std::vector<Channel> channels;
};

That meant that I could iterate over all channels in a track, and subsequently over each event in a channel by just moving linearly through memory.

But because these are now individual entities, with an indirect connection to their "parent", there's quite a bit of searching happening. Searching that may fail and needs synchronisation, for example if a Channel is removed then I would need to ensure that all related entities are removed alongside it.

1. The main hurdle is that even though Event, Channel and Track form a strict hierarchy, they are individual entities we need to find() many times.
2. For example, when drawing events, we iterate over registry.view<Event>().each(...) but then each event has got a parent Channel, which in turn has a parent Track.
3. The behavior of the event is based on properites of those parents. E.g. if the Track is muted, the event has no effect. If the Channel is deleted, the event is too.
4. To find these, we could either perform a linear search through the registry, per event, looking for who the parent is. Or, we can store reference to each Event in each Channel and iterate top-to-bottom.

sequentity/Sequentity.h

Line 905 in 5cd803f

for (auto channel_entity : track.children) {

The latter approach is what I've done here, and it's not ideal.

void Intersect(entt::registry& registry, TimeType time, EntityIntersectFunc func) {
    registry.view<Track>().each([&](const auto& track) {
        if (track.mute) return;
        if (track._notsoloed) return;

        for (auto channel_entity : track.children) {
            auto& channel = registry.get<Channel>(channel_entity);

            for (auto event_entity : channel.children) {
                auto& event = registry.get<Event>(event_entity);

                if (event.removed) continue;
                if (!event.enabled) continue;

                if (_contains(event, time)) {
                    func(track.owner, event_entity);
                }
            }
        }
    });
}

Is there another way?

Problem 2 - Sorting

1. The order in which Tracks, Channels and Events are drawn is important
2. Each Track needs a user-controllable order, e.g. in the order of the equivalent character hierarchy we're animating.

Events don't necessarily need sorting, as the user can move these around freely, so we do searching both as entities and plain datastructure.

Before, the order was determined by their memory layout in e.g. Track.channels. With entities, I'm solving it by similarly storing child entities themselves in a vector of its parent. Which is error prone and needs synchronisation, e.g. if you delete the Track you need to delete each related Channel explicitly.

struct Track {
    const char* label { "Untitled track" };
    entt::entity owner { entt::null };
    std::vector<entt::entity> children;
};

...

std::sort(track.children.begin(),track.children.end(), [](const entt::entity lhs,
                                                            const entt::entity rhs) -> bool {
    return registry.get<Sequentity::Channel>(lhs).type < registry.get<Sequentity::Channel>(rhs).type;
});

Summary

I'm not confident this is the way to go, but may have missed something. Because the data hierarchy is heavily connected and because iterating over the data is consistent with this hierarchy, my gut feeling says this isn't a data-oriented design, but rather an ECS-oriented design.