path finding - How can I generate a 2d navigation mesh in a dynamic environment at runtime?

So I've grasped how to use A* for path-finding, and I am able to use it on a grid. However, my game world is huge and I have many enemies moving toward the player, which is a moving target, so a grid system is too slow for path-finding. I need to simplify my node graph by using a navigational mesh.

I grasp the concept of "how" a mesh works (finding a path through nodes on the vertices and/or the centers of the edges of polygons).

My game uses dynamic obstacles that are procedurally generated at run-time.

I can't quite wrap my head around how to take a plane that has multiple obstacles in it and programatically divide the walkable area up into polygons for the navigation mesh, like the following image.

Where do I start? How do I know when a segment of walk-able area is already defined, or worse, when I realize I need to subdivide a previously defined walk-able area as the algorithm "walks" through the map?

I'm using javascript in nodejs, if it matters.

Answer

@Stephen - Long Comment - That paper looks like it might be worth a read when I have some time. Basically what I would have suggested is something along the lines of the Hertel-Mehlhorn Algorithm which is mentioned in the paper (a reference for this specific algorithm can be found here http://www.bringyou.to/compgeom/) with the addition of subdividing the map sides (outside boundary of the play area) some number of time to reduce the occurrences of multiple small triangles formed in the corners. Those small triangles can be problematic as they can end up being smaller than the thing you’re preforming path-finding for. The Hertel-Mehlhorn is for the reduction of the polygons produced by a triangular partitioning if you’re interested here is more on triangulation: http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm.

Also, if you’d rather not reinvent the wheel, I think this library will actually do everything you need: http://code.google.com/p/polypartition/. It preforms the triangulations and reductions with one of a number of different options including Hertel-Mehlhorn. It’s an MIT License which means it can be used for closed-source and commercial projects if that is an issue.

If you do decide to keep working on your own implementation, I’d love to see what you come up with.