A priority queue based turn scheduling system

A priority queue based turn scheduling system

This is an implementation in Python of a turn scheduling system that uses a priority queue. Events include monster and player actions, and therefore is able to represent the relative speed of different creatures.

The theory

When creatures take turns in a roguelike, sometimes it is desireable to have faster creatures to receive more turns relative to other creatures. For example, the player may take two turns for every one turn the giant slug makes, while the player is outrun by the bat who takes three turns for every turn the player makes.

To achieve this effect, a creatures speed is thought of giving it a delay between its actions. When a creature take a turn, there is some delay until it may act again. Faster creatures may have turns between this delay. The turn delay is shorter for faster creatures. Referring to the last example, the player would have twice the speed as the giant slug, and therefore receives half the delay between his or her turns.

These delays are handled by using a priority queue and keeping track of the current game time. When the game starts, the game time is set to zero and all creatures on a level (including the player) are inserted into the priority queue with a priority of zero. The priorities in the queue actually represent the time when the creature will act.

To execute a turn, a creature is pulled off the queue. If the priority the creature had in the queue is greater than the current game time, the game time is set to the priority, representing the passage of time. After the creature takes its action, it is placed back into the queue with a priority equal to the sum of the game time and the creature's delay.

The priority queue

Of course, first we need our priority queue.

import bisect

class PriorityQueue:
    """
        Taken from http://aspn.activestate.com/ASPN/Cookbook/Python/
          Recipe/68435.
    """

    def __init__(self):
        self.__queue = []

    def enqueue(self, value, priority = 0.0):
        """
            Append a new element to the queue
            according to its priority.
        """

        bisect.insort(self.__queue, (priority, value))

    def dequeue(self):
        """
            Pop the value with the lowest priority.
        """

        return self.__queue.pop(0)[1]

    def dequeueWithKey(self):
        """
            Pop the (priority, value) tuple with the lowest priority.
        """

        return self.__queue.pop(0)

    def erase(self, value):
        """
            Removes an element from the queue by value.
        """

        self.__erase(value, lambda a, b: a == b)

    def erase_ref(self, value):
        """
            Removes an element from the queue by reference.
        """

        self.__erase(value, lambda a, b: a is b)

    def __erase(self, value, test):
        """
            All tupples t are removed from the queue
            if test(t[1], value) evaluates to True.
        """

        i = 0
        while i < len(self.__queue):
            if test(self.__queue[i][1], value):
                del self.__queue[i]
            else:
                i += 1