[MUD-Dev] [TECH] Event Queue System

[Jon Leonard]

On Thu, Feb 14, 2002 at 05:02:32PM -0600, the_sage2000 at juno.com wrote:

>  1) Has anyone implemented an event queue system and can give me
>  advise on doing it?

[snip detailed description: queue things to happen in the future
instead of a main game loop touching everything in the MUD, and how
to go about this]

I've seen a great deal of good advice :-), but I didn't see much
discussion on specific data strucutres/algorithms, so I'll point out
that a heap would be a good choice.

Essentially, you don't care about the order of future events
(actions to take on future events) until they're actually ready to
happen, so a partially sorted data structure will suffice.  A heap
winds up having an insertion cost of O(lg(N)) and a removal cost of
O(lg(N)), which is a win over the sorted list with O(N) and O(1),
respectively.

If the insert/dequeue operations are encapsulated, the rest of the
code doesn't need to know how it's stored at all.

As a side note, if you know a great deal of specific information
about when things will be scheduled for (Such as always on second
boundaries, with a limited range of delays), you can get O(1) both
on insert and delete, but this is probably not a profitable
optimization in most cases.

There is an example implementation in DevMUD, comingled with
select() stuff, at
http://www.slimy.com/devmud/prototypes/runnable/proto_8/devmud/select/.

I made a couple of design decisions there that are not universally
applicable:

  1) It is a single threaded design, with the master dispatcher
  spending most of its time sleeping in select(), and using that as
  the timer.  In a multithreaded version, the heap would need to be
  protected with a mutex of some sort, and there'd need to be some
  way to wake up out of the select call if an event is queued newer
  than the time it is currently waiting for.  Maybe some thread
  signalling, or writing to a pipe back into the same process, and
  waking on that.

  2) There isn't any way to cancel outstanding events in it.  I
  intend to add this by passing a pointer to event data and
  nullifying events, because I'm not particularly interested in
  removing events other than by executing them.  Depending on the
  expected operation mix, that could be a bad choice.

Jon Leonard
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev