constructing a navigation graph

To be honest, I have a hard time following you. But I'll give it a shot. I assume you have some low level representation of your (game)world and want to do path finding. To increase search speed, you want a more abstract navigation graph. This is a good thing.
How is your world represented currently? Is it simply tile based or is it some connected 3D mesh?

For 2D tile maps, I once created a navigation graph as follows: I first determined for each tile the distance to the nearest obstacle (blocked tile) using some kind of flood fill. Then, viewing this as a distance map, I search for all local maxima (tiles with larger distance to any obstacle then any of its neighbor tiles). These are the nodes of the navigation graph. Then, I detect local-maximum paths of tiles, starting from a maximum nodes and having strictly lower distance neighbors besides the path. Such a path will eventually end at another local maximum, or you found a dead end, which should be added as a graph node as well. The found paths are stored as edges between the nodes. This gives you a pretty useful navigation path. Some minor post-processing steps might be necessary to combine really close nodes, but that's not the hardest part i.m.o.

For 3D meshes, navigation graph generation algorithms exist, but i do not have any experience in that area.

Succes,

Dietger

thanks a llot for your help.I appriciate you taking the time to answer the query