Jump to content
  • Advertisement
Sign in to follow this  
Vanderry

[C++] Tree class

This topic is 3005 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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by jyk
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.)


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 this post


Link to post
Share on other sites
Quote:
Original post by Vanderry
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.
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 this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
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.

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 this post


Link to post
Share on other sites
On a side note... I'm having some trouble using the STL library downloaded at this page. Simply adding the directory to "Additional Include Directories" in Visual Studio 2008 causes
"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 this post


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

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!