Pathfinding, A* Search and Dijkstra Algorithm

Pathfinding

There is a well-known pathfinding problem called the Travelling Salesmen Problem (TSP), a problem which has confused mathematicians for years. (Freiberger, 2012) defines the problem with the following analogy: “Get cash from the cash point, go to the supermarket, pick up kids from school and prescription from doctor. In what order should you do these things so that the distance you've got to drive is as short as possible?”  This is something we do in our day-to-day lives – we perform multiple tasks, but the heuristics don’t seem to bother us that much. We think about things in a logical way naturally, but we only do things in a way that seems naturally logical. When we are telling a machine to compute the fastest route, we need to involve factors that will produce the fastest route. As outlined by Freiberger, getting to all those places might not be challenging. However, if you add in hundreds or even thousands of nodes then the problem becomes computationally harder.

Dijkstra’s Algorithm

Dijkstra’s algorithm, also known as Dijkstra’s shortest path, is one of the most commonly used algorithms. It uses a best-search function which prioritises routes with the shortest cost first. This algorithm attempts to solve the TSP but there is just one major flaw with it: it’s too greedy.

Figure 3: Greedy Algorithms (Moore & Ross, 2017)

Greedy is a term that is used to describe the optimality of an algorithm. All routes have a cost associated with them. Let’s look at the above image [fig. 3]. This shows two different paths, but the aim is to find the largest sum. Greedy algorithms don’t analyse the route, but rather individual nodes. This means that the path found would be [A > C > G] instead of the correct path which would be [A > B > D]. [A > B > D] has a total sum of 109, while [A > C > G] has a total sum of 25. This algorithm is appropriate to use in situations only where one solution should exist, or used as a baseline to be expanded upon. This is because it “makes decisions based only on the information it has at any one step, and without regard to the overall problem” (Moore & Ross, 2017).

In a gaming environment, Dijkstra’s algorithm can be applied to pathfinding for AI, but there may be instances where the route chosen could appear as strange and unnatural. This is because the algorithm itself does not account for heuristics, only cost. To illustrate, (Computerphile, 2017) provides the analogy of using roads (see [fig. 4]).

Figure 4. Dijkstra’s Algorithm – Computerphile

(Computerphile, 2017)

He states that he is starting at [S] and travelling to [E]. He must travel through [A], and all the nodes below it contains traffic jams (increasing the route cost). Because of this it will search all the nodes above [A] before realising there are no through routes to get to [E]. Even if there was, at this point it could end up making the route longer. Pathfinding in games should be as optimised as possible, therefore unnecessary route finding should be kept to a minimal. The application of Dijkstra is more suitable for a linear graph, where nodes commonly have one or two connections.

A* Algorithm

This is where the A* algorithm (also known as A* search algorithm) is applied. A* algorithm is an adaptation of the Dijkstra’s algorithm. A* combines cost-driven and heuristic-driven algorithms to produce an algorithm that considers both cost and distance / direction. This has the added advantage that it eliminates one of the main problems of Dijkstra’s algorithm: it will consider how far away it is from the target. (Computerphile, 2017) explains the problem with Dijkstra’s algorithm using this example [fig. 5]. [S] is the node which the agent would start at, and [E] is the goal. The highlighted nodes are the areas which Dijkstra would search in before reaching the goal. A* would take the most optimal path, which would head straight down all of the nodes, to the right once, and then to [E].

However, this can have a considerable drain on the CPU and its application would not be applicable for games that feature very simple map designs.

On the other hand, maps with a complex design that have many possible routes to reach the target would be more suitable for the application of the A* algorithm. (Dennis, 2008) explains how he took on a programming challenge: “The object was to find the lowest cost route between 10 cities encoded in a map of integers. Each integer represented the cost to get from that any adjacent location to that spot. This is a classic case of a graph navigation algorithm.” In this case he found that the A* algorithm was the most suited to his task. This considerably cut down the time to reach his goal but added to the build time.

Figure 5. A* (A Star) Search Algorithm – Computerphile 

(Computerphile, 2017)

In summary, I believe that for more linear paths, Dijkstra’s algorithm is more suited. Dijkstra is much better at analysing paths when there aren’t multiple variables that can affect the cost routes of each path, and if they aren’t constantly changing. The A* algorithm is much better for these larger grid search calculations, such as in satellite navigation, where the route can change based on multiple factors.