Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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

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.

share|improve this answer

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:

Illustration of vector-based unit control in an RTS game.

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.