DeltaClock - simple but extreamly efficient scheduling system

From RogueBasin
Jump to: navigation, search

There are a few articles describing various scheduling systems out there already, but I am going to present a slightly different data structure which has the potential to be extremely efficient, while maintaining elegance and simplicity. It is based off of the idea of a delta clock, which I first encountered years ago in my operating systems class as an undergrad. I'll describe the algorithm at a high level, and then given an example implementation in Python.


Delta Clock


Comparative Runtime

Code Example

class DeltaClock(object):
    class Node(object):
        def __init__(self, delta, link):
   = delta
   = link
   = set()
    def __init__(self):
        self.head = None
        self.nodes = {}
    def schedule(self, event, delta):
        assert event not in self.nodes
        prev, curr = None, self.head
        while curr is not None and delta >
            delta -=
            prev, curr = curr,
        if curr is not None and delta ==
            node = curr
            node = DeltaClock.Node(delta, curr)
            if prev is None:
                self.head = node
       = node
            if curr is not None:
       -= delta

        self.nodes[event] = node
    def advance(self):
        events =
        for event in events:
            del self.nodes[event]
        self.head =
        return events
    def unschedule(self, event):
        del self.nodes[event]


Another problem that can solved using the delta clock is act order. Supposing you put both the player and monsters into the delta clock structure, and that you have a generic actor interface for both player and monster, you may have a problem if on one tick the player happens to come early in the queue, and later on another tick. To the player, this will apparently allow the monster to occasionally take extra turns, and occasionally allow the player to take extra turns, which can be disorienting. A simple solution to this is to schedule the player at a fractional offset. If you schedule the player initially at .5 ticks, and monsters at 1 tick, and then have every actor be scheduled in whole tick increments, the player will always be in an event without any monsters, meaning that no one will ever apparently lose a turn.

Personal tools