How can I generate a 2d navigation mesh in a dynamic environment at runtime?
- by Stephen
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.
