Archived

This topic is now archived and is closed to further replies.

OpenGL Game Programming and BST's

This topic is 5147 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

In OpenGL Game Programming they ("they" being Dave and Kevin afaik) use a cool little class that is used to store the game objects. This class is basically a node in a tree of linked lists, creating a nice heirarchy that looks something like this:
NODE  -------> NODE -----------------> Node
 \|/            \|/                    \|/
Node -> node    Node -> Node -> node   Node
 \|/                    \|/
node -> node -> node    node -> node -> node -> node  
and so on. I'm using that same class in my game, but I want to add to it. I want every individual object in the game to have it's own string identifier, like "grenade 001". So I added a small string to the class. But since it'll be searching linked lists for a specific string every time it has to look one up, that'll be kind of slow. So I decided I'd add to the class and build a BST on top of the linked list for quicker searching. BTW, I only want to search one level at a time, not the whole tree. I've never really worked with BST's before, and my first attemp isn't going very well. Has anyone ever done something like this before? Perhaps even with the OpenGL Game Programming node class?? Any advice? Help? [edited by - BradDaBug on November 9, 2003 8:36:05 PM]

Share this post


Link to post
Share on other sites
So the problem is really "How to implement a binary search tree" ?

You can use std::map<std::string,node*> to map from a string to a node pointer. That may be sufficient for your needs. Just don''t forget to keep the map in sync with your tree.

However, do you really need the sorted feature you get from a BST or a std::map? If not, I suggest a hash table. Or, if your standard library has it, a std::hash_map.

Share this post


Link to post
Share on other sites