hi all...
i am currently broadening my C++ knowledge by researching data structures, which is a topic that was not even mentioned in my programming course at TAFE...[?]
i was just wondering what linked lists, binary trees and other data structures are commonly used for in games?
an area of games where the use of data structures is very important is in organising the geometry of the game universe in some sort of spatial data structure (by spatial data structure, i mean a data structure that conceptually splits the game universe into discreet parts).
an example of a spatial data structure used quite often is a BSP (Binary Space Partition) tree, this is basically a normal binary tree but as the name suggests, a bsp tree is derived by recursively dividing the world into two.
for example, we start off with the first node;
0
the first node encloses the geometry of the whole game universe.
we can then partition the game universe, so now we have
0
/ 0 0
where the two nodes in the next level represent two halves of the game universe, we can subdivide further getting;
0
/ 0 0
/ / 0 0 0 0
where the nodes in the next level are the halves of the halves of the game universe and so on.
anyway, by doing this, we have now divided the geometry of the game world into lots of different nodes.
why wouold we want to do this you ask?
well basically, by using a spatial data structure to organise the geometry of the game, we can accelerate many queries about the geometry in the game universe.
for example, we want to find whether two pieces of geometry overlap (for example a rocket and a baddie, if say you fired a rocket at a baddie), instead of doing a collision test between the rocket and every single baddie in the whole game, we can traverse the binary tree, looking for the node that contains the rocket. now, we only have to do a colliison test between the baddies that are in the same node as the rocket. (thus greatly increasing the speed of the game engine)
this is a pretty basic explanation of BSP trees, but thats the gist of it.
I hope i've made some sense here
[:)]
For general info check out the Dictionary of Algorithms and Data Structures: http://www.nist.gov/dads/
Also, you might want to read the STL container docs, they will explain the pros and cons of each in great detail: www.sgi.com/tech/stl
Basically lists are used for objects that have short life-spans, eg a list off all the characters in a game, or the lists of particles in the particle system.
Trees are used when you need to search for something, such as a tachyon has described, but can be used for other things like NPC chatter in a RPG game (a tree of choices).
Hash tables/maps are used to map one thing to another, with an emphasis on fast searching. eg player name -> player stats
Lists and trees of all types are used in games, it's necessary to have some Vector / Dynamic Array, and Linked List class at a minimum. Its very useful to know all the data structures since then you know the trade-offs and peculiarities of each data structure.
For example: Arrays are useful for storing smaller values that are acessed often but not removed often. Linked Lists are good for when large nubmers of items are added / removed, Hash tables are most useful for when fast finding of items is necessary etc.