Delta Clock Scheduler

This article presents a simple data structure for scheduling which has the potential to be extremely efficient, while maintaining elegance and simplicity. It is based of the idea of a delta clock, which I first encountered years ago in my operating systems class as an undergrad.

Suppose you have a set of events which you want to resolve at certain times. You could just store these events in a list, along with the intended times like this:

The problem is that in order to find all the events you want for the current time interval, you have to iterate through the entire list. Updating the list to advance in time also requires iterating through the whole list. Of course for many roguelikes, O(n) for a scheduler is perfectly acceptable. However, for games like Sticks and Stones, we’ll need to do a bit better. Instead, we’ll store our events like this:

Each event is stored with a delta between it and the previous event. In our example, Event1 is scheduled to fire in 5+15 ticks, while Event6 is scheduled for 5+15+2 ticks. Adding an event to this list is simply a matter of iterating through the list once, decrementing as we go. To advance in time, we simply decrement (or pop) the first item in the list.

Of course in the worst case scenario, our run time for adding an event to the delta clock is still O(n), where n is the number of events. However, at least in Sticks and Stones, a large number of the events (typically a creature move event) all fire simultaneously. By combining simultaneous events into a single node in our list, adding a new event gives us a run time which is O(t), were t is the number of unique deltas.

The implementation is pretty simple too! Here is some code:

type Event interface {
  Fire()
}

type deltanode struct {
  delta int
  link *deltanode
  events []Event
}

type DeltaClock struct {
  head *deltanode
}

func (c *DeltaClock) Schedule(e Event, delta int) {
  var prev, curr *deltanode = nil, c.head
  for curr != nil && delta > curr.delta {
    delta -= curr.delta
    prev, curr = curr, curr.link
  }

  var node *deltanode
  if curr != nil && delta == curr.delta {
    node = curr
  } else {
    node = &deltanode{delta, curr, make([]Event)}
    if prev == nil {
      c.head = node
    } else {
      prev.link = node
    }
    if curr != nil {
      curr.delta -= delta
    }
  }

  node.events = append(node.events, e)
}

func (c *DeltaClock) Advance() []Event {
  if c.head == nil {
    return nil
  }

  events := c.head.events
  c.head = c.head.link
  return events
}

That is really it! There are two additional features that you’ll find inside the GoRL implementation of the delta clock. First, I added the ability to unschedule an event. This was done by having the delta clock store a mapping of every event to its node so I can easily find it later and remove it. Second, GoRL gives deltas as floating point numbers, with the integer part representing the actual delta, and the fractional part used to determine the order in which events should fire.