I am right now trying silver's WHCA* algorithm, but with the following setup,
where the narrow corridor has a dead end, the agents just spin around at
the choke point and stuck. Agent 3 is unwilling to get out of the way and just sits there.
The other 4 agents just keep spinning around at the entrance of the choke point.
How do I work around this?

Pathfinding will not solve this. You can use some kind of steering behavior, e.g. queuing and avoidance. If you don't have free moving agents, agents which move only along a riggid grid, you could think about swapping. That is, two agents are able to swap places to solve a locking situation.

I had a similar issue in my game (narrow tunnels and many agents running around). I solved it by disabling inter-agent collision detection and adding steering behavior. So, if everything runs fine, they do not overlap. But in some disadvantageous cases they will start to overlay, but there will not be a locking situation.

I think steering behavior is the way to go....I've read a lot of articles and thesis on the net.

The OD+ID approach could be the way to go too. But I don't have any ideas how to implement it.

The OD+ID idea is to path-find agents in groups and use some sorts of illegal move tables

Hope that I can find a demo ultimately. If not, I think I will turn to use steering behavior as the solution.

Thanks

Jack

Ah, I know that demo app, it's written by me, adapted from David Silver's paper WHCA*

Here is the web page related to project:

http://aptalkarga.com/jkilavuz/whca/

You can prevent agents stuck in corridors like that, but your search depth (time) must be bigger than the length of the corridor.

Edit: Added link to project page

My simulation still got some problems. If I set some fixed windows for many agents, Say

Window
Agent 0:    2, 18
Agent 1:    4, 20
Agent 2:    6, 22
Agent 3:    8, 24
Agent 4:   10, 26
Agent 5:   12, 28

@Window 4, if agent 0 at 0,0 is right next to agent 1 at 1,0

Since agent 0 hasn't extended his reservations up to time 34 for 0,0

and agent 0 hasn't got a turn yet. Agent 1 will step in agent 0 position of 0,0 and reserve 0:0:34

And the reservation table is messed up.

Any ideas I can fix that?

Thanks

Jack

well, there is always a chance that an agent cannot find a path in time-space especially in such very tight environments. some options:

* nevermind about this :) just let one agent step over another

* use a wider environment. shorter or wider corridors for example.

during startup, reserving time in current cell until first windowing time may also help a bit.

Dear raft, Here I am after another issue. If the agent distribution is really packed and the dead end is closed as well,

and it chooses to go back to somewhere to dodge temporarily,

which node should it choose to dodge,

My tries are these

1) Take the average g score of all opened nodes, and see if which node is the closest to that score, which doesn't work

2) Take the node which is opened the most often by all agents, which doesn't work either. Any suggestions for me?

My problem is, okay, I can let it go back to its original position, and have the windows shuffled until the one that is no stuck,

but it is a cheat. If I let it go reversed all the way back to its original pos, sometimes,

it is a waste because some of the agents may already traveled half way to the destination where there is no stuck as well.

Any better ideas for me?

Let me know.

Thanks for kindred help

Jack

the node it chooses to dodge both depends on the time reservations of the nodes around and the destination (goal) node I suppose. maybe you can try temporarily changing destination goal?

Hi raft,

I had the same thinking here, I had tried to change the destinations on the fly.

But it still seems to know a temporary dodge position in order to get out of the narrow passage first.

(i.e: the temp destination == dodge position)

Thanks

Jack

i don't know the demo application :) but can't you add an AI mode to either constantly maintain a distance from others or, if an agent is determined to be "stuck" this can change other agents close by to a mode where they move directly away for a fixed length of time? like people would in real life.. "back up, i'm blocked in.."