This blog post analyzes the StarCraft Dragoon pathfinding problem and examines whether its cause stems from limitations of the A* algorithm.
Multiple units are passing through a narrow entrance. At first, they appear to pass smoothly in a single file, but soon some units break formation, lose their bearings, and move erratically. They wander aimlessly, sometimes traveling far only to turn back. This phenomenon is commonly observed in the famous strategy game ‘StarCraft,’ which dominated the 2000s. Particularly, the game’s ‘Dragoon’ unit, with its uniquely comical movements, made this phenomenon stand out even more, earning it the infamous nickname ‘garbage AI’. While gamers watching the erratic Dragoons thought “the AI’s sophistication is lacking,” this behavior actually stems from the characteristics of the pathfinding algorithm used in StarCraft: the ‘A* algorithm’.
The A* algorithm is one type of pathfinding algorithm that seeks the shortest distance between a starting point and a destination. Conventional pathfinding algorithms do not specifically consider information about the destination during the search process. Instead, they start from the origin and branch out in all directions along the path with the shortest distance, eventually reaching the destination. In contrast, the A* algorithm knows the destination’s location in advance and estimates the shortest path based on that information. This method is called a ‘heuristic technique’. Heuristic techniques improve algorithm speed and reduce costs, making them widely used in actual programs. Although the A* algorithm was devised over 50 years ago, its efficiency is recognized, and it remains widely used in most games today.
Three prerequisites are necessary for applying the A* algorithm. First, the search area must be structured as a grid, such as squares or hexagons. Therefore, the path from the starting point to the destination can be represented as a sequence of ‘grid cells’. Second, each grid cell has one of two states: ‘accessible’ or ‘inaccessible’. Third, to apply heuristic techniques, the current position and the destination’s position must be known, typically through coordinates.
The A* algorithm is akin to connecting two distant puzzle pieces on a large board using the fewest possible connecting pieces. Puzzles also satisfy the three conditions described above. First, the puzzle board has a grid structure. Each puzzle piece is one grid cell, and the two given puzzle pieces represent the starting point and destination. The puzzle pieces connecting them can be seen as a set of grid cells, i.e., a path. Second, if a puzzle piece is missing, it cannot be part of the path and thus represents an ‘inaccessible’ state. Third, we can determine the current puzzle piece’s location and the destination puzzle piece’s location by looking at the printed image on the puzzle box.
The A* algorithm uses the concept of ‘grid cost’ to find a ‘reasonable’ path. The grid cost (F) is the sum of the distance (G) from the starting point to the current cell and the estimated distance (H) from the current cell to the destination. The choice with the minimum F value is considered the rational path. The H value is obtained through a heuristic technique, calculated based on given coordinate information. Since ‘inaccessible’ states are not considered, it is an ‘estimated value’ that may differ from the actual path length. For example, if a lost piece lies on the path to the destination in a puzzle, the puzzle must be assembled by bypassing that piece, requiring more pieces to reach the destination. The H value can range from simple straight-line distances to complex calculated values, and the performance of the A* algorithm varies significantly depending on which value is adopted.
Even the A* algorithm, which efficiently finds the shortest path, can cause problems in games where the environment changes in real time. This is because the A* algorithm calculates the shortest distance in a ‘fixed state’ scenario, like solving a puzzle. Therefore, it cannot handle situations where the starting point, destination, or ‘inaccessible’ areas change in real time.
The phenomenon of Dragoons getting lost, mentioned at the beginning of this article, also stems from this limitation. In games like StarCraft, where units cannot overlap, the unit itself becomes an ‘inaccessible’ area. When multiple large units like Dragoons pass through a narrow entrance, if all the grid cells at the entrance are occupied, the ‘accessible’ entrance is momentarily perceived as an ‘inaccessible’ wall. At this point, if the following Dragoons use the A* algorithm to find a path, they may find a completely different, distant route or determine there is no path, leading them to move in the wrong direction. The most effective solution to this problem is something most users instinctively know: rapidly clicking the mouse multiple times to continuously re-execute the A* algorithm until the Dragoons find a normal path.
The A* algorithm is effectively used not only in games but also in real-life applications like navigation systems. For instance, StarCraft uses a simple map composed of about 10,000 grid cells, whereas navigation systems use actual maps composed of countless grid cells. In this case, the strengths of heuristic techniques—speed improvement and cost reduction—become even more pronounced. When assembling a 9-piece puzzle, you can easily complete it without knowing the entire picture. However, when assembling a 1,000-piece puzzle, knowing the big picture is far more effective.
Thus, the A* algorithm is the master of pathfinding, handling most of the world’s route-finding services. With the proliferation of smartphones enabling the portability of maps and the availability of route-finding services anywhere, the master’s influence continues to grow. Having reigned supreme in pathfinding for half a century, the A* algorithm will likely hold that position for a long time to come.
