Grouping units in world space

Question

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?

Answer 1

If you are looking for an academic solution have a look at cluster analysis, possibly combined with this other Wikipedia page: Determining the number of clusters in a data set.

Keep in mind these algorithms are typically designed for processing highly-dimensional data, not unit positions in 2D/3D, so be sure not over-engineer your solution based on this.

Answer 2

Not entirely sure if this is what you're describing, but there is an article in Game Programming Gems 7 entitled "A Sketch-Based Interface to Real-Time Strategy Games" (Chapter 1.6) that describes a method for moving RTS units using potential fields. Essentially, it says that if you have a multi-segmented path that can be represented by a vector, or series of vectors, where the magnitude of these vectors determines the relative speed of the affected units, you can project that vector onto the terrain, divide it into an arbitrary grid of 2D cells, and have the units infer their movement speed and direction from the vector in the cell they are standing on. I drew a quick little diagram to illustrate what I'm describing:

The algorithm can be easily adjusted to make all units within the affected area stick together by ensuring that the flanking vectors are angled slightly towards the original vector path when they are generated. This method produces a more organic and fluid method of unit control which may be what you're looking for.