We split bot navigation into two layers - pathfinding is run for each bot independently, which yields a path (which will persist for a long time), and we hand off that path to a more reactive system (eg. a steering system that uses velocity obstacles or something) which is responsible for dealing with surprises like other bots getting in the way. Even thought steering works well at preventing collisions between bots, it has to use the path it's given, and it can't avoid chokepoints that force it through other bots - paths that end up slowing everyone down and making them look dumb.
Here's an example in my toy pathfinder: white squares are traversable, dark grey are blocked, and the colored plus signs are the paths of 4 different bots (they're taking paths that heavily overlap each other). All the paths go through the chokepoint in the middle. The purple bot could have easily avoided the traffic jam by going south a bit, but instead he's taking a (slower!) path that forces him to deal with everyone else.
If we increase the path cost of chokepoints by predicting heavily contested positions, A* will route us around those traffic jams. It's easy to predict where other bots will be - just look at their paths. To keep things fast, you can implement this with a per-position count of the number of paths that use each position (treated like a refcount) - that way, the cost of finding a path is independent of the number of other paths.
Here's my toy implementation: although the naive shortest path for all 4 bots would go through the same chokepoint, the bots now take paths that avoid each other. (their 'avoidance radius' falls off at 3 squares, so they're giving each other a wide berth). If the cost were higher, they'd worker harder to avoid each other - but some path intersection is unavoidable here.
This sort of system could be an improvement for style reasons, too - imagine a swat team spreading out to clear an apartment - although maybe they're ultimately going to the same place, you want them to explore as much as they can (kind of like a cheapo version of influence maps).
One complication is that paths become order dependent. The first bot to path in an area ignores everyone else, the second bot only ignores the first, etc. Finding truly 'correct' paths in this case would need to be done simultaneously for everyone (but I don't see how that would even work! Any ideas?).
A less tricky implementation would be to only approximately track positions - by keeping a per-area refcount (if your game spaces are hierarchically partitioned), or only attaching the cost to doorways, or only tracking bend points on the path rather than every position, etc.
A more tricky version would be time-indexed - meaning you care about the specific *time* that each bot will arrive in each position. This makes things more correct - a bot would be happy walking in single-file behind other bots. However, time-indexing has a few caveats:
- makes the bookkeeping more complicated, and makes the runtime slower (slightly)
- requires your pathfinding system to accurately predict the movement speed of a bot
Maybe a simpler alternative to time-indexing would be to tag each position with a velocity - that way you'd get more cooperative groups without all the complexity of real time-indexing. Ie. you're saying "you can use this door without trouble if you're going north".
Here's a paper that does something kind of similar that got me thinking about all this: I think their videos show really impressive group dynamics, and I think a big part of what makes it look good is the planned-local-avoidance thing (more than the footstep planning animation synthesis, although that's pretty cool too!).
