Friday, December 11, 2009

Events

An event system can be both useful and dangerous. Useful, because it allows you to create loose couplings between systems in the engine (an animation foot step generates a sound), which makes a more modular design possible and prevents different systems from polluting each other's interfaces.

Dangerous, because the loose coupling can sometimes hide the logical flow of the application and make it harder to understand, by obliterating call stacks and adding confusing layers of indirection. This is especially true the more "features" are added to the event system. For example, a typical nightmare event system could consist of:
  • A global EventDispatcher singleton where everyone can post events, and everyone can listen to events, provided they (multiply) inherit from the EventPublisher and EventSubscriber interface classes.
  • Multiple listeners per event with a priority order and an option for a listener to say that it has fully processed an event and that it shouldn't be sent to the other listeners.
  • An option for posting delayed events, that should be delivered "in the future".
  • The possibility to block all events of a certain type during the processing of an event.
  • Additional horrors...
So much is wrong here: Global objects with too much responsibility that everything needs to tie into. Forcing all classes into a heavy-handed inheritance structure (no I don't want all my objects to inherit EventPublisher, EventDispatcher, Serializable, GameObject, etc). Strange control flow affecting commands providing spooky "action at a distance" (who blocked my event this time?).

Instead, I believe that the key to a successful event system is to make it as simple and straightforward as possible. You really don't need the "advanced" and "powerful" features. Such complex functionality should be implemented in high-level C or script code, where it can be properly examined, debugged, analyzed, etc. Not in a low level event manager.

Note also that callbacks/delegates cannot completely replace events. While an event will probably generate some kind of callback as the final stage of its processing, we also need to be able to represent the event as an encapsulated data object. That is the only way to store it in a list for example. It is also the only way to pass it from one processing thread to another, which is crucial for a multithreaded engine.

So, with this background, let's look at how events are treated in the BitSquid engine. In the BitSquid engine an event is just a struct:

struct CollisionEvent
{
    Actor *actors[2];
    Vector3 where;
};

An event stream is a blob of binary data consisting of concatenated event structs. Each event struct in the blob is preceded by a header that specifies the event type (an integer uniquely identifying the event) and the size of the event struct:

[header 1][event 1][header 2][event 2] ... [header n][event n]

Since the size of each event is included, an event consumer that processes an event stream can simply skip over the events it doesn't understand or isn't interested in.

There is no global event dispatcher in the engine (globals are bad). Instead each system that can generate events produces its own event stream. So, each frame the physics system (for instance) generates a stream of physics events. A higher level system can extract the event stream and consume the events, taking appropriate actions for each event.

For example, the world manager connects physics events to script callbacks. It consumes the event list from the physics subsystem. For each event, it checks if the involved entity has a script callback mapped for the event type. If it has, the world manager converts the event struct to a Lua table and calls the callback. Otherwise, the event is skipped.

In this way we get the full flexibility and loose coupling of an event system without any of the drawbacks of traditional heavy-weight event systems. The system is completely modular (no global queues or dispatchers) and thread friendly (each thread can produce its own event stream and events can be posted to different threads for processing). It is also very fast, since event streams are just cache-friendly blobs of data that are processed linearly.

7 comments:

  1. I have a similar system, but instead of everyone getting all events like you describe and then ignore those they dont want, I have a subscribe system so only the interesting events are sent to interested objects.

    I've simply used a map of lists in the event manager, mapping event type to a list of subscribers.

    If i understand you correctly, you loop over each event generating capable system to let them send out their events, or is it done completely asynchronous? If the latter, then it sounds harder to reproduce events.
    Does your event system _require_ LUA or similar to manage it?

    /Niklas (datgame on twitter)

    ReplyDelete
  2. No, the events are just processed once. Each low level system has a higher level system that processes its events and acts on them. (You always need a higher level system to connect two low level systems.)

    The high level system could be an event manager with a list of subscribers that events should be posted to, as you describe. But it could also be something else... for example it could have a table specifying sounds to be played for specific events and look up the events in that table. Or a table with script callbacks as described in the blog post. Personally I find a "generic event manager" with a list of "generic event subscribers" to be too "generic" -- it imposes structure and breeds inefficiency without giving any real benefits.

    Event posting in a system is asynchronous. The system just appends events to the blob that represents its event stream. When events are processed at the higher level, we must prevent race conditions in access to the event stream. Either by making sure that the low level system is not running at that time, or by double buffering the event stream.

    No, the system doesn't require Lua. It could just as easy callback into C to process the events. I just wanted to show an example with Lua, since that is the harder case. (Passing the event from C to the script system.)

    ReplyDelete
  3. I don't see how the "bad approach" is conceptually different from yours IF you replace the EventDispatcher is not global or unique.
    Am I missing something ?
    Great technical solution otherwise. A few additional questions yet:
    How do you handle event between systems (perhaps you never need it...) ?
    How do you do if an event need to be dispatched to more than one listener, as it is consumed in the stream ?

    ReplyDelete
  4. Nice post. I've recently implemented a similar system in our engine.

    All the messages for a specific system are stored in a single block of memory.

    I still have a manager though that handles the double buffering and other queue management. Consumers register a callback on a given queue that will recieve a void* + message count when the queue is "flushed" in the top level update loop.

    The queues can be written to by multiple threads/SPUs using an atomic increment on the message count to reserve a spot in the array, and then writing/DMA'ing the message into.

    Haven't had a chance to stress-test the system. The atomic op could become a performance issue, and might have to move to queue per thread.

    ReplyDelete
  5. Clodéric:

    Part of it is a difference in mind set, I guess, my system could be called an EventDispatcher as well, but two concrete differences are:

    1) In the typical "bad approach" events are pushed to the dispatcher rather than pulled by the dispatcher. This means the low level system needs knowledge about the more high level event dispatcher. It can also lead to race conditions if several low level systems push events to the high level dispatcher simultaneously. Also, the logic is harder to follow since events can come to the dispatcher "from anywhere" and "at anytime" instead of being pulled from a specific low level system at a specific time. Also, when the high level system pulls event from a low level system it knows the range of events that that system can generate. When pushing, any type of event may be pushed.

    2) In my system, events are typically (but not necessarily) processed/dispatched by a system that understands the events it is processing. For example, the world manager is at a higher level than the physics system and knows the events it can generate. That means it can do more intelligent processing, such as filter on the actors involved in the collision or the collision force. In the typical "bad approach" the EventDispatcher doesn't know anything about the events it is processing, so it can only filter on type and pass the events along to the system that actually understands them... which is a rather meaningless service and layer of indirection.

    I only talked about "output" events, not "input" events, which is what I guess you mean by "events between system"... an output event in one system becoming an input event to another. In that case you would have a high level system connect the two low level systems (since low level systems don't know about each other). The high level system would know the events that both systems understood and could then do any necessary "translation" between the two systems.

    The high level system that consumes events decides what to do with them. That can involve one or several direct actions... or dispatching them to other systems... so there is no problem having several "listeners"... though I don't really like that term since it comes from the (in my opinion) bad/generic approach.

    ReplyDelete
  6. Nice post, thanks! Just one implementation question: are all your event structs POD types or they have serialize/unserialize methods?

    ReplyDelete