Difference between revisions of "A priority queue based turn scheduling system"

From RogueBasin
Jump to navigation Jump to search
 
Line 2: Line 2:


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

Revision as of 06:44, 13 September 2007

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.