# [C++] Tree class

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

## Recommended Posts

Hey folks !

I've just realized that it might be a good idea to sort nodes created during a pathfinding procedure in a tree structure (the grid is composed of triangles) and I was wondering if there is any particular tree library you guys might recommend.

Since every node will have a unique numeric index I figured it would be faster to maintain a tree structure than just a linear list. So what I need is a tree class that can hold arbitrary data structures, re-sort the nodes (to maintain the order as new nodes are pushed in) and destroy them in a reliable fashion. Many thanks for any tips and hints ! :)

- Dave

##### Share on other sites
std::map or std::set should work, depending on whether your key is extrusive or not. But what are you planning to key them on? What's the natural sort order for triangles in a grid?

##### Share on other sites
The triangles are polygons of a mesh which I search from one point to another using A*, and for each polygon traversed I store calculated data in a form similar to this:

struct PathNode{	float distanceTraveled;	float distanceToTarget;	PathNode* pParent;	DWORD faceIndex;};

There is more data to it, DirectX9 helps store away things like polygon adjacency among other things so the rest I need is supplied there. Now I can imagine my implementation is terribly flawed but I welcome critique to better it.

For now though, could you give me an example of how I would use std::set to store and retrieve these nodes? I take it the set is constructed like a vector in the form std::set< PathNode > pathNodes and that new nodes are pushed in using pathNodes::insert(), but are these nodes organized automatically in an optimal way or do I need to clarify which member variable to use as an index? Also how does find() work, can I supply the index in some way to retrieve the node that matches it?

Hope I'm not asking too many redundant questions, I really appreciate your help :)

##### Share on other sites
Is this for the 'open set' of an A* implementation?

If so, a typical solution would be to use a priority queue. The SC++L does supply a priority queue container adapter, but if re-sorting of existing nodes is required (as is typically the case with A*), std::priority_queue may not be an appropriate choice due to its limited interface.

You can, however, use a std::vector along with the various SC++L 'heap' functions for this. (Note that you'll most likely want to use a custom comparator keyed off the distanceTraveled member field of your node struct.)

##### Share on other sites
Quote:
 Original post by jykIs this for the 'open set' of an A* implementation?If so, a typical solution would be to use a priority queue. The SC++L does supply a priority queue container adapter, but if re-sorting of existing nodes is required (as is typically the case with A*), std::priority_queue may not be an appropriate choice due to its limited interface.You can, however, use a std::vector along with the various SC++L 'heap' functions for this. (Note that you'll most likely want to use a custom comparator keyed off the distanceTraveled member field of your node struct.)

Interesting... Actually I was going to use the tree to hold all encountered nodes, open or not, so that I could easily query at any point if a polygon has been encountered at all. Then I would use some other means to keep track of which ones are open, possibly a vector holding indices or direct references to the nodes.

I probably have a very screwy way of thinking here but the way I see this differs from the standard A* implementation is that it can't really be thought of as a 2D grid since a triangle has 3 direct neighbors and not 4 (which is a good thing in terms of complexity I guess).

##### Share on other sites
Quote:
 Original post by VanderryInteresting... Actually I was going to use the tree to hold all encountered nodes, open or not, so that I could easily query at any point if a polygon has been encountered at all.
The most straightforward method is to attach that information to the polygon itself. Alternatively, you can use a hash set, which has a better time complexity for lookups than a balanced tree.
Quote:
 I probably have a very screwy way of thinking here but the way I see this differs from the standard A* implementation is that it can't really be thought of as a 2D grid since a triangle has 3 direct neighbors and not 4 (which is a good thing in terms of complexity I guess).
A* has nothing to do with grids... students tend to learn it in terms of pathfinding on grids, but at its core it's a graph search algorithm and a grid is just a kind of graph.

##### Share on other sites
Quote:
 Original post by SneftelThe most straightforward method is to attach that information to the polygon itself. Alternatively, you can use a hash set, which has a better time complexity for lookups than a balanced tree.

I was thinking since a lot of the polygons of a mesh will not be walkable (those with too much inclination) there would be a lot of unused memory if I let the polygon structure carry this data. Also just in case it would be a good idea to run several pathfinding procedures simultaneously (to minimize loop time) I think it would be better to store this information elsewhere, and of course to avoid having to clean the data between the calls. Now I don't mean to sound like I have a perfectly good idea what I'm doing (because I don't xD) so please let me know if this is reasonable thinking.

But a hash set, if there isn't anything to lose by switching from a std::set to this, then I will absolutely try that.

##### Share on other sites
"error C2061: syntax error : identifier 'T'" in winnt.h (I presume due to the inclusion of iostream).
There was something mentioned on the website about using the right compiler flag but I honestly have no idea how to change it.

##### Share on other sites
Errr... you know that Visual C++, like all C++ compilers, includes an STL implementation, right?

##### Share on other sites
Yeah, I just thought some elements weren't included in the standard package. Including <hash_map> works but I can't access the hash_map identifier, if this is the correct spelling.

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633670
• Total Posts
3013262
×