07 September 2012

Event managers and MVC - part 2

I wrote about MVC and event managers in January. Here's more!

Ordering of tick events in the game loop

A traditional game loop follows roughly this pattern:

  • process inputs on model (keyboard, mouse, network rcv)
  • process tick on model (update each entity and the world)
  • tick the renderers (graphics, sound, network send)
  • eventually wait for next frame, and repeat

Problem: Let's start with a simple event manager that does not make any difference between the inputs, models, or renderers. In other words, the event manager has no clue about MVC. Then, two annoying things happen. First, and most importantly, the event manager could publish a tick event generated by the clock to the model first, to the controllers second, and to the views last. It's as if we were running a different loop: tick the model, process inputs, and render. Since inputs need a whole frame to be processed on the model, the controls may feel laggy to the player (33ms lag at 30 FPS). This is terrible in twitch games like FPS or fighting games. Second, the dispatching of events could be non-deterministic: in one frame, controllers are ticked first, while in another, models are ticked first. The lag to process player commands would be random, and they may not be able to adapt to it.

Solution: We need an event manager that follows the game loop described above. Poll the controllers first, and send the events they generate right away on the model, views, or other controllers that subscribed to those events. Then tick the model and publish any resulting events right away. And finally, send the tick event to the views.

Implementation: the original simple event manager had a dictionary mapping each event type to a list of callbacks. The simple event manager was not differentiating between tick events and other events. Now, we need to distinguish between tick and non-tick events. And for tick events, we must distinguish between controllers, models, and views. This results in a set of controller callbacks, another set of model callbacks, and a third set of view callbacks for the tick events, and the usual dictionary mapping each non-tick event type to a list of callbacks.

Events that generate new subscribers

Problem: We're sending a tick event to the model. The model happens to create a new creature in the game. Let's say that the data of this creature needs to be updated every simulation step, so it should subscribe to the tick event as a model. However, the event manager is currently iterating on the set of model entities currently subscribed to be ticked. And in Python, when a set is iterated on, it can not be modified. I'm also guessing that lockless sets do not belong to the standard library of most programming languages, so this problem may not be unique to Python.

Solution 1: Before starting to process the tick event on the models, make an empty set. This set will store the callbacks of each model entity that started to subscribe to the tick event during this current frame. So we call this set new_callbacks. Our newly-created creature will be put in that set by the event manager when it subscribes to the tick event. When the event manager has finished iterating on the usual set of model entities, it makes a copy of new_callbacks, and replaces new_callbacks by an empty set. Then, the event manager iterates on the copy set, ie our new creature. If the creature spawns 3 minions at the first tick of its existence, the event manager will store the 3 callbacks from the minions in new_callbacks. Then, when the event manager is done with processing the copy, it adds the copy's callbacks to the usual set. Then, it replaces the copy by new_callbacks, and ticks the 3 minions. This can go on until both new_callbacks and the copy set are empty. Then, all old and new models have been ticked. Below is the output I'm expecting:

Created controller
Created model
Created view
---- Clock tick 0
Ticked controller
Ticked model
Created boss
Ticked boss
Created minion
Ticked view

The code does not exactly output this: the view is ticked before the boss is created. Oh well ... :-)


Solution 2: Solution 1 involves 3 sets and is quite convoluted, but there is simpler (and more dangerous!): using a data structure that is not locked when iterated on. In Python, this means using a list instead of a set. However, it's not the perfect data structure for the job: if an entity happens to subscribe twice to an event, the entity will receive the event twice. Most likely, your entities only need to be ticked once per frame, so if a bug causes an entity to act twice faster than expected, you'll know where it might come from. That's why modifying a list while iterating over it is not recommended.