Relative Priority Queue

Games that choose lines of speech “randomly” from a set usually don't want true randomness. They want to be sure that the same line isn't chosen twice in a row, or perhaps for an even longer period.

For my game I opted for the simplest solution first. I just keep an iterator into each line set and run through the lines in order, wrapping back to the start after I've used all of them. I doubt anyone will notice that the lines are used in the same order, since I have lots of different line sets that come into play during gameplay.

I couldn't help thinking about more complicated solutions to the problem, though. What if you have some lines that are so memorable you don't want them to reappear for a long time after they've been used? Other, simpler lines could be reused more frequently without sounding dumb.

One way to do this would be to assign to each line a “timeout”; a duration before it can be used again. The line with the lowest timeout is the next to be used. After using it you'd reset its timeout value and decrement all the rest.

This is sort of like a regular priority queue, except that you really don't want to have to decrement priorities on all the entries every time you extract something.

I was thinking that you could implement a relative priority queue as a binary heap where each element stores its priority relative to its parent rather than a global priority value. For instance, here's a standard priority queue containing absolute priority values:



The relative representation of the same priorities would be:



The usual binary-heap-based queue algorithms should work with only small modifications to take into account the relative nature of the priority values. Here's extraction of the lowest-value element. The end element is swapped into the first position:



Then additional swaps are made to ensure that parent nodes have lower values than any of their children:



Relative priority queues could also be useful if you've got timer events in a game that are set to go off at times in the future. Some (shipped!) games I've worked on used absolute times for everything; they run into problems if you let them run continuously for too long. Dealing in relative times lets your game run in a kiosk at Best Buy for days on end.