If you're going to use a navigation mesh, you should definitely do some automatic generation. The automatic generation can be tricky depending on what your mesh actually uses, since the performance of your pathfinder will greatly depend on the quality of your mesh. If you already have a triangulation of the pathable area through a 3D level, you could probably use that as a starting point and then do a mesh simplification algorithm to reduce the number of triangles into a set of equivalent covering convex polygons. You can look for the Hertel-Melhorn algorithm which does such a thing (but not optimal).

You need to know the pathable area of your levels for you to be able to do this. Could be either marked up by a human or you have some procedure to generate your terrain in which you should be able to distinguish between walkable and unwalkable areas. Once you have this, you need to figure out what the 2 or 3 space representation is of this area actually looks like so you can extract out point data. Even in 3D games, you can usually just simplify this down to basically a 2D problem and build an abstract graph that still retains all of the traversable areas in the 3D space.

If you just have some point data which describes points within the walkable areas of your map, you could do a constrained Delaunay triangulation to get you first mesh and then simplify it later. The Delaunay triangulation, I've read is useful for a variety of reasons but I haven't actually used it myself for pathfinding, so I can't really say much of my own experience. The Delaunay triangulation provides certain properties which seem nice for pathfinding, such as avoiding really long and skinny triangles. The constrained Delaunay triangulation is different in that it allows you to specify edges which must be a part of your triangulation, but this also forgoes the guarantee of the Delaunay property since you may be forcing an edge which breaks the property.

To be quite frank, this seems like a lot of work just to get performance. I actually went down a similar road, and my navigation mesh doesn't use triangles at all. It's basically a grid based pathfinder where the grid cells can be an arbitrary size. The navigation mesh generation I do is very simple and can lead to bad edge cases, but I'm totally cool with what I've got for my game. It was much simpler than having to write up and test all of these other algorithms for triangulation (I have a 2D game and I have no triangle data for my levels; the levels themselves are built up from tiles).

To get a decent path out of your navigation mesh, you'll also need to do some string pulling. Check out the funnel algorithm for info on that if you don't know what that is (http://compgeom.cs.u...topic-paths.pdf section 2.2.4). Mikko Mononen also has an excellent, and simple implementation of the funnel algorithm described here: http://digestingduck...-algorithm.html.

Be sure you arrange your data structures in a way that you can initialize the graph in a fast way. I've found that often the slowest part of the A* pathfind isn't even the graph search. People seem to write their graph representation in a way that makes the graph initialization slow. I was one of those people. When I rewrote my pathfinder, I wrote my graph representation in a structure of arrays format which allowed for me to get super fast memcpy()/memset() initialization calls. That alone helped me improve reduce the initialization time for my pathfinding by a factor of 5 to 10. The improved data layout also undoubtedly helps in the graph search portion as well, but to a lesser degree. You can also do some tricks to make the graph initialization even faster (I still touch every single node in the graph). I'm aware of some tricks, but not the details, where you can consider graph nodes to be initialized by checking a count value and comparing it to another count value and depending on that comparison, the node is considered initialized or uninitialized.