Multi-agent pathfinding

Dave wrote:

> I'm looking for information on multi-agent pathfinding, either from
> academic research or the games industry.
> The problem: find optimal or near-optimal routes on a grid to get n
> agents to n different destinations, avoiding collisions.
> I'm looking at ways to improve on the usual approach (A* for each
> agent, and then recompute route every time a collision is imminent)

Not sure thats the usual approach. For my stuff[1] I do an A* path
plan every so often on each agent. This makes sure and catches doors
closing and such.
However, this A* stuff doesnt take into account any other agents,
just large moving objects that affect nav.
For more mobile objects I use avoidance code that works on a local
level.


[1] did all the Nav work for Oddworld: Stranger's Wrath, out soon.

--
marc
 >> Stay informed about: Multi-agent pathfinding 

On Thu, 25 Nov 2004 12:07:26 -0800, Dave wrote:

> The problem: find optimal or near-optimal routes on a grid to get n
> agents to n different destinations, avoiding collisions.
>
> I'm looking at ways to improve on the usual approach (A* for each
> agent, and then recompute route every time a collision is imminent)

The references found at the following URL may help you:

http://groups.google.dk/groups?selm=3BBECC0A.D1798EE4%40mail1.stofanet.dk

--
mail1dotstofanetdotdk
 >> Stay informed about: Multi-agent pathfinding