# 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.

-
The dynamic partitioning you’re trying to implement is going to depend on the specifics of your map elements. Are your obstacles elements entirely composed of grid aligned rectangles as shown in your example? Rotated rectangles? Irregular polygons? Or non-polygon shapes with lots of curves? Do you have point/poly data for the shape of the obstacles? If so is that shape data in terms of triangles, rectangles, exclusively convex polygons or a mix of convex and concave polygons? – Matthew R Jul 5 '12 at 6:48
@Matthew My world is composed of convex polygon obstacles, no curves and no concave polygons. Each obstacle is stored as a polygon object with vertices represented by vector objects. – Stephen Jul 5 '12 at 13:18
For what it is worth, I am working on a solution based on this paper: gradworks.umi.com/3493710.pdf If I am successful I will post my solution. – Stephen Jul 5 '12 at 13:19
the navigation mesh isn't there to 100% tell you if you can go somewhere or not, it's just a basic outline of walkable areas, you still have to do collision checks against dynamic objects, edit: pretty much what Ray said – dreta Jul 6 '12 at 11:02
@Stephen -- See Long Comment answer. – Matthew R Jul 7 '12 at 6:26

@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.

-
Great answer, @Mathew. And you should definitely read that paper! It's easy to follow and explains a great technique (especially Appendix A which talks about agent based discovery/generation of the mesh). I am coding a version of this algorithm for javascript, and it is coming along well. I'll post it as an answer when it is done. – Stephen Jul 7 '12 at 14:49
@Stephen would love to see this work – kevzettler Oct 28 '14 at 3:05
@Stephen I'm looking for a javascript version too – Apolo Apr 5 at 16:16

Rather than a mesh, you might just consider a hierarchical A* approach. A mesh's biggest advantage is in dealing with game worlds that aren't grid aligned, rather than in reducing complexity from a grid.

With a hierarchical approach, you subdivide your world repeatedly (much like a quad tree), and generate connectivity information between the nodes. You can then quickly generate a path between large chunks of the world, and only use the high-resolution grid to path find within a larger chunk.

The hierarchical approach will give orders of magnitude better performance, while a mesh at best is only going to give you a small linear improvement.

The naive approach is to just divide your world into X by X larger grid aligned chunks, generate the connectivity info between them (e.g., is there a path between through chunk 2x1 from 3x1 to 2x2, and what is the distance of the average path).

Note that you may not always get ideal paths with this approach in some particular circumstances. Generating variable-sized layers of chunks alleviates the problem, but honestly it's usually just way easier to avoid the ever making makes with the problem paths and to rely on the fact that the player is highly unlikely to notice any enemies taking suboptimal paths except in the most degenerate of cases.

-
I should explain further: My game is not grid aligned. I was building a grid in an 800 x 600 pixel area, each pixel being one space on the grid (I was still figuring out A*, so I wasn't thinking about the performance of this yet). I have obstacles that are not as simple as the ones in the above example image, I was just trying to illustrate the problem. Obviously such a playing field needed to be revised, and after some research I think a nav mesh would be the right way to go. – Stephen Jun 27 '12 at 12:52

I think you might be overcomplicating this. You probably don't need to generate navigation meshes on the fly. Instead have a static navigation mesh for your base world.

Pathing around obstacles can be solved using steering behaviours (use obstacle avoidance). If on the off chance your obstacle is so large it fills or completely blocks off travel from one nav-poly to the next, then have some way of checking for this edge case and recompute the path between the poly you're currently in and the one you're blocked off from.

-