A navigation mesh is a means to automatically identify points at which to place path nodes. A navigation mesh is a set of convex hulls (polygons) overlaid on an environment such that the area within each hull is guaranteed to be obstacle-free. The convexity of the hulls is important because an agent within the area of a hull can move to any other point within the hull without crossing a hull boundary.
Furthermore, when two convex hulls are adjacent to each other (i.e., they share an edge), that edge can be thought of as a "portal"—an invisible door—from one safe navigation region to another. Connecting adjacent convex hulls into a network of safe passages results in a path node network through which an agent can travel between any two points in the environment without fear of collision. That is, a navigation mesh can be used to automatically place path nodes throughout a game map. The resulting network of path nodes creates a super-highway by which an agent can move from any safe area to any other safe area.
There are many ways to convert a navigation mesh into a path node network. In the figure below, I have chosen to place path nodes at the center points of each portal and to generate edges between nodes that are on the same convex hull. This keeps the number of nodes and edges low and ensures that the paths are far away from obstacles. It does create a bit of inefficiency since the path network may take the agent a little bit out of its way. However, there are opportunities to "smooth" the path by taking shortcuts or cutting corners, resulting in conservative but naturalistic-looking navigation.
I write the code to generate a navigation mesh for an arbitrary environment and to generate a path network for the environment. The path network should work on any given terrain of obstacles and allow the agent to traverse between any two points (as long as there exists a path wide enough for the agent to fit without colliding with an obstacle.
Log in or sign up for Devpost to join the conversation.