These days i wrote the pathfinding for a game engine which supports QUAKE3 BSP maps. I choose the waypoint to construct the walkable areas, but i can't obtain the data of BSP map,i don't know how to build the navigraph. Is there anyone could tell me? I'll be gratitude to you!

I think your best bet would be place some kind of nav point entities around the map. Then connect every entity to its neighbours, i.e. where you can walk from navpoint A to navpoint B, connect them. Then calculate the distance between them and store them inside the navpoint.

Then you could use a normal A* algorithm, the distance from one navpoint (node) to the next is the G value.

I havent done it myself, but it seems to work in my head... hehe, no promises. [smile]

Thank you very much for your advice. Now I have wroten a programe to execute A* algorithm. But the problem is BSP map ,i don't know how to find navpoint on this map.All information is encapsulated in the *.bsp file.If I let NPC walk around the environment,and then restore all the postition by hand, is it too complicated and useless?