[Algorithms] Formations/flocking

[Sergei M. <se...@ha...>]

Hi all!
I am not sure that this maling list is the place for these topics, but if
things like 'collision' takes place here, why not...
I am wondering is there something about formations and their behaviour when
they face obstacles... i.e. I have a group of units forming a 'formation'
i.e. all of them are 'locked' to specific offsets from any other unit
(probably the closest one to the geometric center). And all that mess must
move through the world avoiding obstacles and trying to keep its form as
much as possible.
It is obvious that there will be single path finding task - for the group
leader and then the formation will move with him (althought the A* may be
used with a proper weight function to cast many path finding calls and
produce good results, but this is slow!). So I find a single path for the
leader and then this path is partitioned by points located at constant
distance each to other and at each point the formation is placed - why?
because this way each unit will search for a short-distance path (i.e.
between previous formation copy and the current one) many times, preventing
a long-distance search done once. This keeps them together and properly
formed. So, the problem - when some of the units' offsets are placed inside
obstacles then one must find 'the best' nearest location for that offset.
How? This is very important when a wide formation is passing a narrow
tunnel. Thanks.
    Sergei Miloikov, Haemimont-Smartcom AD