Hands-On Artificial Intelligence with Unreal Engine

上QQ阅读APP看书，第一时间看更新

Unreal Navigation System

The Unreal navigation system is based on a Navigation Mesh (Nav Mesh for short). It entails dividing the navigable space into areas – in this case, polygons – which are subdivided into triangles for efficiency. Then, to reach a certain place, each triangle is considered a node of a graph, and if two triangles are adjacent, then their respective nodes are connected. On this graph, you can execute a pathfinding algorithm, such as A* with a Euclidean distance heuristic, or even something more complicated (e.g. variants of A* or systems that take into consideration different costs). This will produce a path among these triangles where the AI character can walk.

In reality, this process is a little bit more complicated, because considering all the triangles as nodes of a giant graph will produce a good result, but it is inefficient, especially since we have access to the information that's stored in the polygons and how these are connected. Moreover, you might need extra information about specific triangles, which might have different costs, different abilities required to traverse them, etc… However, unless you need to change the underlying structure of the Navigation System, you don't need to work/operate at this level of detail. Being able to understand that all of the triangles form a graph in some way, in which pathfinding algorithms can run, is more than sufficient to master the tool itself.

To be able to use the Navigation System, let's understand the main process of setting up the navigation system. At this stage, we will no longer worry about how the system is structured underneath, but rather how we can use all of its features. The system will do the rest. In the same way, we need to provide information about the map to the navigation system (e.g. specify special areas). Usually, it's the AI programmer in your team who takes care of this, but if your team is small, a level designer might take care of this task. Although there is not a specific process, but, rather an iterative procedure, let's explore the different steps – or tools, if you prefer – that you can use to define the Nav Mesh in Unreal. We will examine them in detail throughout this chapter:

Generation of the Navigation Mesh: This is the first step. Before you'll be able to use the following tools, it is important to start generating a Nav Mesh. This step includes defining how to generate the polygons, the triangles, the precision of the Nav Mesh, and even which kind of agents will traverse this specific Nav Mesh.
Navigation Mesh Modifiers: Not all the parts of the Nav Mesh are created equal, and this is a tool to specify which parts of the Nav Mesh should behave differently. In fact, as we have seen before, there might be a zone with poisoned gas, and the agent would like to avoid this part, unless they really have to traverse it. The Nav Mesh Modifier allows you to specify that the area containing the gas is special. However, the type of behavior within the area (e.g. this path should not be traversed, or should only be traversed by agents with swimming abilities) is specified within a Nav Area.
Navigation Areas: This allows you to specify how a specific type of area should behave, whether it should be avoided, etc. These are key when performing Nav Filtering to determine which areas the agent can traverse.

Navigation Links: These can connect two different parts of the Nav Mesh. Suppose you have a platform ledge. By default, the AI agent will find another way. If you have in mind the Third Person map template, the agent that needs to get down from platform will go around the area to use the stairs, rather than just falling/jumping off the platform. A Nav Link allows you to connect the part of the Nav Mesh that's on top of the platform with the part below it. As a result, the agent will be able to fall off the platform. However, note that Nav Links can connect two generic portions of the Nav Mesh, thus allowing pathfinding to find its way through jumps, teleports, etc.
Nav Filtering: We don't necessarily want to find a path in the same way on every occasion. Nav Filtering allows us to define specific rules on how to perform the pathfind for that specific instance (for that specific time that the pathfind is invoked to seek a path).

Let's break these points down and talk about them in more detail.