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

Shader Driven Rendering Demos

The following videos are from the work carried out by one of my Honours Project students this past academic year. One can follow this link to read some further detail about it. One may access a playlist of all the videos below on YouTube. The engine consists of over 55,000 lines of code spread across almost 80 classes.

A rewrite of the NVIDIA SDK Island demo using the XPR Python library and the original NVIDIA media resources.

A rewrite of the NVIDIA SDK Ocean demo as an extension of XPR which uses the inbuilt Compute Shader pipeline along with the original NVIDIA media resources.

XPR Python based rewrite of the NVIDIA SDK Terrain demo. Uses the XPR engine’s mesh generators, resource management system, multipass framework and inbuilt tessellation pipeline.

A demo that showcases XPR native instancing and geometry shader driven particles using the textures and animation logic from the Microsoft SDK Particle sample.

An optimised, procedural representation of the Menger Sponge fractal using the XPR engine’s inbuilt pipeline. The demo supports up to 7 recursive subdivisions of the original cube and can animate each resulting cube individually.

A demonstration of hardware instancing as supported by the XPR engine. This sample renders 125.000 boxes using only one model with multiple positions.

A rewrite of an old Microsoft SDK demo using new completely shader-driven methods. Uses XPR multipass and post-processing features to showcase HDR.

An XPR engine demo that demonstrates how to override pipeline bindings in order to create and animate custom fractal shaders. In this case the fractals represented are Mandelbrot and Julia set.

An XPR engine demo that loads a series of meshes that form a car from an FBX file.