Hmm ... not sure if I understood the last post quite, have to look into that sort of stuff first.

But on the navigation mesh subject: nav-mesh is ok for things that is walking on the mesh, or need restrictive movement on a 2D basis. What if I then put a Dragon into this world, or airplane, or a bird in a complex map of those you find in quake?

Only thing I could think of is that those objects would have to start and stopp on the mesh, but ...

... how would pathfinding in Decent be? (the wird old indoor space 3D game)

I am not sure if a set of connected 3d convex volumes would be called a nav mesh. I don't know if there is an generally accepted term for it yet or not. I may be off here, but a nav mesh implies 2d connectivity to me.

If you have things that fly, then a traditional 2d nav mesh probably won't handle it (at least, without some sort of 3d augmentation).

Instead of a network of 2d convex shapes, things that fly (like Decent) probably would use a network of 3d convex shapes. Most of the same properties apply to a 3d mesh; some of the algorithms used for automatic construction have a higher computational complexity, but that it is still very doable.

I am pretty sure the Decent level building tool operated in convex shapes; these were probably translated fairly directly into their navigation volume system. I haven't looked at it, but it looks like the Decent code was released: http://www.descent2.com/ddn/sources/descent2/ It may be worth glancing at.

I was discussing pathfinding with another person I know at work, and he was wondering if you could create an algoritm that would just spread out tons of points, randomly .... then do pathfinding among them. The only fear I have is that the points become too many to pathfind among, and too few in some areas making the NPC wlak weird routes. Then I also wonder if this would be easy too use in A* which are weighted.

But maybe a combination of those two. Have a nav-mesh as a basis, and dropp lots of points around in space for flying creatures, and try optimize the number of points and where they are dropped, and remove as much as possible. Then create a path in the air for these flying stuff, and "follow" the path so the have some freedoms.

...Thats the only idea I have. But then we have like 2 pathfinding systems... but thats ok.

If you're interested, here's a link to an article I wrote for my GDC talk on arbitrary mesh 3D pathfinding from a couple of years ago.

The system was used in a 3D shooter with very good results, fully automated, no manual node placement or artist tweaking. If I ever work on an FPS again, I'll definately use it.

http://www.gamasutra.com/features/20020405/smith_01.htm

Hope this can be of some help.