This is kind of a general query but could be useful for some pathfinding implementation i am trying out... I am building up a list of nodes that are connected to each other in my world based on a certain set of rules... however, the issue is how do i get from say node C -> node E efficiently if the connection is indirect i.e. A / \ B D / \ | C \ | \E B -> E and D -> E are connected aswell Do i have to recurse the whole tree everytime to find the shortest route from C to E? In this example its not a problem but if the tree has several hundred nodes? i know there are some general tree searching algorithms but they all seem to be fairly inefficient if they aren''t binary space trees...unfortunately each of my nodes can contain upto 4 children and not really suitable for that kind of algorithm as far as i''m aware. i have assigned costs to all node connections but the problem is finding best route without looking through the whole tree each time. The searching of the tree is the only thing which is causing me a headache...i''m not using A* at this level as its supposed to be a hierarchical route finder.. regards

Let me try and get the tree displayed correct

A
/ \
B D
/ \
C E

hope this appears ok..

regards

Let me try and get the tree displayed correct

A
/ \
B D
/\ \
C \ \
\-E
hope this appears ok..

regards

Ok i give up, its not happening lol, hope people can see what i am trying say...

If it''s a pathfinding database, then surely you can add some positional information to the nodes to use in a heuristic? And you can always try caching previously found paths to avoid having to recalculate them.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

You''ll want to use a graph traversal algorithm. BTW: use the ''code'' and ''/code'' markup tags to force formatting to the way you want it.

Timkin

Ah a graph traversal algorithm, that seems to be just the ticket...many thanks for the help.

Kylotan, not sure what you mean in your reply, i''m fairly new to this so bear with me...

The topline at the moment is that i have several very large grids for which several thousand entities are walking around trying to get from their A to their B....by building up a list of critical nodes (points of interest in the world ) i can then say if i am at A and i need to get to B i can quickly scan the pathfinding database based on cost for each point of interest..
once i''ve determined if they are connected, i then find the shortest route, i then have a list to all the cells for that particular route which the entity follows ( as this is built up as the routes are laid down )...

This is the only way i can see resolving this issue fairly quickly on an average machine - the bottleneck for me was the recursion through the tree and finding the shortest route between any 2 points on that tree.....just needed to find the quickest way to do it and that graph traversal algorithm with a little optimization seems to be just the ticket for me.

regards