7
\$\begingroup\$

For intentional reasons, certain units in the game I'm currently programming don't have any collision detection and response among each other.

This enables them to clutter right on top of each other. This is a wanted behavior, since there will be situations in the game when the player does want them to stack like that.

However, I want to make the process of uncluttering them easy for the player, so that they just have to press a hotkey or click some button on the screen and have the units disperse just enough so it's easy to select a group of them with the mouse (if they stand on top of each other one mouseclick selects all units).

How could I do this without running a brute force N^2 nearest neighbor search on all units?

\$\endgroup\$
1
  • 4
    \$\begingroup\$ The word you're looking for is "cluster" not "clutter". \$\endgroup\$
    – Nicol Bolas
    Commented Nov 24, 2012 at 20:17

1 Answer 1

Reset to default
8
\$\begingroup\$

Create a grid with enough spaces for all the units you want to "unclutter", have them each choose the nearest unclaimed grid space. Then have them move towards their respective grid space.

enter image description here

This will move them into something like a formation, where the player can easily select an individual unit.

That's an O(N) operation with pretty good results.

\$\endgroup\$
2
  • \$\begingroup\$ Oh wow, that's incredibly simple and effective. Thanks! \$\endgroup\$
    – TravisG
    Commented Nov 24, 2012 at 18:12
  • 2
    \$\begingroup\$ No problem! I would try experimenting with different formations too, like spiral shapes and circles. Have fun. \$\endgroup\$
    – House
    Commented Nov 24, 2012 at 18:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .