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.

A Nod(e) To Data structures!

Data Structures!

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. For this blog, you can give a nod(e) for using these data types for many simple things.

Graphs

A graph is a really abstract data type, which could represent the mathematical graph, or a tree data type. Basically there will be a start node, a root node, and it will have a “child node”. The root node will be a parent which has access to their “children”, so does the children to their children, and so forth. Each parent can have any number children, and you can keep traversing the graph as long as the parent has a child .

The special part about graphs is that these paths can have weights applied to them. These weights are special numbers which can be used to help influence the path which the user takes. Increase the number, and it could act like erecting road block, while decreasing the number could create a short cut. This could also be used for other variables, such as costs, distance, or time.

Uses for my Game

 AI- For AI, there are many application for it, from path finding to giving a more dynamic feel for the A.I..

1. First, the A.I. could use A* for path finding to the player easier, with the help of a graph. Each graph node can be used to represent the tiles, set a square of specific size in game. 
2.  Second the graph can use the help of weights, which can be applied to a tile if there an object on it, or if it has a special attribute which will affect the A.I.. These weights can also be used to affect the AI depending on its state of it. For example the AI may take the longer path if it is feeling confident with more health, or the shorter path if it has left health
3. Finally, a more advanced AI could use this to help in coordination so that an AI could be attacked on multiple fronts. This could be done increasing weights on tiles based on how many A.I.s are taking that path, since they are all going for 1 player. This way the AI will be forced to take the long route to the player, flanking him while he is being assaulted from the front.

A Tree

A tree is a quite simply a set of nodes, with an implicit hierarchy, where one node will contain some number of “children”. Like a graph there will be a parent has access to their “children”, the difference is that here, we like to limit the number of children that each parent has. Not only does it save space, but it also gives numerous other advantages to each tree. A tree of this kind can be defined by the number of children it has, for example a binary tree which has only 2 children is a binary tree, while a quad tree will have 4 children. With this, the equation for the searching through the tree would be, Log_{2(or how many children the tree has)}n, which is VERY EFFICIENT!

Before delving deeper into the advantages of the different types of trees, the major disadvantage of trees is their organization in tree form. When dealing with trees, you may organize data by the value of a specific variable. However this could result in an unbalanced tree, having a lot of nodes on one side of the tree, while the other side remains empty. Balancing this out involves a secondary process, which be something like an AVL tree, that could be computationally more expensive.

Binary Tree

As its name suggests, the binary tree’s parent will only have 2 children, and so forth. Binary trees are good for organization data and allocating memory, due to the fact you would be defining the size of the list before putting the elements. The limitation is the fact it would have to be of number that is a power of 2, due to fact you are going down a level in hierarchy. With this limitation, the data will know that the 2 next elements (after all the children on the same level) will be children of this node.

One disadvantage is if the list size is just 1 bigger than the allocated size, meaning you now have to allocate twice the memory for the data. For example if you had a list of size 8, but you have 9 elements, you now have to allocate 8 more slots of your list in memory for that extra slot.

Uses for my game- 

I can use the binary tree for storing a specific number of objects, objects which I may wish to continuously look for. This could range from the Enemies, to the bullets.

Quad Tree

In my other blog I will talk about something called voxels, which could be used for many 3d applications. One of these applications is representing terrain in using voxels, which as we learned could be computationally expensive . 

However as we discussed in class, using quad trees for terrain would be “a step up”. The reason why this would be a step-up is that this would be a more accurate representation of something, such as a flat plain. The reason is that we would subdivide the plain into only 4 sectors (quadrants), and continue to subdivide the sector if there was an imperfection in the terrain. This way, we will only need store a location if it has an imperfection, rather than having the make storage space for every single tile.

As a tree, its advantage would be the shorted searching time due to the efficient organization of the data structure. This could allow for something like collision detection to be used with using the graph, on a per level basis. Simply we can use the character position and compare its location in the graph to determine if it is inside terrain or not.  The limitation though would be that the terrain could only be represented in a 2D grid

Oct tree

Using the example from above, you wonder how can we adapt it for a 3D grid, the answer is using an oct tree. With an oct tree, as shown with the diagram below, we can represent the world easily with the concepts of a quad tree in 3d.

 Thats all for now, stay tune for the next blog where I will talk about stacks, queues, and voxels!

Mike Acton: OOP is bad

This is a summary of my class learning about why OOP is bad based on Mike Acton’s work. Mike Acton very experienced engine programmer and has been in the game industry for over 22 years. He specializes in engine programming and has worked with sony’s consoles ever since PS1 and helped discover secrets of cell on ps3. Currently resides at insomniac game, and has been programming for their engine for the past 6 years. He has done over a dozen publications about improving programming and recently done a lot of done key notes.

What I got from the lecture

The first point is that if statements are bad due to their branching of code. It is ok if you execute the statement which satisfies the if statement. However when you choose to execute another branch of the statement, you waste more time. That is because rather stepping over to the next point in memory; you would jump to another place. Like in real life you would rather travel in a local area, rather than wasting time going to the airport and flying around! 

Class are bad, even though they help us see better, in the end it is the computer which processes the code. Normally in class there is everything from matrices, to pointers, and other inherited classes. However the computer sees a huge mess of different objects being sent in at once. Each time it encounters a new variable or object, the computer will spend time trying to alocate memory for it, wasting precious computing time.  We should group like objects together and send them through as a stack. This is what computers, specifically SPUs (synergetic processing unit) are made for, and handling huge stacks of work at once. This is why we should move towards a data orient programming for some areas of programming.