Navigation Meshes

Navigation Meshes

    In this blog, I will talk about Navigation Meshes.  Our last chunk of lectures have been on Navigation Meshes, how they work, and how you can implement them.  To put into simple terms, navigation meshes, or navmeshes, are basically areas which are mapped out, and then relied upon by bots and AI to determine where they can and can't walk.  They are really helpful in determining pathfinding for AI.

    Pathfinding in games is far from "solved", as you can see in this video: http://www.youtube.com/watch?v=lw9G-8gL5o0#t=35, but navmeshes help solve some of the problems that you find with pathfinding techniques, such as waypoint navigation.  Navmeshes also allow you to describe large areas, which allow for much better AI decision making, with less effort (as opposed to using waypoints, which could need a ridiculous amount in open areas).

    Navmeshes also will allow course correction, which is something that can be difficult or impossible with waypoint navigation.  With waypoints, you would need to cast a whole bunch of new points around the obstructing object, which could intern, make your pathfinding much slower.  With a navmesh, you can simply raycast against the obstructing object and make a course correction.

    Navmeshes can also describe interactable areas for AI.  The picture above me shows a navmesh marked with a green X.  This navmesh tells the AI that they can jump on an object and enter a new navmesh (located on the top of the object).  

 

    They also make it easier to determine paths for different characters (different heights, size, vehicles).  Normally, you would have to introduce a new set of waypoints for a character to follow, and a vehicle to follow, since vehicles are much larger and would not be able to hug as tightly to buildings or objects as characters can.  With navmeshes, you can simply adjust the distance from the object based on the size of the object, and then you can build 2 different paths using the same mesh.  This makes it a robust tool when determining different paths for different sized objects.

    Navmeshes are a great pathfinding tool, and there are many navmesh generators out there, so they are easy to implement as well.