Entering / Exiting a NavGraph - Pathfinding

Question

I've got a manually created NavGraph in a 3D environment. I understand (and have implemented previously) an A* routine to find my way through the graph once you've 'got on the graph'.

What I'm interested in, is the most optimal way to get onto and 'off' the Graph.

Ex: So the routine go's something like this: Shoot a ray from the source to the destination, if theres nothing in the way, go ahead and just walk it.

if theres something in the way, we need to use the graph, so to get onto the graph, we need to find the closest visible node on the graph. (to do this, I previously sorted the graph based on the distance from the source, then fired rays from closet to furthest till i found one that didn't have an obstacle. )

Then run the standard A*...

Then 'exit' the graph, through the same method as we got on the graph (used to calculate the endpoint for the above A*) so I take and fire rays from the endpoint to the closest navgraph node.

so by the time this is all said and done, unless my navgraph is very dense, I've spent more time getting on/off the graph than I have calculating the path...

There has to be a better/faster way? (is there some kind of spacial subdivision trick?)

Answer 1

You could build a Quadtree of all the nodes, to quickly find the closest node from a given position.

Answer 2

It is very common to have a spatial subdivision of the world. Something like a quadtree or octree is common in 3D worlds, although you could overlay a grid too, or track arbitrary regions, etc. Basically it's a simple data-structures problem of giving yourself some sort of access to N navgraph nodes without needing an O(N) search to find where you are, and your choices tend to come down to some sort of tree or some sort of hash table.