Introduction to the Event Scheduler
What does it mean that a mud is event-queue driven, why should one want to have a mud that is event-driven and how would one go around changing a DIKU based mud, so it uses an eventqueue? These are some of the questions we are going to try and answer in this text.
First, let me point out that this is not a snippet, nor is it a foolproof set of instructions for implementing an event-queue. Rather it is an example on how I would go around doing it, with bits of code thrown in here and there, I'll leave most of the coding details to yourself for several reasons, most importantly that you should create an event queue that fits your needs best, and not some stock version that may or may not solve your problems.
Brian Graversen, february 2002
What is an event queue (mud style)?
It is basicly a queue of events scheduled to go of at some time in the future. A DIKU mud normally runs in pulses, 4 each second, and each pulse the mud would check the queue to see if any events are ready to be executed. A simple example which, we will use again and again, is autosaving of players pfiles; let's say we want to make sure a player is automaticly saved every 2 minutes, to go about this using an event queue, we would simply add an event to the queue, which contained a set of instructions about the player, and what to do with him; we also tell the event that it should reschedule itself after it triggers. The event would be set to execute 2 minutes from the time we entered it into the queue. Then two minutes later, the queue spits out the saving event, and executes it. Since we told the event to requeue itself when it executes, the event will also create a new save event for that player, and schedule it to execute in 2 minutes. This way, the player will automaticly save himself every 2 minutes, over and over.
The above example is simple, and doesn't show the full potential of event queues, but it does give a good example on how to avoid some of the CPU hogging update functions. If your mud normally has an autosaving feature, it probably loops through all the mobiles on the mud, finding the player that was saved last, and saves him (at least this is the standard way on godwars). Is there really any need to loop through every single mobile on the mud to save one player?? I think not! This goes for all such update functions, what about healing, why do we need to loop through the 90% of the muds population that isn't even hurt, just to heal the 10% that are, every 5-10 seconds? This can also be done with events; let's say a mobile get's hurt, and isn't currently healing itself (we check to see if the mobile has a healing event scheduled), we simply add a healing event to trigger in a few seconds. The healing event will keep rescheduling itself, untill the mobile if fully healed.
Of course, events can also be used for mobprograms and player commands. Let's say you want to create a more realistic magic system, where players starts casting spells, and a few seconds later, the spell occours - simply schedule the spell to go off in a few seconds. You can event link a set of events to go off, one after each other, or what about deathtraps that players have a few seconds to try and avoid?
As I've hinted above, an event queue can drasticly reduce the time spend in some of the heavier update functions, for instance the aggro update, that scans every single mobile on the mud each pulse, seeing if it wants to attack someone in it's room. One basic way to go about this would be to schedule an aggro_check event in a room whenever a player enters it, since events aren't checked untill all mobiles have moved, we don't have to worry about the aggressive mobile always attacking the first that enters the room. An aggro_check event would be linked to the room itself, which would then check all mobiles in that room when it triggers, we drasticly cut down on aggro checks, without losing any realism.
Ok, I'm sold, how do I do this?
First thing to do, is decide how much information an event needs to store. At the very least, the event needs to know who owns it (a mobile, an item, a room, etc). It also needs to know what kind of event it is, and most likely, what function it needs to call when it triggers. It also needs to be part of two lists; a local list attached to the owner of the event (so we can remove all events for the owner, should it/he/she be destroyed or quit), as well as a global list, which is attached to the event queue itself. Below is an example of an event structure
struct event_data
{
EVENT_DATA * next_global; /* next event in this hash bucket */
EVENT_DATA * next_local; /* next event for owner */
EVENT_FUN * fun; /* the function being called */
char * argument; /* the text argument given (if any) */
sh_int passes; /* time before this event executes */
sh_int type; /* event type ETYPE_XXX */
sh_int bucket; /* which bucket is this event in */
union /* */
{ /* this is the owner of the event */
CHAR_DATA * ch; /* a union to make sure any of the */
OBJ_DATA * obj; /* types can be used for an event. */
ROOM_INDEX_DATA * sublocation; /* */
} owner;
union /* */
{ /* this is the target of the event, */
CHAR_DATA * victim; /* if more targets are needed, we */
OBJ_DATA * obj; /* can hide it in 'argument'. */
ROOM_INDEX_DATA * sublocation; /* */
} target;
};
Of course, we need to add an EVENT_DATA entry into the obj_data, char_data and room_index_data structures, so they know which events they own.
Now let's make the event queue. The simplest and most effective way that comes to mind, is an array of linked lists, each entry in the array will be refered to as a bucket from this point on. Let's say we have 64 buckets (it may be wise to increase this number, should your mud use exceptionally many events). Consider this, if we want an event to trigger in 8 pulses, we sould simply put it in the queue 8 buckets from where we stand in this pulse. Now all we have to do, is check the next bucket in the queue each pulse, and when we run out of buckets, we start over. Should we need to schedule an event to execute later than our 64 buckets, we would just wrap it around, and use event->passes to keep track of how many times we need to run through all the buckets before this event triggers.
/* The eventqueue could very likely be kept as something local, if * you keep all the event enqueing/dequeing/checking functions in * the same place. If not, just make it global :) */ extern EVENT_DATA *eventqueue[64];
Know we need some support functions to handle our events, the most vital ones seems to be functions that allows us to enqueue and dequeue events to and from the event queue. The dequeue() should probably also strip the event from the owner of the event (if any), where enqueue() should just put the event in the global queue.
/* enqueue_event() should take an event and an integer as arguements, * using the integer to calculate in what bucket to place the event, * and how many passes the event should be ignored (if any). * * The function should return TRUE on a succesful enqueue. */ bool enqueue_event ( EVENT_DATA *event, int game_pulses ); /* dequeue_event() should simply remove the event from the eventqueue, * and free any memory associated with the event. If some sort of * memory sharing/recycling is used, then it should also take this * into consideration. */ void dequeue_event ( EVENT_DATA *event );
Now we are able to add and remove events from the queue, so the next thing to do, would be the heartbeat function, that runs through one bucket each pulse. If we assume that an event function returns TRUE if it dequeues() the event itself (if the event causes the owner of the event to be extracted/destroyed, and thus removing all events on the owner, including this one), the following heartbeat function could be used. It should be called once every pulse (from game_loop_unix()).
void heartbeat()
{
EVENT_DATA *event;
/*
* current_bucket should be global, it is also used in enqueue_event
* to figure out what bucket to place the new event in.
*/
current_bucket = (current_bucket + 1) % 64;
for (event = eventqueue[current_bucket]; event; event = pEventNext)
{
/*
* pEventNext is also global, should an event cause other
* events to be dequeued, it is vital that we known which
* event is actually next. Remember to update this pointer in
* dequeue_event().
*/
pEventNext = event->next_global;
/*
* Here we use the event->passes integer, to keep track of
* how many times we have ignored this event.
*/
if (event->passes-- > 0) continue;
/*
* execute event and extract if needed. We assume that all
* event functions are of the following prototype
*
* bool event_function args (( EVENT_DATA *event ));
*/
if (!((*event->fun)(event)))
dequeue_event(event);
}
}
Now you need to make sure everything runs smoothly, and that events are freed when needed. I'll end this story with an example of the autosaving event, which reschedules itself every 2 minutes. This bit of code was taken from my own mud, so it might not look so DIKU'ish. Ok, changed the code a bit, so it looks like a DIKU event.
bool event_mobile_save(EVENT_DATA *event)
{
EVENT_DATA *newevent;
CHAR_DATA *ch;
if ((ch = event->owner.ch) == NULL)
{
bug("event_mobile_save: no owner.");
return FALSE;
}
/* save the player */
save_player(ch);
/* schedule new save event */
newevent = alloc_event();
newevent->owner.ch = ch;
newevent->fun = &event_mobile_save;
newevent->type = EVENT_PLAYER_SAVE;
LINK_LOCAL(newevent, ch->event_first, ch->event_last);
/* enqueue to execute in 2 minutes */
enqueue_event(newevent, 2 * 60 * PULSE_PER_SECOND);
/* we didn't dequeue the old save event, so we return FALSE */
return FALSE;
}
You may want to add more support functions, for instance I have one that starts a set of events running on a new mobile when it enters the game. Also remember, this is in no way the only way to do this, you should always experiment and tweak, you may end up with something even better.