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

Examples of Graphics, Animation and Fractals in Film

Vol Libre (1980) created by Loren Carpenter is an extremely well know example of early computer animation. It used fractal terrain generation of create a flythrough of a three dimensional landscape. This would in turn lead on to the development of the Genesis Sequence in Star Trek II the Wrath of Khan (1982) (IMDB).

The following video provides a nice bit of background about fractal terrain generation as described by Loren Carpenter himself. In 1978 he came across the book Fractals Form, Chance and Dimensions by Benoit Mandlebrot and having read the entire book twice started use fractal techniques to develop computer generated terrain.

Another good example of computer generated imagery is the Light Cycle battle from Tron (1982) (IMDB).

Tron Legacy (2010) (IMDB) features an updated Light Cycle battle.

Flight of the Navigator (1986) (IMDB) demonstrates the first use of image mapping the surrounding environment on to a surface. In this case it is mapped on to a Trimaxion Drone ship from Phaelon. It also features some nice scenes whereby the Drone ship morphs from “Class 3” mode to “Class 1” – thereby allowing it to efficiently cut through the Earths atmosphere.

Going back to Fractals – its interesting to see how Fractal Graphics seem to crop up in film’s from time to time such as the Mandelbrot Fractal paint job of a car featured in a desert scene from Transformers Revenge of the Fallen. This can be clearly scene at time index (0:36) in the following video clip.

Fractal techniques were again used to generate the lava spewing forth and landing upon a platform, on which Obi-Wan Kenobi and Anakin Skywalker were engaged in a lightsaber battle, located on the volcanic planet Mustafar in Star Wars Episode III Revenge of the Sith (2005) (IMDB).

Another nice example of fractals being mentioned in a film comes from Star Trek First Contact (1996) (IMDB), whereby the Sovereign Class USS Enterprise NCC1701-E is being taken over by the Borg. The Borg are trying to reroute main control to Engineering where they are based. Upon hearing this Captain Picard asks commander Data to “Lockout the main computer”, after some interaction with a console, Data responds by saying that “I have isolated the main computer with a fractal encryption code, it is highly unlikely the Borg will be able to break it”. Hence as you can see even in the 24th century, fractal techniques still prove to be very useful.

The term “Fractal Zoom” is used to describe the opening screen effect of Limitless (2011) (IMDB). The camera carries out a number of moves in the X, Y, Z planes commencing with a downward looking view onto a city street. One can read some further detail about how the effect was achieved (online).

Industrial Light and Magic (ILM) developed a new Fractal Rendering technique for Lucy (2014) (IMDB). An overview of this may be seen (online) with detail of the work being published at SIGGRAPH. The technique was used to render many of the space travel scenes in the film.

Fractal techniques were also used more recently in Guardians of the Galaxy Vol 2 (2017) (IMDB). The following articles (online) (online) provides a good deal of detail on the use of fractal techniques, particularly in the creation of Ego’s planet. Such techniques may also be seen in other segments of the film.

Wikipedia has a nice list of computer animation in film and television available (online). Do you know of any other interesting examples of computer graphics / animation featured in films.