Shortest path in games (StarCraft example)

Question

In games like StarCraft you can have up to 200 units (for player) in a map.

There are small but also big maps.

When you for example grab 50 units and tell them to go to the other side of the map some algorithm kicks in and they find path through the obsticles (river, hills, rocks and other).

My question is do you know how the game doesnt slow down because you have 50 paths to calculate. In the meantime other things happens like drones collecting minerals buildinds are made and so on. And if the map is big it should be harder and slower.

So even if the algorithm is good it will take some time for 100 units.

Do you know how this works maybe the algorithm is similar to other games.

As i said when you tell units to move you did not see any delay for calculating the path - they start to run to the destination immediately.

The question is how they make the units go through the shortest path but fast.

There is no delay in most of the games (StarCraft, WarCraft and so on)

Thank you.

Answer 1

I guess it just needs to subdivide the problem and memoize the results. Example: 2 units. Unit1 goes from A to C but the shortest path goes through B. Unit2 goes from B to C. B to C only needs to be calculated once and can be reused by both. See https://en.m.wikipedia.org/wiki/Dynamic_programming

In this wikipedia page it specifically mentions dijkstra's algorithm for path finding that works by subdividing the problem and store results to be reused.

There is also a pretty good looking alternative here http://www.gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php where it takes into account dynamic stuff like obstacles and still performs very well (video demo: https://www.youtube.com/watch?v=z4W1zSOLr_g).

Another interesting technique, does a completely different approach: Calculate the shortest path from the goal position to every point on the map: see the full explanation here: https://www.youtube.com/watch?v=Bspb9g9nTto - although this one is inefficient for large maps

Answer 2

First of all 100 units is not such a large number, pathfinding is fast enough on modern computers that it is not a big resource sink. Even on older games, optimizations are made to make it even faster, and you can see that unit will sometimes get lost or stuck, which shouldn't really happen with a general algorithm like A*.

If the map does not change map, you can preprocess it to build a set of nodes representing regions of the map. For example, if the map is two islands connected by a narrow bridge, there would be three "regions" - island 1, island 2, bridge. In reality you would probably do this with some graph algorithm, not manually. For instance:

1. Score every tile with distance to nearest impassable tile.
2. Put all adjacent tiles with score above the threshold in the same region.
3. When done, gradually expand outwards from all regions to encompass low-score tiles as well.
4. Make a new graph where each region-region intersection is a node, and calculate shortest paths between them.

Then your pathfinding algorithm becomes two stage:

1. Find which region the unit is in.
2. Find which region the target is in.
3. If different regions, calculate shortest path to target region first using the region graph from above.
4. Once in the same region, calculate path normally on the tile grid.

When moving between distant locations, this should be much faster because you are now searching through a handful of nodes (on the region graph) plus a relatively small number of tiles, instead of the hundreds of tiles that comprise those regions. For example, if we have 3 islands A, B, C with bridges 1 and 2 connecting A-B and B-C respectively, then units moving from A to C don't really need to search all of B every time, they only care about shortest way from bridge 1 to bridge 2. If you have a lot of islands this can really speed things up.

Of course the problem is that regions may change due to, for instance, buildings blocking a path or units temporarily obstructing a passageway. The solution to this is up to your imagination. You could try to carefully update the region graph every time the map is altered, if the map is rarely altered in your game. Or you could just let units naively trust the region graph until they bump into an obstacle. With some games you can see particularly bad cases of the latter because a unit will continue running towards a valley even after it's been walled off, and only after hitting the wall it will turn back and go around. I think the original Starcraft had this issue when units block a narrow path. They would try to take a really long detour instead of waiting for the crowd to free up a bridge.

There's also algorithms that accomplish analogous optimizations without explicitly building the region graph, for instance JPS works roughly this way.