Cossacks game pathfinding

Question

Cossacks (released in 2002) is an RTS game where you can build huge (few thousands men per player) armies on a really big maps. Imagine Age of Empires 2 for few players on Ludikris map with no lag, with 8000 units on the map (or even bigger map with even more units!). What is interesting is the fact, that if you send this huge army to the other corner of the map ... the game does not stall. Units just start moving towards their target position. There are obstacles on the way, like hills, buildings, walls etc, which are avoided by units.

There is, however, a problem with pathfinding - sometimes units just go back and forth around hills, so that might indicate, that whole path length is divided into smaller parts and units' gets confused. But still, that's massive amount of computation to be done for a few-thousand-men army, really impressive.

Do you have any idea how such smooth (in terms of performance) pathfinding was/could be achieved?

Answer 1

I don't know which technique was specifically used in Cossacks, but I guess you are also interested in the problem at hand in general terms. In fact, nowadays, there are ways trough which such result can be achieved - although of course advanced techniques are needed in demanding scenarios.

Overall, two are the main bottlenecks when implementing path-finding in that type of map you describe: number of agents and size of the space to be searched (path-finding = search for a viable or the shortest path).

1. The number one approach in such situation is trying to decrease the size of the problem, i.e. search less and search in lower areas.

   1a) On the one hand, to search in lower areas means reducing the possible paths that have to be evaluated in a path-finding step. For that, spatial partitioning is often used. The scene is divided in areas so that the path-finding can be performed in smaller search-spaces at a time. Also, there are search algorithms such as the HPA* and the HAA* that implement inherently a hierarchical path-finding, by partitioning the scene.

   1b) On the other hand, searching less means assuring that only some agents search paths at a time. An useful trick here is to create the impression of a higher number of agents path-finding than the real one. For instance, in some games there are squads of a given number of soldiers, where the path-finding is actually done per squad, not per soldier. If you think of a squad composed by 10 soldiers, that alone reduces the path-finding by an order of magnitude. Then, once the path of the squad is found, what is needed is that each soldier is able to avoid obstacles in the ways - which means collision avoidance per soldier.

2. I mentioned collision avoidance above. Notice that quite likely, most of the frequent CPU work of the many units in the situation you describe would not be due path-finding in itself, but rather due to avoiding obstacles during the path-following stage. But hills, buildings and so on are never very numerous. The real problem arises when agents have to avoid each other.

   Indeed, that can hurt performance when thousands of agents are avoiding the collision against each other at the same time. However, tricks can be also used here. First, agents only have to avoid the agents and buildings that are close to then. Second, in some games (particularly isometric games), there can be quite a tolerance with how much agents can in fact collide (or even overlap) with each other, since the camera angle disguises it. In some older games, units simply could "walk over each other" - meaning that one agent does not fully block the path of the others.

   Also, modern applications can handle fairly impressive number of actors avoiding collision at the same time. E.g.: https://www.youtube.com/watch?v=Hc6kng5A8lQ or download and see an ORCA algorithm example with 25000 agents in a really huge crowd: http://gamma.cs.unc.edu/ORCA/videos/ORCA-3.wmv

3. In games with huge number of units fighting, a lot of units die. And die fast. Often before the mass of units even have to avoid too much obstacles.

4. Modernly, a technique called Flow Field Path-finding has been introduced in Supreme Commander 2 (2010), that actually allowed for the first time the RTS control of massive number of individually behaved agents: How does Flow Field pathfinding work?