Data Structures- Queues,Stacks,Voxels

As its name suggests data structures are different ways which we organize data for our game.  There are many ways data structures which we can use in our game, ranging from the simple stack, to the more advanced voxel. For every Data structure, they each have strength and weakness, giving them situations which they are each suited for. This is part 2 of my Data structure blog, for part 1 click here

Queue

Quite simply- First in, first out This works just like a real life queue, where the person who enters first will get served first.

Uses for my game- Updating objects (positions, animations, physics). We use the priority queue to give to processes, such as animation, or specific objects, such as the player, first priority. If wanted the AI to be more advance, I can request it to queue up a bunch of commands to execute.

Stack

Quite simply- First in, last out. When dealing with stacks, imagine making and eating a stack of pancakes. The first pancake you make will go to the bottom, and when start eating, you’ll start from the top of the stack.

            Uses for my Game- In game stacks have many uses, from editors, to path finding, and finally for matrix multiplication. If we had a level editor, we could use stacks here to undo and redo recent changes which the user just did. If I used A* for my path finding, stacks can work for representing the neighboring nodes, rather than a graph. Finally if I were to use matrix multiplication, I would have to use stacks to make sure the multiplication is done in the right order. This would be done if I wanted to do something, like convert from model view, to what is actually being seen, for many reasons.

Voxels

These are an interesting data structure, and have many uses but they aren’t a new subject to me. My interest about it lead me to write a blog about Voxels and their use in Command and Conquer: Tiberian Sun, which you can visit here.  

If you don’t want to go there, a voxel is basically a shorted name for Volumetric Element. It is a setup from its 2D counterpart, the Pixel :Picture Element,and contains data in a 3d space. It can contain any form of data throughout it, from a simple Boolean value; to a RGB value. This way you can represent a 3D model, with an actual volume for each of its sides.

This makes it a great way for solving many 3D related real life problems. One problem is if we wanted to print a virtual 3D object in real life, we could turn it into a voxel. 3D printers like voxels because they go through the object, level by level, starting at the bottom. Another would be for the field of medicine, as they are great for CT scans. In CT scans, values stored in voxels are based on the opacity of material to X-rays. Since voxels can contain multiple scalar values ; in ultrasound scans with density and volumetric flow data are captured as separate channels of data relating each voxel in the data structure. With this doctors can visualize scans of the patient’s organs in 3d and help identify any anomalies within.  

In games voxels play major role, though none could probably be implemented in my game. The CryEngine 2 and 3, uses a combination of height maps and voxels to generate its terrain. This is because height maps cannot represent the interiors of caves or a concave object, so voxels must be used. With the popularity of minecraft, and resurgence retro styled games there have been many recent games which have had a voxel like world.  3D Dot Game Hero, Castle Story, Block Ops, and Cube are just a few of these games. Finally, the Unreal engine 4 uses real-time global illumination with full secondary lighting and specular reflections with voxel ray casting.

           

As you can deduce, the major problem with voxels will be their size in memory, due to their bulkiness. With a simple voxel cube of 128, each holding 4 byte of data(which is just small number value) , the voxel will be 8 million bytes! With this you can reduce it by storing only smaller memory values, such as Booleans. However there have recent advancements in voxels which have compressed the size of each voxel.