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
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.
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:
Create the backbone with the member values:
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.
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:
Prepend the VertexReport
class to the Graph
class specification, in the same file:
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.
Just like the previous representation, it's important to have several things in order before continuing:
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.
We'll be creating the graph representation class as well as a custom Vertex
class:
Create the VertexVisibility
class deriving from Vertex
:
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.
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
:
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.
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
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:
Declare the GetPathDFS
function:
Validate if input objects are null:
Declare and initialize the variables we need for the algorithm:
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.
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 take into consideration the comments in the code to understand the indentation and code flow more effectively:
Declare the GetPathBFS
function:
Declare and initialize the variables we need for the algorithm:
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.
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.
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.
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.
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:
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.
For this recipe, it is important to have some understanding of how recursion works.
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:
Let's start by defining the main function called GetPathIDAstar
:
Declare and compute the variables to use along with the algorithm:
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.
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.
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:
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...
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.
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:
Define the Smooth
function:
Check whether it is worth computing a new path:
Implement the loops for traversing the list and building the new path: