August 1, 2010 at 14:16Comparison of route search algorithms in StarCraft and StarCraft 2
Those who played the beta version of Starcraft 2 probably noticed how the algorithm for finding unit movement paths has changed. Much of what was said in the article is based on personal assessments. I did not program either BroodWar or StarCraft 2, and some conclusions will be based on my guesses. Also, do not believe 100% in my words, try to draw your own conclusions. The article will include both facts and speculation.
Translation of The Mechanics of Starcraft 2 Pathfinding
StarCraft 2 uses an algorithm for finding paths called “flocking” or “swarm AI” (swarm behavior, approx. Per.), Which attempts to coordinate the movement of units according to the type of movement of a school of fish or flocks of birds. It is very likely that StarCraft 2 uses an advanced algorithm that finds the minimum number of control points and allows units to independently lay a smooth route to bypass obstacles or other units.
In terms of the result, Blizzard did a great job on the algorithm. Of course, this is a closed area and there is no detailed information about it. But the fact that 200 units move around the map flawlessly suggests that the algorithm works efficiently. Great efforts are spent on such technologies in the gaming community, and therefore Blizzard could not ignore this problem. When I started playing BroodWar, I spent a lot of time trying to figure out how it works.
Finding paths in BroodWar works a little differently. On an isometric map, a unit can only move in 8 directions, and you should not spend a lot of processor time on the algorithm. Therefore, the route search algorithm in this situation can be based on the A * algorithm (A-Star - wave algorithm) and, looking at the movement of units, I think this assumption is very close to the truth.
Application of the A-Star algorithm in broodWar
What a player sees in this situation The
map is covered with a large number of nodes, like a tile. Once in a node, the unit knows where to move on (each node is associated with possible directions of movement), and so on, until it reaches its destination. The nodes through which the unit has passed become reference points. But StarCraft 2 avoids collisions by bypassing other units along a small radius route, and in BroodWar units compete for nodes. This is the main reason why you get a better environment in StarCraft 2 than in BroodWar, but there is also the opposite effect: units run away when moving towards each other.
Mutalisks choose different anchor points if they are rotated 180 degrees.
An attempt to simulate the BroodWar algorithm by setting a large number of key points
The difference is that in BroodWar units use, according to the A * algorithm, the same key points, moving step by step. And in StarCraft 2, a separate route is calculated for each unit and the minimum number of nodes is used.
In BroodWar, collision protection is also more primitive. The unit avoids collisions due to the fact that it stops and passes another, or calculates a new route of movement. In BroodWar, when reconnaissance by workers, you can often see a situation where one player stops the scout with his unit, and the other tries to get around the obstacle, or both players try to detain each other in this way.
In StarCraft 2, units avoid collisions and avoid obstacles by changing the route. It is logical to assume that each unit has a collision sensor, which at the right time will signal to bypass the obstacle. It also allows units to merge together or vice versa to separate without calculating a complete new path or loss of momentum. In the worst case, units can ignore the radius of the collision, thereby providing smoother movement and better overall movement efficiency.
OpenSteer :
BroodWar’s Zerg open source library for avoiding obstacles decides who runs first. And in StarCraft 2, zerg begin to unfold in advance.
A lot of BroodWar fans don't like the new algorithm, and there is a reason. One of the most effective tactics at the beginning of the game is bypass and environment. But, if enemy units move close to each other, then the environment will not be so effective. Zerglings do so much damage to marinas when they are not standing in a heap, because marinas attack from a distance, but zerglings do not. If you reduce the "surface area" of your army (for example, place it in the shape of a circle), then the units will receive much less damage. Accordingly, the larger the army, the greater the effect of such tactics.
Flash vs Effort (OSL 3rd final game). Flash's marinas are far enough apart. Therefore, the zerglings running from the flank killed them. It cost Flash a victory.
Another question is that, ideally, the amount of effort spent on moving a unit should directly correlate with its effectiveness. Those. players who do not control their units must be punished for this. But it seems that in Starcraft 2, the algorithm can control units better than the player, which means that you will get the opposite effect from your actions.
I believe that the “wrong movement” of the unit can disrupt the plans of newcomers, and for Blizzard there is nothing worse than showing that the game is imperfect. I also believe that units should run away when they are carelessly controlled, and vice versa. You should not force people to “struggle with the interface” in order to create a balance in the game.
On my own, I’ll add that from a mathematical point of view, Blizzard has developed a very good algorithm. They would have published it.
Note: the article was written before the official release of SC2
Translation of The Mechanics of Starcraft 2 Pathfinding
Route search
StarCraft 2 uses an algorithm for finding paths called “flocking” or “swarm AI” (swarm behavior, approx. Per.), Which attempts to coordinate the movement of units according to the type of movement of a school of fish or flocks of birds. It is very likely that StarCraft 2 uses an advanced algorithm that finds the minimum number of control points and allows units to independently lay a smooth route to bypass obstacles or other units.
In terms of the result, Blizzard did a great job on the algorithm. Of course, this is a closed area and there is no detailed information about it. But the fact that 200 units move around the map flawlessly suggests that the algorithm works efficiently. Great efforts are spent on such technologies in the gaming community, and therefore Blizzard could not ignore this problem. When I started playing BroodWar, I spent a lot of time trying to figure out how it works.
Finding paths in BroodWar works a little differently. On an isometric map, a unit can only move in 8 directions, and you should not spend a lot of processor time on the algorithm. Therefore, the route search algorithm in this situation can be based on the A * algorithm (A-Star - wave algorithm) and, looking at the movement of units, I think this assumption is very close to the truth.
Application of the A-Star algorithm in broodWar
What a player sees in this situation The
map is covered with a large number of nodes, like a tile. Once in a node, the unit knows where to move on (each node is associated with possible directions of movement), and so on, until it reaches its destination. The nodes through which the unit has passed become reference points. But StarCraft 2 avoids collisions by bypassing other units along a small radius route, and in BroodWar units compete for nodes. This is the main reason why you get a better environment in StarCraft 2 than in BroodWar, but there is also the opposite effect: units run away when moving towards each other.
Mutalisks choose different anchor points if they are rotated 180 degrees.
An attempt to simulate the BroodWar algorithm by setting a large number of key points
The difference is that in BroodWar units use, according to the A * algorithm, the same key points, moving step by step. And in StarCraft 2, a separate route is calculated for each unit and the minimum number of nodes is used.
Collision Protection
In BroodWar, collision protection is also more primitive. The unit avoids collisions due to the fact that it stops and passes another, or calculates a new route of movement. In BroodWar, when reconnaissance by workers, you can often see a situation where one player stops the scout with his unit, and the other tries to get around the obstacle, or both players try to detain each other in this way.
In StarCraft 2, units avoid collisions and avoid obstacles by changing the route. It is logical to assume that each unit has a collision sensor, which at the right time will signal to bypass the obstacle. It also allows units to merge together or vice versa to separate without calculating a complete new path or loss of momentum. In the worst case, units can ignore the radius of the collision, thereby providing smoother movement and better overall movement efficiency.
OpenSteer :
BroodWar’s Zerg open source library for avoiding obstacles decides who runs first. And in StarCraft 2, zerg begin to unfold in advance.
A lot of BroodWar fans don't like the new algorithm, and there is a reason. One of the most effective tactics at the beginning of the game is bypass and environment. But, if enemy units move close to each other, then the environment will not be so effective. Zerglings do so much damage to marinas when they are not standing in a heap, because marinas attack from a distance, but zerglings do not. If you reduce the "surface area" of your army (for example, place it in the shape of a circle), then the units will receive much less damage. Accordingly, the larger the army, the greater the effect of such tactics.
Flash vs Effort (OSL 3rd final game). Flash's marinas are far enough apart. Therefore, the zerglings running from the flank killed them. It cost Flash a victory.
conclusions
Another question is that, ideally, the amount of effort spent on moving a unit should directly correlate with its effectiveness. Those. players who do not control their units must be punished for this. But it seems that in Starcraft 2, the algorithm can control units better than the player, which means that you will get the opposite effect from your actions.
I believe that the “wrong movement” of the unit can disrupt the plans of newcomers, and for Blizzard there is nothing worse than showing that the game is imperfect. I also believe that units should run away when they are carelessly controlled, and vice versa. You should not force people to “struggle with the interface” in order to create a balance in the game.
On my own, I’ll add that from a mathematical point of view, Blizzard has developed a very good algorithm. They would have published it.
Note: the article was written before the official release of SC2