# Grouping units in world space

I figure that I intend to generate, for group orders, one optimal path, and then use a flocking algorithm to "glue" the units together as they all follow this one optimal path. However, a naive implementation would fail if, for example, the units were ordered from two distinct locations- two optimal paths would have to be computed. So for a group of units, I need to group them into subgroups which can all share the same optimal path.

At the moment, what I'm thinking is to pick an arbitrary unit in the group, and then pick all units in a certain, relatively small radius. Then for every unit in that radius, I increase the radius.

Are there any existing algorithms for grouping units into subgroups?

• Can your problem be re-worded as follows?? Given set of N points, find a set of circles with diameter D that contains all the points. Each point is a unit in the game. Set of points in each circle correspond to a group of units following the same optimal path. – XiaoChuan Yu Apr 22 '12 at 23:40 