Data Structures – Working with Queues and Games

Queues are really quite a fundamental data structure that all in computing should know. Probably one of the most popular real world examples of a queue in operation is that of a checkout counter in a shop. This is a classical example of First In First Out in operation. The first person to join the queue will be the first to be served at the checkout. All further customers join the back of the queue. Hence is a nice example of enqueue() and dequeue() in operation.

The “Hot Potato” Queue Simulation
Another example that is often used is the “Hot Potato” (online), whereby a person has a “Hot Potato” that gets passed around by “people” in the queue. At each iteration a “person” from will become removed from the queue and placed at the back – therein enqueue(dequeue()). This will occur a certain number of times before the “person” with the “Hot Potato” will be finally removed from the queue. This process continues until just one person remains.

Print Queue
An example more tangibly related to computing is perhaps the “Print Queue”. When a new document is sent for printing it is placed at the end of the queue enqueue(). The process of actually printing off a document will remove it from the queue dequeue(). Under many circumstances this will removed the first print job. However many multi-function printers/photocopiers of today, will present a list of print jobs one screen once you log on, allowing you to select which job or jobs you wish to print. So the example of the “Print Queue” isn’t perhaps the best any more, although even with these multi-function one can often “Select All, Print & Delete” which will print off each job in the “Print Queue” following the standard FIFO ordering.

Waypoints
So what might be a good example of a queue system in operation that would be applicable to students studying Game Development? One nice example is perhaps that of Waypoints, the following (online) link is to an animation that moves an onscreen object towards a location the user has clicked (Waypoint), as the user clicks other locations, these are added to the “Waypoint” queue. When the onscreen object reaches a Waypoint location it is dequeued.

Message Queue
Another nice example is of how to implement a “Message Queue” in a game (online). In this case game avatars can pass messages to one another following a distinct packet/envelope structure, that of: sender, destination, type, data. Therefore instead of having Objects communicating in what could be almost considered as a fully interconnected mesh of messages (just consider what a system sequence diagram for this would be like). All Object / Avatar instances instead communicate with each other through a single queue based messaging system.

Production / Build Queues in Games
One example I considered quite applicable to Game Development students was that of the Production Queue. Many stratagy based games make use of “Production Queues” or “Build Queues” to creating anything from Tanks, and Ships to Aircraft and Experimental Weapons such as the AC1000 from Supreme Commander 2 (online) developed by Gas Powered Games.

The Noah Unit Cannon Experimental (online), is a fixed emplacement that can queue up the production of several types of land units, such as the Rock Head Tank, Titan Assault Bot and the Sharp Shooter Mobile Anti Missile Defense to name but a few.

Simcity Buildit
Simcity Buildit makes very extensive use of Production / Build Queues through the form of Factories that produce basic materials such as Metal, Wood, Plastic, Glass and Electrical Components. These items can take anything from 1 minute for Metal up to 7 hours for Electrical Components to be produced. When fully upgraded these factories have a production queue of 5 units. Materials produced in the Factories can then go on to be used in one or more of the nine Commercial Buildings. The Commercial Buildings take the form of Farmer’s Market, Furniture Store, Hardware Store and Donut Shop to give just a few examples. Details of all the items these factories and buildings can produce can be seen (online) (online). The following videos give some sense of what these building are like.

Given that one can wait almost an entire day to process a full production queue of Beef (11 units) it is very useful to have the opportunity of speeding up the process with “Speedup Tokens” in the form of: Turtle x2, Llama x4 and Cheetah x12. To create “Speedup Tokens” one must either earn them through the “Contest of Mayors” or create them from small pieces by creating “Epic Projects”. These are building that can create a fragment of a “Speedup Token” every 24 hours. The more “Epic Buildings” one has the more fragments are needed to create a “Speedup Token”, however as a starting point one needs 3 fragments for Turtle, 6 for Llama and 9 for Cheetah.

Perhaps tasking Games Development students with creating Production Queues that simulate the creation of Beef, Televisions, Popcorn or Pizza as is the case with Simcity, or Land, Air and Naval units in the case of Supreme Commander is a good way of demonstrating the use and need for queues – particularly in strategy games. Another interesting reason for focusing on Production / Build queues is that especially in the case of Simcity Buildit, many of the items produced are dependent on other items. Therefore quite long chains of production can be formed just to produce the necessary resources to create one “Expensive / Complex” final item.

Parallel Processing / Super-computing
Simcity Buildit provides a really good example of the costs associated with production / processing and relate very well to issues around Parallel Processing / High Performance Computing (HPC) / Super-computing and how jobs can impact one another in the determination of the overall execution time. The classical example of this is the process of making breakfast – many tasks can be done in parallel, though one will be constrained by the cost of the operation that takes the longest. Taking a parallel approach to making “breakfast” can however yield a good deal of cost / time savings over a step by step approach (online).

What other Games use Production Queues?
Do you know of any other games that make heavy use of “Production Queues” / “Build Queues”?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s