Quote: Original post by Kylotan

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.

I was going to say that as well. I'm pretty sure Baldur's Gate and all the infinity engine games just used an individual A* pathfinding on each character, without bothering to deal with squad movement. You could often get them stuck walking back and forth knocking into eachother if you tried to move your whole party at once in a small space.

I'm not sure about WC3, but from observing it, it looks like it uses Timkin's explanation of an oracle and coordinated movement. If you have a bunch of units near eachother that are walking to the same location, it picks one of those units to be the "leader", pathfinds for him, and then has the other units trail behind him. You can watch it happen; if things are jumbled up when you click move, one unit will march off while the rest stand there, then gradually follow behind him.

There is a known and well validated solution to this problem within robotics and that is to perform path planning based on expected time of arrival. It's also easy to think of comparitive problems (packet routing in congested networks is a similar problem) and draw inspiration from them.

So, if you know that you're pathing in the vicinity of dynamic obstacles and that you expect congestion at certain points, factor that into the search. At each search node, estimate the expected time of arrival at the goal, then select the path that meets your criteria (earliest arrival, lowest variance in arrival time within a group, ordered arrival, etc.). If you want to add movement cost into this, then you have a multi-criteria performance evaluation; computationally a little more complex, but certainly manageable.

Cheers,

Timkin