path finding - How do I implement group formations in a 3D RTS?

I managed to get pathfinding work for a single unit, and I managed to avoid agent-agent collision, but now I need to be able to send a group of agents to some location.

This is my set-up so far:

• Waypoint pathfinding


• The minimum distance between two nodes is a little bigger than the biggest bounding sphere radius allowed for an agent.


• Agents avoid collisions with other agents by doing some steering behaviour I based on clearpath

So now I need to send my agents somewhere in group. I have read some posts saying that some way to do it is to create a group leader and give the other units offsets to his position.

But then the problem is, what if the group formation cannot be achieved? e.g. you want to form a rectangle, but at the target position there is a structure nearby which prevents you from creating a rectangle setup.

Answer

There is actually a pretty nice article about this over at Gamasutra. And covers topics like formations and resolving collisions:

And another article from them on the same topic, which is a bit shorter but has more pseudo code examples:

Finally, a nifty thing to think about when implementing your system is the idea of a "Flow Field" Supreme Commander 2 used this; And it's based on Washington State University's Crowd Flows research.