In my game I have lot of independent agents running around in a tunnel system. Agents can block each other, so the problem is, that at certain bottlenecks the agents will create a traffic jam.

To solve this for just 2-3 agents, agents, who detect a blocking situation with an other agent will wait for a random time. In this situation it is likely that one agent will push away a waiting agent and the traffic jam will be dissolved. But once there are around 3-5 agents it gets really nasty. So far I have already implemented a knowledge system in which other agents will try to avoid this bottleneck once the jammed agents starts announcing the bottleneck, thought this works only if there's an alternative route available.

Any ideas how I can dissolve such a jam ? Do I need to cheat in this situation ?

Steering Behaviors to the rescue? Maybe there are some ideas in there for you. Starcraft 2 for instance uses a form of the Queuing behavior to flock units around in formation.

There was an article in one of the Gems or AI Wisdom books (I believe the latter) where people were doing time-sliced A* where agents were able to reserve spots at discrete points in the future. e.g. "4 frames from now, I will be using that tunnel". As other agents ran their plans, if, at frame 4, they tried to use that tunnel, they would detect it as blocked and go elsewhere.

Another method was one that I saw Chris Jurney (Kaos/Relic/Double Fine) show about how they avoided vehicle collisions in Dawn Of War 2. He showed an example of 2 tanks moving on intersecting routes. They each projected a version of themselves ahead based on their speed. If those projections collided with each other, one or the other would slow down or stop until the collision was no longer going to occur. This is the "local steering" version of the A* implementation above.

The first method sounds a lot like David Silver's cooperative pathfinding paper. I played around with that one for awhile... it's a cool technique, but it's limited to its grid.

The second sounds similar to UNC's RVO/ClearPath/ORCA/whatever they're calling it this week... project page here. Incidentally, these guys have made their source code available, which is an unusual and highly classy thing to do. Even stranger, it's actually pretty good code. Highly recommended.

Oh, and finally, UCLA has done some work in "externalized steering logic"; basically, zones of explicitly designed cooperation around bottleneck areas. The main advantage of this technique, as I see it, is that it can integrate into pretty much any other path-planning technique. I don't think that paper's available online.. let me know and I think I can get you a copy.

@KulSeran
Great link. I think that steering behaviour could be a valid option (I already implemented some basic steering behaviour).

@Inno
The reserving of spots, maybe entering an access queue, sounds interesting. The second sugguestions sounds a lot like the queuing steering behaviour mentioned by KulSeran.

@Sneftel
The cooperative pathfinding link is broken, or atleast I can't access it. The externalized steering logic sounds interesting and I would appreciate more infomation. The clear path link should work, but feels a little bit like an overkill for my requirements.

To sum it up sofar, I got two problems. Avoiding and dissolving a jam.

To avoid it steering behaviour could help. Maybe a two way steering behaviour such like always steering on the right side of a path in combination with the queueing steering behaviour (slowing down when detecting an other agent) would avoid most jams in doors and tight tunnels.

But on the other hand there're situation where a jamming is not avoidable, in example a combat situation in a door frame after which the winning team plans new action out of an already jammed situation. In this case I don't really know how to dissolve such a jam ? Any ideas ?

Sorry if I'm repeating something already said (as I've not clicked all the links) but I think that being able to instruct another unit to move temporarily may suffice. The high priority unit could tell lower priority units that are on its path to move away to a nearby location off the path, and then to return shortly afterwards.

One solution that is worth mentioning is making the tunnels wider.

Quote: Original post by alvaro
One solution that is worth mentioning is making the tunnels wider.

I think there is an algorithmic solution for that... nice catch. ;-)

Quote: Original post by alvaro
One solution that is worth mentioning is making the tunnels wider.

This has been done two times ^^ .

Well, I will start with steering behaviour:
pathfollow with offset for "right" lane
+ queueing
+ short time fleeing to disolve a group of jammed agents

When I will encounter traffic jams still, I will take a look at the more advanced approaches or just start cheating if the agents are not in the view of the player.

Thanks for all your input.

Quote: Original post by Kylotan
Sorry if I'm repeating something already said (as I've not clicked all the links) but I think that being able to instruct another unit to move temporarily may suffice. The high priority unit could tell lower priority units that are on its path to move away to a nearby location off the path, and then to return shortly afterwards.

There must be a global ordering of units for this approach, otherwise multiple high-priority "lords" can push other units into the jam from opposite directions, indirectly pushing and blocking each other.