Dynamic updates of navigation meshes

Path planning is the field of Artificial Intelligence (AI) whose objective is to study and research algorithms that plan the optimal route to traverse from one point to another in a given environment. They are primarily utilized in the field of robotics and simulation programs such as video games. Navigation meshes are important data structures based on graphs that can be used to represent any general 3D environment. The main reason is because they are very efficient and flexible. Additionally most widely used pathfinding algorithms are based on graphs. In real life applications, for a given environment its navigation mesh is generally created manually. They may be automatically generated partially but majority of the work is done manually. A set of algorithms that generate near optimal navigation meshes for an input environment have been studied in the paper A Framework for Navigation of Autonomous Characters in Complex Virtual Environments by Ramon Olivia and Dr. Nuria Pelechano. NEOGEN (Near-Optimal Generator of navigation meshes) is a framework written by the authors that includes the algorithms introduced in the paper. The framework is written in C++. The output navigation meshes of NEOGEN can be used to plan simple paths (walk from point A to B if there exist sequences of convex polygons that the character can walk through). But a path can be complex (may include swinging from a rope, jumping, etc). The primary objective of this project is to find ways how the navigation mesh generated by NEOGEN-3D so that it can be used for more advanced and complex pathfinding. For example climbing stairs, jumping from platform to platform, etc. This project also pursues the following secondary objective of detecting limitations of the current implementation of NEOGEN-3D and propose solutions to overcome those limitations