In this chapter, we will learn path-finding algorithms for navigating complex scenarios. Game worlds are usually complex structures, be it a maze, an open world, and everything in between. That's why we need different techniques for approaching these kinds of problems.

We'll learn some ways of representing the world using different kinds of graph structures, and several algorithms for finding a path, each aimed at different situations.

It is worth mentioning that path-finding algorithms rely on techniques such as Seek and Arrive, learned in the previous chapter, in order to navigate the map.

A grid is the most widely-used structure for representing worlds in games because it is easy to implement and visualize. However, we will lay the foundations for advanced graph representations while learning the basis of graph theory and its properties.

First, we need to create an abstract class, Graph, declaring the virtual methods that every graph representation implements. It is done this way because no matter how the vertices and edges are represented internally, the path-finding algorithms remain high level, thereby avoiding implementation of the algorithms for each type of graph representation.

This class works as a parent class for the different representations to be learned...

This is another widely-used technique for world representation based on points located throughout the valid area of navigation, be they manually placed or automated via scripting. We'll be using manually placed points connected automatically via scripting.

Just like the previous representation, it's important to have several things in order before continuing:

• Having the Edge class prepended to the Graph class in the same file
• Defining the GetEdges function in the Graph class
• Having the Vertex class

Sometimes, a custom navigation mesh is necessary for dealing with difficult situations such as different types of graphs, but placing the graph's vertices manually is troublesome because it requires a lot of time to cover large areas.

We will learn how to use a model's mesh in order to generate a navigation mesh based on its triangles' centroids as vertices, and then leverage the heavy lifting we learned from the previous recipe.

This recipe requires some knowledge of custom editor scripting and an understanding of implementing the points of visibility graph representation. Also, it is worth mentioning that the script instantiates a CustomNavMesh...

The Depth-First Search (DFS) algorithm is a path-finding technique suitable for low-memory devices. Another common use is to build mazes with some minor modifications to the list of nodes visited and discovered, but the main algorithm stays just the same.

This is a high-level algorithm that relies on each graph's implementation of the main functions (build, init, and so on), so that the algorithm is implemented in the Graph class.

It is important to take a moment and verify when the recipe is manipulating actual objects, or vertex IDs.

The Breadth-First Search (BFS) algorithm is just another basic technique for graph traversal and is aimed at getting the shortest path in the fewest steps possible, with the trade-off of being expensive in memory; thus, it is aimed especially at games for high-end consoles and computers.

This is a high-level algorithm that relies on each graph's implementation of the general functions, so the algorithm is implemented in the Graph class.

Even though this recipe is only defining a function, please...

Dijkstra's algorithm was initially designed to solve the single-source shortest path problem for a graph. Thus, the algorithm finds the lowest-cost route to everywhere from a single point. We will learn how to make use of it given two different approaches.

The first thing to do is to import the binary heap class from the Game Programming Wiki (GPWiki) into our project, given that neither the .Net framework nor Mono have a defined structure for handling binary heaps or priority queues.

The source file is already in the book's online repository service provider as it is no longer available online.

The A* algorithm is probably the most widely-used technique for path finding given its implementation simplicity, efficiency, and because it has room for optimization. It's no coincidence that there are several algorithms based on it. At the same time, A* shares several roots with Dijkstra's algorithm, so you'll find similarities in their implementations.

Just like Dijkstra's algorithm, this recipe uses the binary heap extracted from the GPWiki. Also, it is important to understand what delegates are and how they work. Finally, we are entering into the world of informed search; that means that we need to understand what a heuristic is and what it is for...

IDA* is a variant of an algorithm called Iterative Deepening Depth-First Search. Its memory usage is lower than A* because it doesn't make use of data structures to store the looked-up and explored nodes.

For this recipe, it is important to have some understanding of how recursion works.

This is a long recipe that can be regarded as a big two-step process: creating the main function and an internal recursive one. Please take into consideration the comments in the code for better understanding of the...

When dealing with large graphs, computing paths can take a lot of time, even driving the game to a halt for a couple of seconds. This could lead to ruining the overall experience, to say the least. Luckily enough, there are methods for avoiding that.

We'll learn how to implement path-finding techniques using coroutines by refactoring the A* algorithm learned previously, but we will handle its signature as a different function.

When dealing with regular-size vertices on a graph, such as grids, it's pretty common to see some kind of robotic movement from the agents in the game. Depending on the type of game we're developing, this could be avoided using path-smoothing techniques, such as the one we're about to learn:

Let's define a new tag in the Unity editor called Wall and assign it to every object in the scene that is intended to work as a wall or obstacle in the navigation.

This is an easy, yet powerful, function:

1. Define...