I'm implementing a multi agent A* algorithm on a tile map. Agents move only in the X and Y axes. I avoid collisions between them by checking where the others are when calculating paths.
It works fine except the situation where agents have to pass the same tile from different directions. In situations like this, an optimal solution would be for one agent to wait for the other to pass:
Also, if there's no northern corridor, then pathfinding fails.
How could I implement such an algorithm?
Answer
You can start by letting the pathfinding fail. On failure, choose a random time in the future to re-try pathfinding. Some low level networking protocols work that way, and quite well. What you have to do is build paths one at a time, and mark as used all the tiles an agent will pass through. When further paths fail the random timer to restart will help spread out the new path searches and break up looping failures.
The second part of your problem could be handled by returning two paths. The first path is the regular return, even if it fails from a block. The second path is a path that completely ignores all the agents. You can then use the knowledge gained from these two paths to decide whether waiting or taking the long way would be better. The heuristic for that decision will take some work, but it's better than not trying anything at all.
In the very bad case where your agents are getting blocked a lot by single width corridors like this you may have to add safe spots to stand where agents can quickly path to and wait for their real path to open up (so the agent doesn't just wait and block a corridor).
No comments:
Post a Comment