7

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.

mrk
  • 8,059
  • 3
  • 56
  • 78
  • Are looking for fast shortest path algorithm or algorithm that calculate all paths from start to end in particular scenario in an optimized way. Please try to rephrase your question in manner that it would be possible for users who have not played game can understand same. this seems product specific and may not be relevant for community as whole – Stakshi Oct 11 '18 at 06:10
  • Changed the question. I want to know how the algorithm find shortest path for all fifty or 200 units and no delay in the game is observed. Shortest path algorithm is not so fast if the map is big like in StarCraft or WarCraft. –  Oct 11 '18 at 09:48
  • 1
    I mostly played in WC2 and SC1 era, and would like to mention that actually, units do not use shortest path. They start moving in right direction, but thier trajectory is far from optimal. I guess, game map is divided in large areas, like 10x10 or 20x20. Maybe some metadata on traversing possibilities is saved at map creation time. Then finding shortestpath in such small matrix is trivial. (I'm not a game developer and may be mistaken) – Oleg Gritsak Dec 07 '18 at 04:06

2 Answers2

6

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

Tiago Coelho
  • 5,023
  • 10
  • 17
  • I dont thing this will work, in these these there are at least 2 players each player has up to 200 units - so 200 units plus dynamic things like rocks which can be destroyed. So if i memoize the path, the next time i use it there can be something blocking the path like my unit or enemy unit. Maybe some combination "memoize" and if something blocking the path calculate again ? That would work maybe... –  Dec 06 '18 at 08:01
  • sure, there will need to be dynamic path invalidation at each step, but the most expensive thing would be calculating all the possible paths lengths, and that is done only once. – Tiago Coelho Dec 06 '18 at 09:57
  • Thanks, maybe the starcraft developers are doing something similar. If I ask them i doubt they will answer me :) –  Dec 06 '18 at 13:19
4

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.

Wassinger
  • 347
  • 2
  • 16
  • Thank you, I suppose that algorithms are not perfect, because 200 units are constantly running, flying, burrowing and the path should be recalculated too often. Even in SC there is a bug when you click unit to go to the opponent minerals it goes through the opponent worker unis. So maybe they are using combination of algorithms,memoization and recalculating or similar.But if they want the algorithm to be "perfect" and to be really shortest path maybe it willcost more processor time.And in mind that this algorithm should be calculated for each unit on the map. This is very complex logic I think –  Dec 07 '18 at 06:23