Navigation

The problem behind pathfinding is as old as the Labyrinth at Knossos: how do I get from point A to point B using the shortest route and avoiding all obstacles in-between?

Many algorithms have been developed to solve pathfinding problems, including those related to the A* algorithm, which was first introduced in computer science during the 1960s (section 2).

Pathfinding routines are typical components of many video games, with Non-Player Characters (NPCs) having the task of finding optimal paths on the game maps, which can constantly change. For example, passageways, gates, or doors can change their statuses during gameplay.

There are quite a lot of problems when it comes to pathfinding, and unluckily for us, there isn't a one-solution-fits-all approach. This is because each problem will have its own solution, depending on the type of problem it is. Not only this, it will also depend on the type of game that you are developing. For example, is the final destination for the AI a static building (stationary), or do they need to jump on top of a floating raft (dynamic)? You also need to take the terrain into consideration – is it flat or rocky, and so on? To add an additional layer of complexity, we also need to consider whether there are obstacles present, as well as whether these objects are static (fire hydrant) or if they can be moved (e.g. boxes). Then, we need to think about the actual path itself. For example, it might be easier to travel along the road, but running across rooftops will get you where you need to be quicker. Following the same train of thought, the AI might not even have a final destination, in the sense that they don't have to be somewhere specific. For example, they might just wander around as someone who is part of a village. However, I have only highlighted a few issues and considerations that are related to pathfinding. As you experience different situations that use pathfinding, you are likely to encounter other issues. Remember to be patient and to consider all the variables that I have mentioned here and others that are specific to your situation.

Fortunately for us, Unreal has incorporated a navigation system that can be used for the most common of situations. As a result, we don't need to re-implement everything from scratch. The main goal of this chapter is to ensure that you understand how to use it, and ensure that you have some idea of how you can expand on it. 

In this chapter, we will cover the following topics:

• What to expect from a Navigation System

• The Unreal Navigation System, and how it works

• How to Generate the Navigation Mesh for a level, and its available settings

• How to Modify the Navigation Mesh, by using the following:

  • Navigation Areas, to change the weight associated with a part of the Navigation Mesh
  • Navigation Links, to connect two parts of the Navigation Mesh that would otherwise be separated
  • Navigation Filters, to perform a slight change to the Navigation Mesh while executing a specific query on the Navigation System

Let's dive in!