This article explains why the Dragoon unit in the game StarCraft gets lost in narrow entrances, and shows that it’s not a flaw in the game’s artificial intelligence, but rather the nature and limitations of the Asta algorithm. We’ll cover the basic principles of the Asta algorithm and how it applies to games and real-world scenarios, as well as the issues that can arise.
A group of units are passing through a narrow entrance. At first, they seem to pass through in a single file, but soon a few units break away from the line and move around in a disorganized fashion. They go as far as they can and then turn back. This phenomenon can be seen in Starcraft, a popular strategy game from the 2000s. One unit in particular, the Dragoon, is particularly notable for its ridiculous movements, earning it the unfortunate nickname of “garbage AI”. While the game’s players may have seen the wandering Dragoon and thought it was a sign of poor AI, the phenomenon actually stems from the nature of StarCraft’s wayfinding algorithm, the A* algorithm.
The A* algorithm is a type of wayfinding algorithm that finds the shortest distance between a starting point and a destination. A typical wayfinding algorithm doesn’t take into account information about the destination as part of the navigation process, but instead starts from a starting point and follows the shortest path in all directions, eventually reaching the destination. The ASTA algorithm, on the other hand, knows the location of the destination in advance and uses that information to estimate and find the shortest path. This method is called a “heuristic” technique. Heuristics are often used in real-world programs because they can speed up the algorithm and reduce its cost. The Asta algorithm is over 50 years old, but its effectiveness has been recognized and it is still widely used in most games today.
There are three prerequisites for the ASTA algorithm to work First, the area to be explored must have a grid structure, such as a square or hexagon, so that the path from the starting point to the destination can be represented as a continuous set of “grid cells”. Second, each grid cell has one of two states. It is either ‘accessible’ or ‘inaccessible’. Third, in order to apply the heuristics, we need to know the current location and the location of the destination (via coordinates).
The ASTA algorithm is like the process of connecting two separate puzzle pieces on a large puzzle board with a minimum number of pieces. The puzzle must also fulfill the three conditions described above. First, the puzzle board has a lattice structure. A puzzle piece is a grid cell, and the two given puzzle pieces are the start and end points. The puzzle pieces that connect them can be seen as a set of lattice squares, or paths. Second, if a puzzle piece is missing, it can’t be a path, so it represents an “inaccessible” state. Third, we can look at the picture printed on the puzzle box to see where the current puzzle piece is and where the destination puzzle piece is.
The ASTA algorithm uses a concept called “cost of the lattice” to find a “reasonable” path. The cost of the lattice (F) is the distance (G) from the starting point to the corresponding square plus the estimated distance (H) from the square to the destination. The choice with the minimum F value is called a rational path. The H value is obtained using a heuristic technique and is calculated based on the given coordinate information. It is an ‘estimated value’ that may differ from the actual length of the path because it does not take into account ‘inaccessible’ conditions. For example, if a piece of a puzzle has a missing piece on its path to the destination, it will require more pieces to reach the destination because the puzzle will have to be reassembled around the missing piece. The value of H can be anything from a simple straight line distance to a complex calculation, and the value you choose will greatly affect the performance of the Asta algorithm.
While efficient at finding the shortest path, this can be problematic in games where the environment changes in real time. This is because, like a puzzle, the ASTA algorithm finds the shortest distance while the objects are “fixed,” so it can’t respond to real-time changes in the starting point, destination, or “inaccessible” areas.
The phenomenon of Dragoon getting lost mentioned at the beginning of this article is also due to this limitation. In a game like StarCraft, where units can’t stack on top of each other, each unit itself is an “inaccessible” area. When a large group of units, such as the Dragoon, passes through a narrow entrance, the entrance that is “accessible” when all of the grid spaces are occupied is suddenly perceived as an “inaccessible” wall. If the following Dragoon uses the Asta algorithm to find a path, it may find a different, longer path, or it may think there is no path at all and go in the wrong direction. The most effective way to fix this is something most users know instinctively. The most effective way to fix this is something most users know instinctively: click your mouse quickly several times to rerun the Asta algorithm over and over again until your Dragoon finds the correct path.
Asta algorithms are not only used effectively in games, but also in real-world applications such as navigation. For example, StarCraft uses a simple map of 10,000 grids, but for navigation, it uses real-world maps with countless grids. In this case, the strengths of heuristics in terms of speed and cost savings are even more pronounced. When solving a 9-piece puzzle, it’s easy to complete the puzzle without knowing the whole picture, but when solving a 1000-piece puzzle, it’s much more effective to know the big picture.
This is how the Asta algorithm is the master of directions, responsible for most of the world’s directions services. The proliferation of smartphones has made maps portable and directions ubiquitous, making it even more influential. After half a century of reigning as the king of directions, the Asta algorithm is here to stay.
