# DeltaClock - simple but extreamly efficient scheduling system

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

## Code Example

```class DeltaClock(object):

class Node(object):
self.delta = delta
self.events = set()

def __init__(self):
self.nodes = {}

def schedule(self, event, delta):
assert event not in self.nodes

while curr is not None and delta > curr.delta:
delta -= curr.delta

if curr is not None and delta == curr.delta:
node = curr
else:
node = DeltaClock.Node(delta, curr)
if prev is None:
else:
if curr is not None:
curr.delta -= delta

self.nodes[event] = node

for event in events:
del self.nodes[event]
return events

def unschedule(self, event):
self.nodes[event].events.remove(event)
del self.nodes[event]```

## Extras

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.