Which data structure(s) to back a Final Fantasy ATB-style queue? (a delay queue)

Question

Situation: There are several entities in a simulated environment, which has an artificial notion of time called "ticks", which has no link to real time. Each entity takes it in turns to move, but some are faster than others. This is expressed by a delay, in ticks. So entity A might have a delay of 10, and B 25. In this case the turn order would go:

A A B A A

I'm wondering what data structure to use. At first I automatically thought "priority queue" but the delays are relative to "current time" which complicates matters. Also, there will be entities with larger delays and it's not unforseeable that the program will run through millions of ticks. It seems silly for an internal counter to be building higher and higher when the delays themselves stay relatively small and don't increase.

So how would you solve this?

Answer 1

You store the entities in a Heap and group them by their time left to wait. The group of entities that are next to move would be at the top of the Heap. You only have to update these entities. When their time remaining to wait drops to 0, you remove them from the heap. Put the next group of entities in line at the top of the Heap while decrementing their time to wait by the amount of time that just passed before the previous move.

For example:

Your Heap has 3 nodes (A,B, and C), the top is node A with two entities both having 5 ticks remaining. The childern have 10 and 12 ticks remaining respectively.

• At time t=5 you move all the entities that are bucketed in node A
• Remove A from the Heap
• B moves to the top of the Heap with 10-5 = 5 ticks remaining then
• repeat.

Answer 2

It seems to me by your description that the concept of "what's next?" is more important than "how long is it until the next action?". This being the case, sort your queue by "next-to-go" or lowest number of ticks remaining to highest. Inserts, of course, get entered in their appropriate order, and altered entries ("Speed up" spells) get removed trom the queue, altered, and then re-entered appropriately.

Then, you just pop the next job off the queue. Whatever number of ticks it had remaining must be the "time-elapsed". Makes a pass over the queue, decrementing the ticks remaining field of each entry by the amount of ticks you just discovered.

This has the advantage of keeping track of the concept of time remaining, but also of not having to fire events or execute any other code for ticks that go by when there is no action to take. You can afford this, since there is no relation to real time at all. There is only "what's next?", and "How long did it take to get there?".