In this blog post, we’ll take a detailed look at the principles, features, and real-world applications of the A’ algorithm, which is used in games and various real-life fields.
“Hey, my Dragoons keep getting lost.”
While playing “StarCraft,” the real-time strategy simulation game that gained massive popularity worldwide, Jun-sang became curious about how the in-game units find their way. Pathfinding algorithms are used in games like this. In computer science, an algorithm refers to a clear and finite procedure that takes input and produces the desired output to perform a task or solve a problem. Therefore, a pathfinding algorithm literally refers to the process of finding the shortest path from a starting point to a destination. In this article, we’ll take a closer look at pathfinding algorithms and explore how they’re used not only in games but also in real life.
First, the pathfinding algorithm used in the aforementioned “StarCraft” is the A’ (pronounced “A-star”) algorithm. To briefly explain the concept of the A’ algorithm, it is a method in which a unit in the game starts from a departure point and moves incrementally in the most efficient direction by comprehensively considering the distances to the destination from surrounding points relative to the departure point. This process is repeated—calculating the most efficient direction from the current position—until the shortest path to the destination is found.
In computer science, the A’ algorithm is one of the most representative graph search algorithms for finding the shortest path from a given starting node to a destination node. The various methods for efficiently storing and utilizing data are collectively referred to as data structures, with graphs and trees being representative examples. A graph consists of vertices and the edges connecting them; the vertices are called nodes, and the edges are called edges. A tree is a type of graph that has a structure branching out in multiple directions from a single trunk, much like the branches of a tree. A search algorithm is an algorithm that explores data structures such as graphs and trees to find the desired information.
Looking more closely at search algorithms, among the various search methods, there are breadth-first search (BFS) and depth-first search (DFS). Breadth-first search is a method that first visits all adjacent nodes starting from the starting node. In contrast, depth-first search (DFS) selects one adjacent node from the starting node, explores it to its end, and then, when it can no longer proceed, returns to the previous node to explore other nodes that have not yet been visited.
The A’ algorithm combines the advantages of BFS and DFS while also using a heuristic value to estimate the shortest path for each node. A heuristic is a method of repeatedly making the choice deemed most appropriate at each step based on given information.
To explain the algorithm in detail, we first prepare two lists: the Open List, which stores nodes that have not yet been explored, and the Closed List, which stores nodes that have already been explored. The heuristic evaluation function used in the A’ algorithm is expressed as F = G + H. Here, G is the actual movement cost from the starting point to the current node, and H is the estimated movement cost from the current node to the destination. F is the total estimated cost, which is the sum of these two values. Movement cost refers, quite literally, to the cost, distance, or time required to move between points.
First, the starting point is added to the closed list, and adjacent reachable nodes are added to the open list. This is similar to the concept of breadth-first search. Subsequently, the F values of the nodes in the open list are calculated; the node with the lowest cost is moved to the closed list, and new reachable nodes from that node are added back to the open list. This process is repeated.
In an ideal environment, simply repeating this process would allow the algorithm to reach the destination. However, if an obstacle is encountered, a situation may arise where further movement is impossible, even if the total cost is low. In this case, the node is added to the closed list to prevent revisiting it, and the node with the lowest total cost among those in the open list is selected to continue the search. This process resembles the characteristics of depth-first search. Therefore, the A’ algorithm can be described as an algorithm that combines the characteristics of both breadth-first and depth-first search. By repeating this process, the destination node is added to the open list, and at that point, by backtracking through the closed list, the shortest path from the starting point to the destination can be determined.
Since its initial publication in 1968, the A’ algorithm has been widely used as a highly efficient algorithm in the field of pathfinding. Today, it is used as a core technology for finding the shortest path not only in the games mentioned earlier but also in various fields such as navigation, robot path planning, autonomous driving, and logistics systems. Having long been recognized for its outstanding performance and versatility, the A’ algorithm can rightfully be called the top star in the world of pathfinding algorithms.
