Contents
Navigation Meshes and Pathfinding 1 The navigation mesh Graph. To summarize, a navigation mesh is a mesh that represents where an NPC can walk. 2 Navigation Meshes In practice. In our cases, we used A*, the simple stupid funnel algorithm and a traditional steering algorithm that is still in development. 3 Graph Search Algorithm.
A navigation mesh is actually a 2D grid of an unknown or infinite size. In a 3D game, it is common to represent a navigation mesh graph as a graph of flat polygons that aren’t orthogonal to each other. There are games that use 3D navigation meshes, like games that use flying AI, but in our case it’s a simple grid.
Using a navigation mesh also speeds up graph exploration because, technically, a navigation mesh has fewer nodes than an equivalent waypoint network (that is, a network that has enough points to cover a navigation mesh). To summarize, a navigation mesh is a mesh that represents where an NPC can walk.
How are navigation meshes different from waypoints networks?
However, as technology has evolved, computers got more memory that became faster and cheaper. In other words, there was a shift from efficiency to flexibility. In a way, navigation meshes are the evolution of waypoints networks because they fulfill the same need but in a different way.
How is string pulling used in navigation mesh?
String pulling is the next step in the navigation mesh algorithm. Now that we have a queue of cells that describes an optimal path, we have to find a queue of points that an AI agent can travel to. This is where the sting pulling is needed. String pulling is in fact not linked to characters at all : it is rather a metaphor.
To summarize, a navigation mesh is a mesh that represents where an NPC can walk. A navigation mesh contains convex polygonal nodes (called cells). Each cell can be connected to each other using connections defined by an edge shared between them (or portal edge).