Formations

[Barsonax]

Summary

Implement formations with the following features:

• Dynamic obstacle avoidance
• O(n) scaling (where n is the amount of agents). This is important because it should be able to handle a few thousand agents atleast.
• Support for arbitrary formation shapes

I believe a approach that combines A* and Potential fields will be able to do this. There will be 3 'layers' in such a system:

1. A* based pathfinding for the formation as a whole. This will plan a long distance path.
2. Potential field based pathfinding for a agent so that it can finds its way to his position in the formation.
3. Potential field based steering once agents are in their formation spot (as in close enough).

Layers 2 and 3 will ensure agents will always retain the dynamic obstacle avoidance that potential fields can provide.

Layer 3 will avoid having to calculate countless expensive potential fields.

The formation behavior should not have a hard dependency on A* and can be used separately.