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..
- 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.
- 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
- 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, Log2(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!
No comments:
Post a Comment