Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
2  
The word you're looking for is "cluster" not "clutter". –  Nicol Bolas Nov 24 '12 at 20:17

1 Answer 1

up vote 8 down vote accepted

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.

share|improve this answer
    
Oh wow, that's incredibly simple and effective. Thanks! –  TravisG Nov 24 '12 at 18:12
2  
No problem! I would try experimenting with different formations too, like spiral shapes and circles. Have fun. –  Byte56 Nov 24 '12 at 18:18

Your Answer

 
discard

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.