What to expect from a Navigation System

First of all, before we explore the Unreal Navigation System, it is useful to define what we would expect from a generic Navigation System. The following is required from the Navigation System:

• It needs to determine if a path (that can be traversed by the agent performing the query) exists between two generic points on the map
• If such a path exists, return the one that is the most convenient for the agent (usually the shortest)

However, while searching for the best path, there are many aspects to take into consideration. A good navigation system should not only consider these, but also perform the query in a relatively short period of time. Some of these aspects are as follows:

• Is the AI agent who's performing the query able to pass through a specific portion of the map? For instance, there might be a lake, and the AI character may or may not know how to swim. Similarly, can the agent crouch and move into a ventilation tunnel?
• The AI agent might want to avoid (or prefer) certain paths, which aren't necessarily the shortest ones. For instance, if a building is on fire, the agent should try to avoid this, or risk of getting burned. As another example, let's say there are two paths: one is covered from enemy fire, but it's long, while the other one is short but exposed to enemy fire; which one should the AI choose? Although this might be part of the decision-making process, some heuristics can be implemented at the level of pathfinding, and a navigation system should support them.
• A map might be dynamic, which means that obstacles, objects, roads, cliffs, and so on, change during gameplay. Is the navigation system able to handle these changes in real time while they happen, and correct the generated paths?

Now, it's time to see how Unreal implements all of these features.