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

Option #1: Polling

I would probably build a controller that can discover the delay for all the different entities and maintain a ticks-remaining for each entity. The controller would cycle through ticks and on each tick it would reduce the ticks-remaining for all entities in the game.

Once an entities ticks-remaining value reaches zero you know it's their turn, either controlled by the heartbeat method that handles the ticks or a method that you call.

Option #2 Events

Think like the UI paradigm, the interface doesn't constantly poll the button to see when it is clicked. Rather it let's the button notify the UI when it has been clicked via events. Have your Entities (or an EntityBattleContext) fire an event when it is ready. You will have to handle you game time in some manner, since it isn't based off real world time at all you may need to have all the Entities listen for a GameTick event and when they receiver that event update their interal TicksRemaining variable.

Before following the event driven route make sure the polling route won't work. Remember the cardinal rule always optimize later because more often then not you don't need the optimization.

Answer 2

If we assume your entities are observing or watching the simulation time, they could each implement an interface which makes them track the ticks left and provides a method to get how many ticks are left for a particular entity. At each tick, the entity reduces its ticks left by 1.

You could then keep a sorted set queue (set because each entity will be in the queue only once) of these entities, sorted based on get ticks left, so that the 0th entity is the one to move next, and the Nth entity is the "slowest".

When the entity's get ticks left method is 0, it is removed from the sorted set, the ticks left timer is reset, and it is re-inserted into the sorted set.

Answer 3

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?".

Answer 4

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 5

Look at how Java's DelayQueue is implemented.