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.