Imagine a Starcraft map as one big grid which is divided into hundreds of little squares. Most units, the smaller units (like marines and zerglings) occupy a single square while the larger units (such as dragoons and ultralisks) occupy multiple squares.
When a unit is issued a move command, the parameters of that command (the current location and destination in the grid) are run through the pathfinding algorithm which spits out an array of path coordinates. The unit then moves along the path, but it only goes 1 square at a time, one set of coordinates at a time. Each time it travels to a new square, it asks “is the next square along the path occupied?” If the answer is “no,” the unit keeps moving along the path. If the answer is “yes,” the unit waits a fraction of a second, and checks again. If the path is still unoccupied after a certain time increment, a new path is generated from the algorithm and the unit walks around the square that was unwalkable.
Another circumstance in which the path is re-calculated is when a new move command is issued while the unit is en route. This behavior has given rise to spam-clicking. The path is literally re-calculated each time you click, so technically a unit is finding the most efficient path at the point of time closest to the click. Because the grid (remember the starcraft map is just 1 big grid) which marks the walkable and unwalkable areas is constantly changing, so also are the results of the pathfinding algorithm. And the older those results are, the less efficient they will be. Hence: spam-clicking!
If you clicked your marine to go across the map, and a building gets placed in the middle of the map while the marine was en route, the original path calculated can no longer be considered accurate (because it was generated before the building was placed). A helper function detects when a path is no longer “accurate”. It asks “is the square in front of me occupied?” If no, it will continue along the path. If yes, it will wait, check again, and generate a new path if it is still occupied. All of this happens very quickly between animation frames.
At one point in the development of Strike Tactics, I utilized this same technique for pathfinding.
Notice how the units stop when they detect an object in front and politely wait for the object to move before continuing along the path? This is Starcraft 1 pathfinding. Units always remain visually separated at the expense of pathfinding efficiency. In other words, units take longer to get from point A to point B but they do so without walking on top of each other.
Here's a look at what the "helper function" which asks "is this node in front of me occupied?" looks like in Javascript. Each time a new node is walked to, the next node in the path is checked. If it's occupied, an interval begins (unit.waitInt) which waits for the node to become un-occupied. If it takes too long, the path is thrown out and a new one is calculated (in my game, setting the unit.goToTarget will cause the unit to find a new path).
function checkGoToNextNode(unit) {
if (unit.path[0] !=undefined) {
var grid = staticGrid;
var findPathMatrixNodeSize = matrixNodeSize;
if (unitDefinitions[unit.unitName].size =='lg') {
var findPathMatrixNodeSize = matrixNodeSizeLG;
var grid = getGridCloneOfStaticLGFromStatic(unit);
}
// lg units should reserve all 9 rather than just center 1var gridX = fnRound((unit.path[0] - (findPathMatrixNodeSize /2)) / findPathMatrixNodeSize);
var gridY = fnRound((unit.path[1] - (findPathMatrixNodeSize /2)) / findPathMatrixNodeSize);
// check if next path is walkable, if not, wait till it isif (grid.nodes[gridY][gridX].walkable || smoothPaths) {
if (unit.nextWalkToNode !=undefined) {
var goToNodeCopy = [unit.nextWalkToNode.x, unit.nextWalkToNode.y];
game.time.events.add(500, (function(goToNodeCopy) {
returnfunction() {
setNode(goToNodeCopy);
};
})(goToNodeCopy), this);
}
if (unitDefinitions[unit.unitName].size =='lg') {
// large units must reserve a node in the staticGrid to prevent other large units from going therevar gridXInStatic = fnRound((unit.path[0] - (matrixNodeSize /2)) / matrixNodeSize);
var gridYInStatic = fnRound((unit.path[1] - (matrixNodeSize /2)) / matrixNodeSize);
staticGrid.nodes[gridYInStatic][gridXInStatic].walkable =false;
unit.nextWalkToNode = staticGrid.nodes[gridYInStatic][gridXInStatic];
} else {
grid.nodes[gridY][gridX].walkable =false;
unit.nextWalkToNode = grid.nodes[gridY][gridX];
}
moveToNext(unit);
} else {
if (unit.unitName !='drone') {
stopAnimationsNetwork(unit, false, 0);
}
unit.waitInt = setInterval(function() {
unit.timesWaited++;
var distanceFromEnd = Phaser.Math.distance(unit.x, unit.y, unit.goingX, unit.goingY);
if ((distanceFromEnd <=100) && (unit.timesWaited >3)) {
clearInterval(unit.waitInt);
actionsAfterCompletingPath(unit);
return;
} elseif ((distanceFromEnd >=100) && (unit.timesWaited >20)) {
// find a new path
actionsAfterCompletingPath(unit);
clearInterval(unit.waitInt);
unit.goToTarget = {
'x': unit.goingX,
'y': unit.goingY
}
return;
}
if (grid.nodes[gridY][gridX].walkable) {
if (unit.nextWalkToNode !=undefined) {
unit.nextWalkToNode.walkable =true;
}
unit.timesWaited =0;
grid.nodes[gridY][gridX].walkable =false;
unit.nextWalkToNode = grid.nodes[gridY][gridX];
clearInterval(unit.waitInt);
walkMech(unit);
moveToNext(unit);
}
}, 50);
}
}
}
If you think that's complicated and messy, consider that this is just one small component of the system. That to me, was a big red flag. The more complicated a system is, the more likely it will fail. Simpler systems work better because there are fewer things in them that can fail.
I discovered this technique on my own through experimentation and had no idea Starcraft used it until I saw Day9’s video. Although Day9 doesn't appear to understand what is going on under the hood, he explains what the pathfinding system feels like to the player and what the gameplay implications are - it just made me think hard about what the units were doing when looking for a path. I came to realize the units were constantly stopping and going because they were asking "is this square occupied?" just like in my own implementation.
At some point in pre-alpha, I ditched this entire approach and revamped pathfinding to something much simpler. Instead of units constantly checking if the node they are about to walk to is occupied, the units simply maintain relative distance from each other when they walk. The only nodes which are marked as unwalkable are the start and end destinations. Even though the same grid structure is used, units don't move like they are playing hopskotch because a second algorithm (independent of the pathfinding algorithm) smooths the paths. This is the system currently used in Strike Tactics.
Early feedback from alpha testers was the impetus to overhaul pathfinding in this way, and as soon as I made the change, “pathinding” ceased to even be a topic of discussion among alpha testers. That to me proved the new pathfinding was good, because it did its job unnoticed. My reasoning is that If players notice your pathfinding, that’s when you know it’s bad. The contrapositive is that you don’t get praise for good pathfinding, because no one notices it. SC2 pathfinding is probably the best pathfinding system ever devised for a dynamic world. Units of all sizes miraculously find their way to destinations, without overlapping each other and without stopping. Despite this, the only discussions surrounding SC2 pathfinding are in relation to brood war pathfinding, and how it just doesn’t have the same charm to it. Brood War pathfinding is considered "fun" for some players, because it requires more micro-management to move your units effectively.
Anyway, I don’t recall the last time someone complained about pathfinding in Strike Tactics, so I like to think it’s a solved problem at this point. The units simply go directly to their destination in the fastest way mathematically possible. It might not look as good as the original system where units always remain visually separated, but it certainly feels better. And if there’s anything I’ve learned, feel is much more important than looks. Players prefer more efficient unit movement and pathfinding over all else. They don't care how it looks. Truthfully, I don’t think anyone (other than me) has noticed that units occasionally walk on top of each other in Strike Tactics. Yet that was one of my greatest fears and where i spend 99% of my energy writing pathfinding. Funny, the things developers feel are important don’t always align with the things players feel are important.
In Starcraft 1, you will also notice that units move in grid-fashion. In simpler terms, units move like they are playing one giant game of hop scotch. A unit can move to the square in front, the square to the left, the square behind, etc. But what units can’t do is move forward 1 degrees, back 2 degrees, left 3 degrees, etc. Movement is strictly limited to cardinal direction: N, S, E, W and NE, NW, SE, SW, etc. This is why the movement feels so “blocky.” Units need to move like this because they need to be able to ask "is this node i am walking to occupied?" If they moved outside the grid (like in sc2), they would not be able to ask that question.
If the path the algorithm spits out is most accurate when it is newly created, why didn’t Blizzard automatically recalculate the path instead of only recalculating it on click or when a unit bangs into another?
Because these calculations are expensive, even by modern computing standards. Depending on the size of the grid, and the algorithm used calculating hundreds of paths for hundreds of units 10 times a second adds up. Thus algorithms like A* are only run when needed, on click or when a unit gets stuck.
The difficulties in implementing pathfinding is never a simple as “determining the quickest route to get from point a to point b,” although gamers - and people who have never worked on pathfinding - probably assume it as such. A lot of devs seem to think good pathfinding is all about choosing good pathfinding algorithms, but that's an oversimplification. It's sort of like assuming Chevy can design the best car by simply realizing they need to use wheels to move the car. The wheel part is already a solved problem. The algorithm part is already a solved problem. The difficulty is in implementation.
Since in an RTS game, the world is constantly changing, the problem is never as simple as determining the fastest route to get from point a to point b. In a changing world, the problem is determining the fastest route from point a to point b while not bumping into objects c, d, e, f, g, etc, which are by the way, constantly moving at various speeds an in various directions. The difference between solving dynamic world pathfinding and static world pathfinding is the difference between shooting a moving target and one which stands still.
Many modern RTS games avoid the problem altogether by simply doing overlap/collision checks on every frame and separating units which get too close (think of it like bumper cars). Starcraft 2 uses this technique to some extent, but the technique is CPU intensive. With SC1 pathfinding, the only real CPU-heavy stuff (computing the path with the algorithm) happens when you issue a click command or when a unit gets stuck and needs to generate a new path. But with collision detection, the CPU intensive stuff is happening every millisecond. It absolutely would not be possible with 1999 tech.
