Hi all! I'm interested about how pathfinding of multiple agents in existing computer games is actually done. I just read about Cooperative pathfinding (Silver, 2005) but that's quite new thing, highly unlikely used in Warcraft 3, Command & Conquer, Baldur's Gate, etc. :) Is there any way to find out what kind of techniques 1995-2005 games use? How is ma-pathfinding done if it's not cooperative? Are all other agents just ignored or considered as static or dynamic obstacles? I know LRA* but it's hard to imagine that would work in crowded environment. Is there any really simple way to do cooperative pathfinding? Any information or links about this subject (low-tech multiagent pathfinding :) are very welcome. Thank you!

if the agents are in a group then usually a path is found for one of them and the other ones follow him somehow. usually only static obstacles are taken into account during the path search and the dynamic ones are dealt with as they come.

(... with steering behaviors to handle local dynamic objects)

There was an article in one of the recent Game AI books that added a temporal element to A* - adding a dimension for time of occupation for each node so that blockage could be scheduled around. Cooperating units could then mark where they intend to be along their path and other units avoid those places when they are already reserved.

There are two principle paradigms for multi-agent systems: cooperative or coordinated. These are applicable whether we are concerned with pathfinding of squads in games or actual robots playing soccer.

Cooperative agent solutions stress that agents negotiate the solution to their problem among themselves, generally with each agent having equal say in the final solution. No single agent typically knows what all other agents are doing (but might be given information about neighbouring agents). An example of this is the flocking behaviour we hear mentioned often in this forum.

Coordinated agent solutions generally rely on an oracle (which may be one of the agents) that coordinates the operation of all agents. The oracle is responsible for observation, decision making and disemination of orders to agents. This is commonly seen in squad-based AI where the squad leader acts as the oracle.

The most common approach in games for pathfinding for multiple agent scenarios would be the latter. Most of the review/post-mortem articles I have read over the years have focues on pathfinding once for the squad leader and then having all units follow the same path (possibly while maintaining a rigid formation), or having each unit use the leaders path as a basis for their activity. There are of course exceptions and variations on this theme in many shipped games, but the core idea is the same: solve the problem once and massage the solution for individual agents.

As for cooperative agents in games, you'll see a lot less of that, mostly because it becomes very difficult to design high level group behaviours using only rules for local interaction between individuals. Having said that, steering behaviours (as InnocuousFox pointed out) have become popular in recent years, particular with regard to enforcing local movement behaviours on groups of agents with common goals (such as squads moving in formation).

Gamasutra is a good resource for post-mortem articles and design articles. The Game Programming Gems and Game AI Wisdom series of books also have a good selection of articles on techniques used in commercial titles.

I hope this helps.

Cheers,

Timkin

Quote: Original post by Timkin
The most common approach in games for pathfinding for multiple agent scenarios would be the latter. Most of the review/post-mortem articles I have read over the years have focues on pathfinding once for the squad leader and then having all units follow the same path (possibly while maintaining a rigid formation), or having each unit use the leaders path as a basis for their activity. There are of course exceptions and variations on this theme in many shipped games, but the core idea is the same: solve the problem once and massage the solution for individual agents.

This is more or less what Company of Heroes is doing. We have soldiers grouped into squads, and only the leader is actually going to the goal... the rest are busily making short distance move orders to stay in formation. Other soldiers are static obstacles to these searches. This works out ok to avoid each other because we constantly repath (every ~0.5-1 second for followers, every 1-3 seconds for leaders). We keep the costs down on the repathing through lots of different optimizations, but primarily the use of hierarchal pathfinding keeps it in check.

Chris

Quote: Original post by SKalliola
I just read about Cooperative pathfinding (Silver, 2005) but that's quite new thing, highly unlikely used in Warcraft 3, Command & Conquer, Baldur's Gate, etc. :)

The pathfinding in Baldur's Gate is so poor that I doubt any cooperation took place at all. One character would quite often go the long way around if another character happened to stand between it and the destination, even if that character was moving away from the choke point at the time.

Which makes me think...

Can you generate a time estimate of when a choke point will be cleared and convert that to a terrain weight? That way, in a situation such as that, the agent would decide whether to wait (a la Reynolds queuing at a door), or find a new path. Let's face it, it would be just as silly for us to watch a huge queue at a door if there was a slightly longer, yet more time-effective path available.

I suppose that when a path is generated, it could reserve each node in the map for the time that the character expects to arrive there (plus and minus some small duration). Querying nodes for subsequent paths could then easily take this into account. The only implementational hiccup I can forsee is when a path is cancelled, but even then you just need to go through the remaining path nodes and reset the reserved time.

Obviously there are some omniscience issues here, but storing a timestamp per node is small enough to have separate copies of this for each player I assume.

In the old C&C's it works something like this:

1) pathfind agent A
2) if any idle agents are along the path of A, move them out of the way as A draws near
3) completely ignore collisions between agent A and agent B if they are both moving and their paths intersect

From an RTS view it's more likely that you'll interpret in-motion pass-through collision as occlusion (especially in the older games where you couldn't bring the camera that close to the ground). Nowadays in RTS games you do a little more look ahead and avoidance but there's still a _lot_ of in-motion collision. Generally you get a lot of "dynamic avoidance" just by making sure that units come to rest in unique positions.

-me