How excellent was Red Dead Redemption 2? Vivid landscapes with an artistic touch almost like an oil painting on a canvas, meets with the state of the art computation techniques to create an immersive gaming experience. I have to say, it is also not that bad to be able to write a story on these games once I have truly cherished. No no, this post will not be about Red Dead Redemption. I just couldn’t have missed the opportunity.
Today, we are going to talk about pathfinding. And not just in games, but about pathfinding in general. We will start by discussing games and how game worlds are represented in this context. Once we reduce our game world to the generic pathfinding problem, we will be investigating different algorithms and compare how well they perform under different circumstances.
Pathfinding algorithms aim to find the shortest path between two given points. Many games include some sort of pathfinding mechanism, some are simple, and some are much more advanced. These mechanisms are mainly utilized in agent (characters, NPCs, animals or vehicles) movement and can be critical in terms of realistic artificial intelligence feeling.
Remember the auto travel feature while you are riding your horse to the next quest marker in games like Red Dead Redemption and Assassin’s Creed? That is a very common application of the pathfinding mechanism in games.
The first question we need to answer is how to represent the game world. The environment is seemingly continuous (it is not but it feels like it is) with roads, hills, valleys and obstacles along the way. We want to run some sort of search algorithm on the game world to find the best route, but it is not a very easy task unless we find a way to represent the world as a discrete set of locations. Luckily, we can.
Navigation Meshes
Representing the real world in a digital environment was one of the most interesting subjects for me during my university years. You see, the entities in the real world are continuous and can be divided into presumably infinitely smaller pieces, from atoms to even smaller subatomic particles. In a computer environment, however, you have limited space to represent things. No matter how realistic your game looks, you are limited by the number of pixels on the screen.
In computer graphics (along with other study areas), we use polygonal meshes to model real-world entities. A mesh is the subdivision of a continuous geometric space into discrete geometric entities. Big words, huh? Just check the image below, this bunny is very famous. The most common shapes used in the mesh generation process are triangles and quadrilaterals. As you increase the number of subdivisions (using smaller shapes), you get a smoother representation of your subject.
A navigation mesh is a polygonal mesh that is specifically used to represent the traversable area to be later used in pathfinding. The traversable area is simply divided into convex polygons. The process of dividing a surface into smaller polygons is called tessellation. Each polygon shares an edge with the neighbouring polygons, which means that you can walk between them.
If you take each cell (polygon) and assign a node to the centre of gravity in that cell, you will obtain the Voronoi diagram of the mesh. You need to use convex polygons in this process, otherwise, the assigned nodes may end up outside the corresponding polygon. If you connect the nodes in neighbour cells, you will end up with the dual graph of the mesh.
I know these are a terrible bunch of drawings but come on, dig deep! Now we have a bunch of locations and paths that we can navigate between, instead of the terrain data with no directions. All there is left to do is to find the shortest path between the green and red nodes.
Path Finding Algorithms
Now that we reduced our problem to a graph search, we can turn our focus on the path-finding algorithms.
The problem at hand is no longer any different than the generic path-finding problem. In this section, we will go through a bunch of different solutions and try to find the most suitable one.
Breadth First Search and Depth First Search
Let’s face it from the beginning: We will not be going with BFS or DFS. Nevertheless, they are good for introductory reasons. Both algorithms do a very simple thing and that is to visit every single node on the graph until the destination node is reached. They are exhaustive algorithms, meaning they are not very efficient. In fact, using DFS doesn’t even make sense in this context, since it does not find the shortest path.
Instead, let’s focus on the BFS algorithm. It starts from the given node and checks all the neighbouring nodes until the destination is reached. Since it always checks the closest nodes first, it will always return the optimum solution, as long as the edges are not weighted (more on this later).
I am assuming that most of you are already familiar with BFS and DFS algorithms, so I am keeping this part short. If you are unfamiliar with the algorithms though, you may benefit from stopping here for a moment and doing a quick internet search on how these algorithms work. Here is how you can implement BFS using a queue.
Breadth-First-Search(Node start, Node destination) Queue queue;
queue.enqueue(start);
start.visited = true; while !queue.empty() Node current = queue.front();
queue.dequeue(); if current == destination
return for each neighbor of current node
if !neighbor.visited()
queue.enqueue(neighbor)
neighbor.visited = true
Dijkstra’s Algorithm
BFS is very simple to implement, yet it assumes that each path has the same cost. The paths in our problem though, do not have the same cost: some take longer to traverse than others. A good path-finding algorithm shall find the path with the lowest cost so that you don’t get bored while travelling. Unless you like the detour…
We can overcome this issue with Dijkstra's algorithm. In Dijkstra's algorithm, we start from the player’s current location and keep track of the reachable nodes, along with the cost to reach that node. In the first step, only the immediate neighbours can be reached but as you search through the neighbours, the other nodes will become accessible.
So, we begin our search from the starting point and at each step we pick the closest node that is reachable so far. Once a node is reached, its neighbours also become reachable if they were not before and the distances to its unvisited neighbours are updated with the minimum cost path we have seen so far. At the end of the algorithm, we will have the minimum cost paths to all the nodes in the graph.
Dijkstra(Graph graph, Node start, Node destination) for all nodes in the graph
node.cost = INT_MAX start.cost = 0
start.visited = true visitedCount = 1
while visitedCount < graph.size Node min = findMinUnvisited(Graph graph)
for each neighbor of current node
if !neighbor.visited
neighbor.cost = min(neighbor.cost, min.cost + edge) min.visited = true
visitedCount++; return destination.cost
For the sake of simplicity, I assumed that nodes numbered from 1 to n. The performance of the algorithm can be improved using a priority queue to instantly reach the node with the lowest cost. I omitted that part since we are not interested in the runtime analysis at the moment.
Best-First Search
Both algorithms we have seen so far suffer from the same problem: They search the entire graph. We don’t necessarily need to do that, though. Both algorithms assume that our search is uninformed — that we have no prior knowledge about where our destination is. We are informed though, we know that whether our destination is to the east or west, north or south. Think about it, would you start riding the south if your next quest marker flashes on the northern side of your minimap?
The best first search is a greedy algorithm that utilizes this idea and it has a very simple logic. First, we need to define a heuristic function. In our case, Euclidian distance can be used as an estimated difference to our goal but different scenarios work well with different heuristic functions. The algorithm chooses to move to the node with the lowest heuristic value until the destination is reached.
Best-First-Search(Node start, Node destination) PriorityQueue pq // lowest cost node at top
pq.push(start)
set start.visited = true while !pq.empty() Node current = pq.front()
pq.pop() if current == destination
return for each neighbor of current node
if !neighbor.visited()
pq.push(neighbor)
set neighbor.visited = true
The priority queue in this pseudocode is configured with a heuristic function that we chose. Thus, the node at the front of the queue is always the one that can be reached with the lowest cost at any given point. If you compare the pseudocode with BFS, you can see that the only real difference is how you configure a priority queue with the chosen heuristic function.
A* Search
Unsurprisingly, the best-first search also has a shortcoming: It doesn’t necessarily find the shortest path. Just like its name, the A* algorithm is the star of this post and is widely used in path-finding problems. We will continue using the Euclidian distance heuristic from the previous algorithm. Additionally, we will use the actual costs of the edges on the graph to create a more solid ground. So, let’s define a function f(n)
where cost(n) is the actual cost (weight of the edge) of moving from node A to node B. h(n) is the result returning from our heuristic function, when we are at node B. Pseudocode is not that different from the previous ones, just the heuristic function is changed.
A*(Graph graph, Node start, Node destination) PriorityQueue pq // f(n) = cost(n) + g(n)
for each node in graph
pq.push(node) set start.cost = 0
set start.f = start.h while !pq.empty() Node current = pq.front()
current.visited = true
pq.pop() if current == destination
return for each neighbor of current node
if !neighbor.visited()
g = weight of edge + current.g
if g < neighbor.g
neighbor.g = g
neighbor.f = g + neighbor.h
A* is a very efficient algorithm but it is highly dependent on how well the heuristic function is defined. With a good heuristic function, it can guarantee to find the shortest path but you need to understand that not all heuristic functions necessarily return the shortest path. Nevertheless, it is your go-to option and it is widely used in games due to its high performance and optimality.
If you have difficulty understanding these algorithms, I found this amazing website during my research. You can find there wonderfully well-made animations for the path-finding algorithms we have seen and I really advise you to check it out. I‘ll probably add another entry to my algorithms series for the implementations of these algorithms later but I wanted to keep this post as short as possible for the time being.
What started as a graphics post suddenly turned into an algorithms post, weird. By the way, am I the only one still feeling bad for Arthur?
