# How can I keep AI from getting stuck on each other?

I'm currently working on AI and, as stated above, I'm having trouble figuring out how to keep the AI from getting stuck on each other.

More specifically, I'm working on two different behaviors for the AI:

1. The AI form a group of four, determine which one of them is the strongest and bravest (whichever has the highest number), make that one the leader and then snake behind the leader. This doesn't workout because the leader ends up getting stuck on the others as they attempt to walk through him to form a line.

2. The AI moves from one room to another. This doesn't work out because the one changing rooms will get stuck on ones that are doing other things or even on other room changing AI.

The way I've programmed it, AI traveling to a destination will calculate which tile gets it closer to it's goal (they use jump point pathfinding to find their way around) and then they calculate which tile they'll move to the next turn. Other AI check to see if a traveling AI is around them and if there is, they move one space to the side (or at least they're supposed to move.)

Does anyone know a way to keep this from happening?

I've seen some people address this by having AI mark the path they plan to walk on as more expensive for other AI. This has the effect of some avoidance between agents but since it isn't time aware (the future path is more expensive always, not just when the agent will be there in the future) it can make some odd behavior if it is too strong of an effect. Another way people deal with this is to let the AI in this situation either slide past each other instead of getting stuck, let AI push each other around a bit to let them through, or even just allow them to walk through each other (sometimes only when there are no other options). There are other ways to solve it but these are a few ideas. There are entire research papers dedicated to this topic so the right answer depends on your specific needs (:

• I would just let them walk through each other, but my game is turn-based and the player and AI take up one tile at a time. So if they do walk through each other, they could end up occupying the same tile and I don't want to overwhelm the player with thirty enemies on one tile. I could try making tiles more expensive, since I did experiment with an abstract map at one point. Any idea what I should search for to find papers on this? Apr 12 '15 at 19:55
• SIGGRAPH 2014 had some stuff that talked about this. I can't recall the name of the talks specifically but if you are able I'd check out the pathfinding talks from SIGGRAPH 2014 Apr 12 '15 at 21:43

this is my first time helping on a question and is hard for me to understand others when they dont use a graphic exaple. Apologies in advance.

Considering that your game is turn based and your AI units can only move one tile per turn, and considering that they get stuck so easily, then I have to make some assumptions on how you game works and offer at the same time some solutions to your problem.

Case 1.- Your game maps have small corridors, passages, doors,obstacles,and so forth or AIs are positioned too close, so they can't turn around each other : In this case you have to use the help of a "wait" variable whenever there is no way to move, and keep it until the leader frees more space to move. You can either alternate the other AIs order on the snake formation. If the leader got stuck because it can't pass through the other AIs you can add a "switch position" method to switch position whenever they cant move.

Case 2.- Your maps are big but your AIs get stuck because the AIs still want to pass through each other(or your algorithm is not that complex) or they want to have an specific formation no matter where the leader is pointing at or want to go: In this case you can do what you already stated, make the occupied tiles more expensive, you have to treat them as total obstacles. You can also apply the "switch" and "wait" methods to make it easier.

If your AIs can move through more than one tile per turn then you can just let them pass through each other but dont letting them stay in the same tile and using the wait method whenever they just cant move.