Archived

This topic is now archived and is closed to further replies.

Bakednoodle

Tree searching

Recommended Posts

Bakednoodle    122
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

Share this post


Link to post
Share on other sites
Timkin    864
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

Share this post


Link to post
Share on other sites
Bakednoodle    122
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

Share this post


Link to post
Share on other sites