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!