I'm currently working on a rendering system for my new game. The rendering engine relies on my base object which is a node class that only has the members CNode *m_pParent and vector<CNode *> m_pChildren. Because this is going to be used for rendering (as well as various other things) I want to be able to iterate through my tree quickly (which is why I picked vectors) and find a given Node at O(1) speeds. That's the problem though, an N-ary tree I believe only allows me at best (when considering the worst case scenario) O(N) searching. I potentially have to iterate through my entire tree before finding the element I am looking for. I'm about to break out the good ol' Donald Knuth lovin, but if anyone here has any suggestions (some sort of mapping scheme, maybe a better way of tracking the tree, thus allowing me direct indexing...?) it would be appreciated. Thanks

Well, what criteria are you going to be using to find things? Are you searching based on name... based on intersection...? Also, realistically, what is your tree's branching going to look like? Scene graphs tend towards a rather pathological structure... one root node, which has one child, which has one child, which has ELEVENTY BAZILLION children, each of which has one child.

If you're just iterating through all the nodes, obviously there's no way to visit N nodes in O(1). That's true regardless of what data structure you're using.

I wasn't entirely sure of what I would use this for yet. My reasoning for wanting to have it in there is that in case down the road I do need it, it will be in, and it will be fast.

I'm thinking a potential use for it would be that if I have some object that I need to all of a sudden add an effect to, I wouldn't need to iterate through the entire scene graph, and instead could just directly manipulate that object. But you're absolutely correct in saying that this is data structure independent. My initial method of searching was going to be by memory address comparisons, this is my first shot at a scene graph type structure for a rendering system so I'm still working some of the kinks out.

Perhaps you could make a suggestion as to how you would search through your eleventy bajillion objects. I'm thinking having some sort of unique identifier that allows for direct indexing is probably the best solution, but I'd like to hear some other ideas as well.

Thanks

The way you search through eleventy bazillion objects (not eleventy bajillion... you can't do that in real-time yet) to find a particular one, is you don't. If an object cares about that node, it keeps a pointer to the node. The memory address IS the unique identifier, and the accession of the node doesn't involve the data structure at all. Trees only help with searches which are hierarchical; that is, where a parent node is ever able to guarantee that the target node is in its hierarchy, or guarantee that it is not.

Sweet, thanks guys that helps quite a bit.

Now if only I knew what the hell a bajillion was (or bazillion for that matter)

A metric bajillion is a heck of a lot. An imperial bajillion is 1.563 hecks of a lot.

Quote:Original post by Sneftel
A metric bajillion is a heck of a lot. An imperial bajillion is 1.563 hecks of a lot.

1/8.3 bazillion also equals national debt. And it's not usually converted into furlongs per fortnight, since it overflows most real types.