Chapter 2. Navigation

In this chapter, we will cover the following recipes:

• Representing the world with grids

• Representing the world with Dirichlet domains

• Representing the world with points of visibility

• Representing the world with a self-made navigation mesh

• Finding your way out of a maze with DFS

• Finding the shortest path in a grid with BFS

• Finding the shortest path with Dijkstra

• Finding the best-promising path with A*

• Improving A* for memory: IDA*

• Planning navigation in several frames: time-sliced search

• Smoothing a path

Introduction

In this chapter, we will learn path-finding algorithms for navigating complex scenarios. Game worlds are usually complex structures; whether a maze, an open world, or 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, learnt in the previous chapter, in order to navigate the map.

Representing the world with grids

A grid is the most 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 properties.

Getting ready

First, we need to create an abstract class called 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, thus avoiding the implementation of the algorithms for each type of graph representation.

This class works as a parent class for the different representations to be learned in the chapter and it's a good starting point if you want to implement graph representations not covered in the book.

The following is the code for the Graph class:

1. Create the backbone with the member values:

   using UnityEngine;
   using System.Collections;
   using System.Collections...

Representing the world with Dirichlet domains

Also called a Voronoi polygon, a Dirichlet domain is a way of dividing space into regions consisting of a set of points closer to a given seed point than to any other. This graph representation helps in distributing the space using Unity's primitives or existing meshes, thus not really adhering to the definition, but using the concept as a means to an end. Dirichlet domains are usually mapped using cones for delimiting the area of a given vertex, but we're adapting that principle to our specific needs and tool.

Example of a Voronoi Diagram or Voronoi Polygon

Getting ready

Before building our new Graph class, it's important to create the VertexReport class, make some modifications to our Graph class, and add the Vertex tag in the project:

1. Prepend the VertexReport class to the Graph class specification, in the same file:

   public class VertexReport
   {
       public int vertex;
       public GameObject obj;
       public VertexReport(int vertexId, GameObject obj...

Representing the world with points of visibility

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

Getting ready

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

Note

The vertex objects in the scene must have a collider component attached to them, as well as the Vertex tag assigned. It's recommended for them to be unitary Sphere primitives.

How to do it...

We'll be creating the graph representation class as well as a custom Vertex class:

1. Create the VertexVisibility class deriving from Vertex:

   using UnityEngine;
   using System.Collections.Generic;
   
   public class VertexVisibility : Vertex
   {
       void Awake...

Representing the world with a self-made navigation mesh

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 from the previous recipe we learned.

Getting ready

This recipe requires some knowledge of custom editor scripting and understanding and implementing the points of visibility in the graph representation. Also, it is worth mentioning that the script instantiates a CustomNavMesh game object automatically in the scene and requires a prefab assigned, just like any other graph representation.

Finally, it's important to create the following class, deriving from GraphVisibility:

using UnityEngine;
using System.Collections;
using System.Collections.Generic...

Finding your way out of a maze with DFS

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

Getting ready

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.

It is important to

How to do it...

Even though this recipe is only defining a function, please take into consideration the comments in the code to understand the indentation and code flow for effectively:

1. Declare the GetPathDFS function:

   public List<Vertex> GetPathDFS(GameObject srcObj, GameObject dstObj)
   {
       // next steps
   }

2. Validate if input objects are null:

   if (srcObj == null || dstObj == null)
       return new List<Vertex>();

3. Declare and initialize the variables we need for the algorithm:

   Vertex src = GetNearestVertex(srcObj.transform...

Finding the shortest path in a grid with BFS

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

Getting ready

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.

How to do it...

Even though this recipe is only defining a function, please take into consideration the comments in the code to understand the indentation and code flow more effectively:

1. Declare the GetPathBFS function:

   public List<Vertex> GetPathBFS(GameObject srcObj, GameObject dstObj)
   {
       if (srcObj == null || dstObj == null)
           return new List<Vertex>();
       // next steps
   }

2. Declare and initialize the variables we need for the algorithm:

   Vertex[] neighbours;
   Queue<Vertex> q = new Queue...

Finding the shortest path with Dijkstra

The 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 with two different approaches.

Getting ready

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

For downloading the source file and more information regarding GP Wiki's binary heap, please refer to the documentation online available at http://content.gpwiki.org/index.php/C_sharp:BinaryHeapOfT.

How to do it...

We will learn how to implement the Dijkstra algorithm using the same number of parameters as the other algorithms, and then explain how to modify it to make maximum use of it according to its original purpose.

1. Define the GetPathDijkstra function with...

Finding the best-promising path with A*

The A* algorithm is probably the most-used technique for path finding, given its implementation simplicity, and 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 some roots with the Dijkstra algorithm, so you'll find similarities in their implementations.

Getting ready

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 for. 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.

In a nutshell, for the purpose of this recipe, a heuristic is a function for calculating the approximate cost between two vertices in order to compare them to other alternatives and take the minimum-cost choice.

We need to add small changes to the Graph class:

1. Define a member variable as delegate...

Improving A* for memory: IDA*

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.

Getting ready

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

How to do it…

This is a long recipe that can be seen as an extensive two-step process: creating the main function, and creating an internal recursive one. Please take into consideration the comments in the code to understand the indentation and code flow more effectively:

1. Let's start by defining the main function called GetPathIDAstar:

   public List<Vertex> GetPathIDAstar(GameObject srcObj, GameObject dstObj, Heuristic h = null)
   {
       if (srcObj == null || dstObj == null)
           return new List<Vertex>();
       if (ReferenceEquals(h, null))
           h = EuclidDist;
       // next steps;
   }

2. Declare and compute the variables to use along with the algorithm:

   List<Vertex...

Planning navigation in several frames: time-sliced search

When dealing with large graphs, computing paths can take a lot of time, even halting the game for a couple of seconds. This could ruins its overall experience, to say the least. Luckily enough there are methods to avoid this.

Note

This recipe is built on top of the principle of using coroutines as a method to keep the game running smoothly while finding a path in the background; some knowledge about coroutines is required.

Getting ready

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.

How to do it...

Even though this recipe is only defining a function, please take into consideration the comments in the code to understand the indentation and code flow more effectively:

1. Modify the Graph class and add a couple of member variables. One for storing the path and the other to know whether the coroutine has finished...

Smoothing a path

When dealing with regular-size vertices on 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.

Getting ready

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.

How to do it…

This is an easy, yet powerful, function:

1. Define the Smooth function:

   public List<Vertex> Smooth(List<Vertex> path)
   {
       // next steps here
   }

2. Check whether it is worth computing a new path:

   List<Vertex> newPath = new List<Vertex>();
   if (path.Count == 0)
       return newPath;
   if (path.Count < 3)
       return path;

3. Implement the loops for traversing the list and building the new path:

   newPath.Add(path[0]);
   int i, j;
   for (i = 0; i < path.Count - 1;)
   {
       for (j = i + 1; j < path.Count...