Comparison of route search algorithms in StarCraft and StarCraft 2
Those who played in the beta version of Starcraft 2 probably noticed how the algorithm for finding ways of movement of units has changed. Much of what has been said in the article is based on personal evaluations. I have not programmed either BroodWar or StarCraft 2 and some conclusions will be based on my guesses. Also, do not believe 100% of my words, try to make your own conclusions. The article will be both facts and conjectures.
Translation of the article The Mechanics of Starcraft 2 Pathfinding
StarCraft 2 uses an algorithm for finding paths called “flocking” or “swarm AI” (swarm behavior, approx. Lane), which tries to coordinate the movement of units according to the type of movement of a school of fish or a flock of birds. It is very likely that StarCraft 2 uses an advanced algorithm that finds the minimum number of anchor points and allows units to independently create a smooth route to bypass obstacles or other units.
')
In terms of the result achieved, 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. On such technologies, large forces are spent in the gaming community, and therefore Blizzard could not get around this problem side. 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 move only in 8 directions and a lot of processor time should not be wasted on the operation of 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.
The use of the A-Star algorithm in broodWar
What the player sees in this situation
The map is covered with a large number of nodes, according to the type of tile. When a unit arrives at a node, it knows where to go next (each node is associated with the possible directions of movement), and so on until it reaches its destination. The nodes through which the unit passed become reference points. But StarCraft 2 allows you to avoid collisions by avoiding other units along a small radius route, and in BroodWar, units compete for knots. 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 scatter when moving towards each other.
Mutalisks choose different control points if they are rotated 180 degrees
Attempt to simulate the BroodWar algorithm by specifying a large number of key points
The difference is that in BroodWar, units use, according to algorithm A *, the same key points, moving step by step. And in StarCraft 2 for each unit a separate route is calculated 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 misses another, or calculates a new route of movement. In BroodWar, when working as an explorer, you can often see a situation where one player stops a scout with his unit and another tries to circumvent the obstacle, or both players try to hold each other 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 moment will give a signal to bypass the obstacle. It also allows units to merge together or, on the contrary, split up without calculating a complete new path or loss of momentum. In the worst case, units can ignore the collision radius, thereby providing smoother movement and higher movement efficiency in general.
OpenSteer : an open source library to bypass obstacles
BroodWar'r zerg decide who will run first. And in StarCraft 2, zerg begin to unfold in advance.
A large number of BroodWar fans do not like the new algorithm, and for good reason. One of the most effective tactics at the beginning of the game is a detour and an environment. But, if enemy units move close to each other, the environment will not be as effective. Zerglings do so much damage to marines when they don’t stand in a heap, because marinas attack from a distance, but zerglings don’t. If you reduce the "surface area" of your army (for example, arrange it in the form of a circle), the units will receive much less damage. Accordingly, the larger the size of the army, the greater the effect of such tactics.
Flash vs Effort (OSL 3rd final game). Marina Flash'a are located far enough from each other. Therefore, zerglings who ran from the flank killed them. It was worth winning to Flash.
Another issue is that, ideally, the amount of effort spent on the movement of a unit should directly correlate with its effectiveness. Those. Players who do not control their units should 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 a unit can disrupt the plans of beginners, 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 casually managed, and vice versa. You shouldn’t force people to “fight the interface” to create balance in the game.
I'd add that in terms of mathematics, Blizzard has developed a very good algorithm. Still they published it.
Note: the article was written before the official release of SC2
Translation of the article The Mechanics of Starcraft 2 Pathfinding
Route search
StarCraft 2 uses an algorithm for finding paths called “flocking” or “swarm AI” (swarm behavior, approx. Lane), which tries to coordinate the movement of units according to the type of movement of a school of fish or a flock of birds. It is very likely that StarCraft 2 uses an advanced algorithm that finds the minimum number of anchor points and allows units to independently create a smooth route to bypass obstacles or other units.
')
In terms of the result achieved, 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. On such technologies, large forces are spent in the gaming community, and therefore Blizzard could not get around this problem side. 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 move only in 8 directions and a lot of processor time should not be wasted on the operation of 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.
The use of the A-Star algorithm in broodWar
What the player sees in this situation
The map is covered with a large number of nodes, according to the type of tile. When a unit arrives at a node, it knows where to go next (each node is associated with the possible directions of movement), and so on until it reaches its destination. The nodes through which the unit passed become reference points. But StarCraft 2 allows you to avoid collisions by avoiding other units along a small radius route, and in BroodWar, units compete for knots. 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 scatter when moving towards each other.
Mutalisks choose different control points if they are rotated 180 degrees
Attempt to simulate the BroodWar algorithm by specifying a large number of key points
The difference is that in BroodWar, units use, according to algorithm A *, the same key points, moving step by step. And in StarCraft 2 for each unit a separate route is calculated 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 misses another, or calculates a new route of movement. In BroodWar, when working as an explorer, you can often see a situation where one player stops a scout with his unit and another tries to circumvent the obstacle, or both players try to hold each other 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 moment will give a signal to bypass the obstacle. It also allows units to merge together or, on the contrary, split up without calculating a complete new path or loss of momentum. In the worst case, units can ignore the collision radius, thereby providing smoother movement and higher movement efficiency in general.
OpenSteer : an open source library to bypass obstacles
BroodWar'r zerg decide who will run first. And in StarCraft 2, zerg begin to unfold in advance.
A large number of BroodWar fans do not like the new algorithm, and for good reason. One of the most effective tactics at the beginning of the game is a detour and an environment. But, if enemy units move close to each other, the environment will not be as effective. Zerglings do so much damage to marines when they don’t stand in a heap, because marinas attack from a distance, but zerglings don’t. If you reduce the "surface area" of your army (for example, arrange it in the form of a circle), the units will receive much less damage. Accordingly, the larger the size of the army, the greater the effect of such tactics.
Flash vs Effort (OSL 3rd final game). Marina Flash'a are located far enough from each other. Therefore, zerglings who ran from the flank killed them. It was worth winning to Flash.
findings
Another issue is that, ideally, the amount of effort spent on the movement of a unit should directly correlate with its effectiveness. Those. Players who do not control their units should 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 a unit can disrupt the plans of beginners, 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 casually managed, and vice versa. You shouldn’t force people to “fight the interface” to create balance in the game.
I'd add that in terms of mathematics, Blizzard has developed a very good algorithm. Still they published it.
Note: the article was written before the official release of SC2
Source: https://habr.com/ru/post/100698/
All Articles