Prevent collisions between mobs/npcs/units piloted by computer AI : How to avoid mobile obstacles?

Question

Lets says we have character a starting at point A and character b starting at point B. character a is headed to point B and character b is headed to point A. There are several simple ways to find the path(I will be using Dijkstra). The question is, how do I take preventative action in the code to stop the two from colliding with one another?

case2: Characters a and b start from the same point in different times. Character b starts later and is the faster of the two. How do I make character b walk around character a without going through it?

case3:Lets say we have m such characters in each side and there is sufficient room to pass through without the characters overlapping with one another. How do I stop the two groups of characters from "walking on top of one another" and allow them pass around one another in a natural organic way.

A correct answer would be any algorithm, that given the path to the destination and a list of mobile objects that block the path, finds an alternative path or stops without stopping all units when there is sufficient room to traverse.

Answer 1

The simple answer is steering. The steering is used to steer towards the waypoints of your found path. Further, it's used to avoid obstacles including other characters. Implementing a look ahead with a variable steering vector will help make it a smooth movement. Basically, the closer the object the larger the perpendicular vector to avoid the obstacle:

In addition to steering, the character being passed should slow down, or the character passing should speed up for a short time. This will give the passing a more natural look and make it take less time.

Characters should default to one side or the other if they're heading almost directly at each other. This way if both characters are about to head on collide they'll turn away from each other.

A more advanced step would be to implement flow field pathfinding. More information about how it works can be found in this question. A video demonstration of it can be found here.

Answer 2

If you're using Dijkstra, then every time your actor reaches a node on the graph, you could verify that the path he's taking is still valid. If it's not, you can then use Dijkstra's to find a valid path again assuming you've updated the graph to reflect the obstacles. Alternatively when the obstacle is detected you can attempt to steer around it to reach the next waypoint. Steering upon hitting an obstacle is discussed a bit here.