[C++] Tree class

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?

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:



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 :)

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.)

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).

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.

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.

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.

Errr... you know that Visual C++, like all C++ compilers, includes an STL implementation, right?

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

hash_map is called unordered_map and can be found in std::tr1 namespace(comes with VS2010 and is optional download for VS2008).

#include

Interface is just like map

Quote:

Original post by AndyPandyV2 hash_map is called unordered_map and can be found in std::tr1 namespace(comes with VS2010 and is optional download for VS2008). #include Interface is just like map

Oh heh, that's one rock I wouldn't have thought to look beneath. But I don't seem to have any file named unordered_map in my VC directory, and std::tr1::hash holds nothing more than a () operator. So I guess maybe I need that optional download.

[Edited by - Vanderry on July 5, 2010 12:48:36 AM]

Okay so it was tucked away in the stdext namespace? Sorry to clutter up this thread so badly, but now I can go to bed and rest easy :)