Path-finding is crucial for navigating efficiently in a virtual environment. The navigable areas are represented using graph nodes and edges, and the graph search algorithms are applicable. There are many different search algorithms available including Depth First Search, Breadth-First Search, Dijkstra’s and A* Algorithms. This article discusses which are best suited for agent navigation. The following are parts of the original article, check the main article for more details.
Dijkstra’s Shortest Path Algorithm
Dijkstra’s algorithm finds the shortest path (with the minimum cost) between a source node to every other node in a weighted graph. The graph must have non-negative edge costs for the algorithm to work. The algorithm can be stopped once the shortest path from the source node to the target node is determined, or else continued to find the shortest path to all the nodes of the graph.
Demonstrating step 3 of Dijkstra’s algorithm:
In order to illustrate the procedure of the Dijkstra’s Algorithm a simple graph is considered, as shown in the Figure above. The following procedure describes the steps this algorithm goes through to find the shortest path from the source node (A) to the target node (B) of this graph.
- Firstly, all the nodes are marked as unvisited and the source node (A) is considered as the current node.
- A distance value is assigned to each node, which indicates the distance of the node from (A). At the start, the distance value is set to ‘0’ for (A) and to infinity for all the other nodes.
- The algorithm considers all the unvisited adjacent nodes to the current node and calculates their preliminary distance to (A). For each unvisited node adjacent to the current node, the preliminary distance is calculated by adding the cost of the edge between these nodes with the distance value of the current node (as shown in the Figure below). If the newly calculated distance is less than the previously stored distance, it is considered the new distance value for this adjacent node.
- When all the adjacent nodes of the current node are checked, it is marked as visited. The visited nodes are in green and the current node is in grey (as shown in the Figure below). The visited nodes are not checked again and their distance is considered the minimal distance to (A).
- If the target has not been reached or all the nodes have not yet been visited, the algorithm moves to an unvisited node with the lowest distance value and considers it the current node. In other words, the closest node to the source is selected and is set as the current node. Then the same procedures from step 3 are repeated for the current node until the target node (B) is found or all nodes have been visited (as demonstrated in the Figure below).
The above Figure illustrates the rest of Dijkstra’s algorithm process for the graph showed earlier until all the nodes are visited (follow from left to right and top to bottom). When the search concludes, the shortest path from the source node to all the other nodes is found. Dijkstra’s algorithm is one of the most efficient graph search algorithms in weighted graphs with non-negative edge costs. Although this algorithm is faster than most of the other algorithms for graph traversal, it still examines a lot of edges.
Finding a path between A and B in a navigation graph using Dijkstra’s algorithm.
The Figure below illustrates how the shortest path is found in a navigation graph using this algorithm. It is assumed that the horizontal and vertical edges have a cost of ‘1’ and the diagonal edges have a cost of ‘1.4’, which is the approximate Euclidean distance between the nodes. The numbers on the nodes indicate their distance value from the source (A). The algorithm is ceased when the shortest path is found, which is indicated in red bold colour.
Finding the shortest path in a navigation graph can be optimised significantly using the A* Algorithm.
A* Shortest Path Algorithm
The A* algorithm is an extension of Dijkstra’s algorithm, which takes a heuristic value into account for selecting the nodes in the process of finding the shortest path. Different heuristic values can be used depending on the type of graph and the application. For example, in navigation graphs with tile-based topology, where movements are restricted to vertical and horizontal movements of equal length, the Manhattan distance can be considered as the heuristic value. This value is the distance between the source and target points measured along vertical and horizontal axes. In other words, this distance would be equal to the number of tiles that needs to be passed from the source to the target tile.
In a navigation graph where spatial information is available the Euclidean (straight-line) distance between source and target nodes is used as the heuristic value. In other words, the heuristic value is an estimate of the distance between source and target nodes. In the A* algorithm, the heuristic value is considered when calculating the preliminary distance of an unvisited node adjacent to the current node as explained in step 3 of Dijkstra’s algorithm. Therefore, A* calculates the preliminary distance by adding the cost of the edge between these nodes to the distance value of the current node and the heuristic value. As a result, fewer edges need to be examined and the algorithm converges more quickly to the best path.
As shown in the Figure above the A* algorithm finds the shortest path from source (A) to target (B) more efficient than the previously discussed algorithms. The yellow circles indicate the nodes visited along the shortest path, and the green circles indicate other visited nodes. The small number written at the top right of nodes is the Euclidean distance of that node from the target node (B).
The Figure above shows an agent in the developed simulated environment, which is using the A* algorithm in order to find the path from its base location to a resource item. Compared with other path-finding algorithms the A* algorithm is the most efficient algorithm to find the shortest path between two nodes in a weighted graph (with positive edge costs). However, in the case where there are multiple resources available, Dijkstra’s algorithm has proved to be more efficient for finding the closest resource.
Both A* and Dijkstra’s algorithms are used depending on the situation and actions required. For instance, in the case of a resource-gathering simulation when an agent collects an item at a specific location or needs to travel between two specific points, the A* algorithm is best used to find the shortest path. On the other hand, when the agent needs to find the closest item to navigate to and collect then Dijkstra’s algorithm is best to be used. That is because when the virtual world contains multiple resources of the same type spread throughout the environment, by using Dijkstra’s algorithm, only one instance of the searching algorithm would be enough to find the closest item from all the available items.
Path Smoothing Algorithm
A twist to the A* algorithm would make the movement of agents smoother. A path-smoothing algorithm is implemented in order to remove unnecessary edges from the path and therefore avoid the zigzag movements as shown in the Figure above. This algorithm checks the adjacent edges of the path and replaces them with one edge from the source of the first adjacent edge to the destination of the second adjacent edge if there is a possible direct link between them. It repeats this until all the adjacent edges are examined. The result creates a smoother and more efficient path as shown in the Figure below.
References:
- J. L. Gross and J. Yellen. Handbook of Graph Theory. CRC Press, 2004.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press and McGraw-Hill, 2nd edition, 2001.
- S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Pearson Education, Inc., Upper Saddle River, NJ, USA, 2nd edition, 2003.
- M. Buckland. Programming Game AI by Example. Wordware Publishing, Inc., Plano, Texas, USA, 2005.
- R. Bhandari. Survivable Networks: Algorithms for Diverse Routing. Springer, 1999.
- E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, Springer Berlin, Heidelberg, Germany, 1:269–271, 1959.
- P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics SSC4, 4(2):100–107, July 1968.
