1
\$\begingroup\$

In Starcraft 2, unit formations are created when a "group" is generated from a command. Generally, the rules for a group are:

  • All units in the group are in the same spatial "clump".
  • All units in the group were given the same move command.
  • If any unit in the move command is not in the clump, the group is broken and units move towards the destination individually.

How do I define a clump programmatically and detect in a unit is not in the clump?

\$\endgroup\$
1
\$\begingroup\$

I read about this algorithm a few years back for finding groups of units: http://lab.polygonal.de/?p=120

It's called recursive dimensional clustering and also appears in game programming gems 2, and was written by Steve Rabin from Nintendo.

There are probably other algorithms but I personally haven't come across any formally described.

In a nutshell, how it works is that you have a list of objects that each have a min and max x and y (and z if needed). You sort the list across each axis and find groups of objects that overlap on at least one axis.

That might get weird with a large map, but you could limit it to a couple nearest grid cells or something.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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